Hacker News Reader

Comment by hardy263 | Hacker News Reader

So does this mean using biginteger for small numbers could require almost 30x more 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.

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.

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

The article says that the author uses base 10000.

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

Reply on news.ycombinator.com