无限大小的进制转换？

Question

我正在尝试使用整数数组在JavaScript中实现BigInt类型。现在每个整数的上限为256。我已经完成了所有整数操作，但我无法弄清楚如何将BigInt转换为其字符串表示形式。当然，简单的方法是：

BigInt.prototype.toString = function(base) {
    var s = '', total = 0, i, conv = [
        ,,
        '01',
        '012',
        '0123',
        '01234',
        '012345',
        '0123456',
        '01234567',
        '012345678',
        '0123456789',
        ,
        ,
        ,
        ,
        ,
        '0123456789abcdef'
    ];
    base = base || 10;

    for(i = this.bytes.length - 1; i >= 0; i--) {
        total += this.bytes[i] * Math.pow(BigInt.ByteMax, this.bytes.length - 1 - i);
    }

    while(total) {
        s = conv[base].charAt(total % base) + s;
        total = Math.floor(total / base);
    }

    return s || '0';
};

但是当BigInts实际变得很大时，我将无法再通过加法进行转换。我该如何将基于x的数组转换为基于y的数组？

- Ry-

---

问题是否仅仅是“在f之后我可以使用哪些字符”？ - Oliver Charlesworth

@minitech：好的，那么我误解了问题。也许是因为我累了，但我无法弄清楚具体问题是什么？ - Oliver Charlesworth

我正在JavaScript中实现一个BigInt类型，用于保存任意大小的整数。如果我继续使用Math.pow并将其相加，然后进行转换，我将超出JavaScript Number允许的大小，并最终得到Infinity。 - Ry-

@minitech：哦，我明白了。你不能将所有数字相加到“总数”中……对吧。 - Oliver Charlesworth

@minitech：不想自吹自擂，可以看看我最近为类似问题提供的答案：http://stackoverflow.com/questions/5833858/c-fast-base-convert-from-decimal-to-ternary/5834086#5834086。它是针对十进制到三进制的转换，但解决方案很容易适应其他情况。如果有需要，请告诉我... - Oliver Charlesworth

Answer 1

请参考我最近回答类似问题时提供的示例（它是用于十进制到三进制的，但原则应该是可转移的）：C Fast base convert from decimal to ternary。

总结一下：

从低到高迭代输入数字。对于每个数字位置，首先计算输出表示中 1000....000（基数为256）的值（它是前一个 256 倍的 256 的幂）。然后将该结果乘以该数字，并累加到输出表示中。

您需要编写执行输出表示中的乘法和加法的程序。可以使用加法程序编写乘法程序。

请注意，我不断言这种方法在任何方面都很快（我认为它在数字位数的 O(n^2) 级别）；我相信有比这更快的算法。

- Oliver Charlesworth

Answer 2

如果你比我现在更愿意戴上数学思维帽子，似乎有人已经解释了如何使用帕斯卡三角形转换数字表示：

http://home.ccil.org/~remlaps/DispConWeb/index.html

在底部附近有源代码的链接。它们是Java而不是JavaScript，但如果你付出了努力去理解数学，你可能可以自己实现或者付出努力来移植代码...

- Trott