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?

Outride

Is the question simply "what characters can I use after f"? – Embattled

No, not at all. I want to convert, for example, {1, 3} in base-256 to {2, 5, 9} in base-10. – Outride

@minitech: Ok, then I've misunderstood the question. Maybe it's because I'm tired, but I can't figure out what the specific problem is? – Embattled

I'm implementing a BigInt type to hold arbitrary-size integers in JavaScript. If I just keep using Math.pow and summing it up, then converting, I'll exceed the allowed size for a JavaScript Number and end up with Infinity. – Outride

@minitech: Oh, I see. It's the fact that you can't sum all the digits into total... right. – Embattled

@minitech: Without wishing to blow my own trumpet, see this answer I provided for a similar question very recently: #5834358. It's specific to base-10 to base-3, but the solution could easily be adapted. Let me know if that's at all close... – Embattled

Ah, that's a great idea!! Will I have to implement another BigInt with multiplication only that uses the particular base conversion, though, to multiply them without overflow? Or use string multiplication? I suppose that's OK, since toString() won't be called until the result is required, but if there is a better (if more complex) way I'd still prefer to use that... – Outride

@minitech: Yes, you'll need to implement a routine that can do addition (and by extension, multiplication) in the output base. I don't know anything about Javascript at all, but is there a way you can re-use your existing BigInt routines, but parameterise the base that they work in? – Embattled

Not really, but I could change them to work that way fairly quickly. Thanks, you should post that as an answer. – Outride

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.

Embattled

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...

Fregger