Unlimited-size base conversion?

Question

I'm trying to implement a BigInt type in JavaScript using an array of integers. For now each one has an upper-bound of 256. I've finished implementing all integer operations, but I can't figure out how to convert the BigInt to its string representation. Of course, the simple way is this:

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';
};

But when the BigInts actually get big, I won't be able to convert by adding anymore. How can I convert an array of base-x to an array of base-y?

Answer 1

See the example I gave in this answer to a similar question recently (it's for base-10 to base-3, but the principle should be transferrable): C Fast base convert from decimal to ternary.

In summary:

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.

Note that I make no claims that this approach is in any way fast (I think it's O(n^2) in the number of digits); I'm sure there are algorithmically faster approaches than this.