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.

Answer 2

If you're prepared to put on your math thinking cap more than I am right now, someone seems to have explained how to convert digit representations using Pascal's triangle:

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

There are links to the source code near the bottom. They're in Java rather than JavaScript, but if you're putting in the effort to grok the math, you can probably come up with your own implementation or put in the effort to port the code...