How BigIntegers work in JavaScript
silentmatt.com
How BigIntegers work in JavaScript
1–10 of 15 posts
Re: How BigIntegers work in JavaScript
#2Seriously, 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.
Re: How BigIntegers work in JavaScript
#3Seriously, 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.
Re: How BigIntegers work in JavaScript
#4Seriously, 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.
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.
Re: How BigIntegers work in JavaScript
#5Seriously, 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'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!
Re: How BigIntegers work in JavaScript
#6Here 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.
Re: How BigIntegers work in JavaScript
#7So does this mean using biginteger for small numbers could require almost 30x more memory?
Re: How BigIntegers work in JavaScript
#8So 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.
Re: How BigIntegers work in JavaScript
#9Seriously, 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.
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
Re: How BigIntegers work in JavaScript
#10So does this mean using biginteger for small numbers could require almost 30x more memory?
Seems like using base-10 is a mistake- with a higher base, your bignums will be faster and use less memory.