8 ms·
How BigIntegers work in JavaScript
- euroclydon 15y agoSeriously, 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.
- aiham 15y agoThat 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.
- masklinn 15y agoHave 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.
- wbhart 15y agoThat'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!
- gvb 15y agoThe 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 http://en.wikipedia.org/wiki/Endianness
- wbhart 15y agoHere is a javascript bigint library by Leemon Baird http://www.leemon.com/crypto/BigInt.js 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.
- hardy263 15y agoSo does this mean using biginteger for small numbers could require almost 30x more memory?
- Amaan 15y agoWell, yeah, of course. But only an idiot would use a BIGInt for small numbers.
- RodgerTheGreat 15y agoSeems like using base-10 is a mistake- with a higher base, your bignums will be faster and use less memory.
- wbhart 15y agoA 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.
- silentmatt 15y agoIt'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.
- wbhart 15y agoI 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.