javascript - 无限大小的基础转换？

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 实际变得大时，我将无法再通过加法进行转换。如何将 base-x 数组转换为 base-y 数组？

Answer 1

参见我最近在类似问题的回答中给出的示例(它是 base-10 到 base-3，但原则应该是可转移的):C Fast base convert from decimal to ternary .

总结:

Iterate over the input digits, from low to high. For each digit position, first calculate what 1000....000 (base-256) would be in the output representation (it's 256x the previous power of 256). Then multiply that result by the digit, and accumulate into the output representation.

You will need routines that perform multiplication and addition in the output representation. The multiplication routine can be written in terms of the addition routine.

请注意，我并没有声称这种方法在任何方面都很快(我认为它的位数是 O(n^2))；我确信有比这更快的算法方法。