How BigIntegers work in JavaScript | Hacker News Reader

How BigIntegers work in JavaScript

silentmatt.com

26 pointsAmaan14 comments

Open articleView on HN

Here is a javascript bigint library by Leemon Baird

http://www.leemon.com/crypto/BigInt.js

It's about the best I've seen and embodies all the principles that are being explained by Matt.

Seriously, for the number -123, the array [3, 2, 1] has the least significant digit in position zero?

[edit] Ah ha, printed arrays have position zero on the left. I thought it was on the right.

That way digits[0] will be the least significant digit for any given BigInteger, and digits[1] will always be the second, and so on.

Rather than digits[2] for -123's least significant digit, and digits[1] for, say, 43's least significant digit.

Have you read the explanations? They're pretty sensible: it makes digits "align" correctly, so you can essentially just zip & reduce your digits. Which is what you want to do for many operations. Otherwise you'd have to start by reversing your digits arrays or do weird index computations.

It's rather clever.

That's quite standard. The sign can be taken care of separately if one wishes.

The reason for putting the least significant digit first is that carries accumulate towards the most significant digit in ordinary arithmetic. Thus many of the simplest operations want to work from least significant to most significant digit. A final carry out at the top might add an extra digit to the result. It would be really annoying to work with arrays that had most significant digit first. If you had an extra digit you'd have to shift the entire array one place to accommodate it!

The digits look backwards, but by storing the digits with the ones place first, they will line up with other numbers correctly even if they have different lengths.

Aka little endian. http://en.wikipedia.org/wiki/Endianness

So does this mean using biginteger for small numbers could require almost 30x more memory?

Well, yeah, of course. But only an idiot would use a BIGInt for small numbers.

Seems like using base-10 is a mistake- with a higher base, your bignums will be faster and use less memory.

A serious bignum library wouldn't use base 10. I understood that he intended that you use base 10^15 or something like that. And even that was only by way of illustration.

A more standard approach when using doubles would be to use base 2^32. This is important if you want to implement a Schoenhage-Strassen FFT, which certainly makes use of the fact that the base is a power of 2.

It's actually base 10^7 :) The reason for that is that at the lowest level, the result of any operation on a single digit needs to fit in a JavaScript Number. Since you sometimes have to multiply two digits and 64-bit floats have about 15 digits of precision, the largest power of 10 that will never lose precision is 10^7 (because 10^7 * 10^7 = 10^14).

Of course, it would be more efficient to use a power of two, but using a power of 10 makes converting back and forth between strings (in decimal) quite a bit faster. In my original use case that was a large factor, so it's what I went with.

I understand.

Of course you can also multiply 32 x 32 -> 64 bits in Javascript. But of course you need more than one operation to do it.

The article says that the author uses base 10000.

It's hard to say exactly how much more memory it takes, but yes, there is quite a bit of overhead, especially for small numbers. But that's the trade-off you have to make in order to support the large numbers. Obviously you wouldn't use BigIntegers for everything.

Reply on news.ycombinator.com