The Chrome Scientific Calculator supports "approximate" and "exact" numbers. As a slightly simplified explanation, approximate numbers are represented by native JavaScript floating point numbers. Exact integers are represented by an arbitrary-precision BigInteger class (rational numbers have two BigIntegers for the numerator and denominator).
So how do you do math on arbitrarily large integers in a language that only supports 64-bit floating point numbers? Basically the same way you do math in 3rd grade.
The Basics: Storage
A BigInteger is just a sign and an array of digits, from the least significant to most significant:
// n = -123
var n = {
sign: -1,
digits: [3, 2, 1]
};
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. The sign can be any of {-1, 0, 1} to represent negative, zero, and positive respectively. In mathematical terms (abbreviating digits to "d"):
If you look at the source, you'll probably notice that I'm actually using base 10000000, not base 10. I'm using decimal in these examples because it makes things clearer but everything works pretty much exactly the same way in any base. Using a larger base just makes things more efficient because you get 7 digits in each array entry. The examples below are also simplified for demonstration purposes, and don't handle things like signs and different-sized numbers. Keep in mind too that sign and digits are abbreviated to _s and _d to save a few bytes in the .js file.
OK, so that's simple enough, but what about operators like addition, subtraction, multiplication, and division? They are pretty much exactly how you would do it by hand. I'll go through each of them and show how they work. I'll cover addition and subtraction, then multiplication and division in later posts.
Addition
Here's how would you add two numbers by hand:
314159
+ 2718
-------
316877
You stack them up with the ones place lined up. Then you go from right to left, adding each pair of digits. 8+9 = 17, 5+1 = 6, 1+7 = 8, and so on. But the 17 is a problem, because you can only put down one digit in each place, so you have to carry the 1 to the next place. So backing up, we have 9+8 = 17, so write down the 7 and carry the one, then 5+1+1 = 7. That's one digit so we don't have to carry anything, so we just have 1+7 = 8 and so on. Pretty simple right? It's exactly what you've been doing since first grade (or whenever).
So how would you do that in JavaScript? Remember we're storing the digits "backwards" so digits[0] is the right-most/least significant digit. That means the places are already lined up correctly, so we can just loop through them, adding each pair, and keeping track of the carry. For simplicity, I'll assume that both numbers are positive and we padded the digit arrays with zeros to be the same length. In the actual implementation, any extra digits in one number are handled separately to make it faster.
var c = { sign: 1, digits: [] }; // We'll store the result in c
var carry = 0; // Nothing to carry yet
for (var i = 0; i < a.digits.length; i++) {
c.digits[i] = a.digits[i] + b.digits[i] + carry;
if (c.digits[i] >= 10) { // Oops, too big.
carry = 1; // Set the carry to be added into the next digit
c.digits[i] -= 10; // Adjust to be one digit
}
else {
carry = 0; // It fit, so there's nothing to carry
}
}
if (carry) { // Don't forget to add the final carry if it's needed
c.digits[i] = carry;
}
Instead of the if (c.digits[i] < 10) {... statement, we can use the remainder and (integer) division operators:
c.digits[i] = (a.digits[i] + b.digits[i] + carry) % 10;
carry = Math.floor((a.digits[i] + b.digits[i] + carry) / 10);
Since JavaScript numbers are always floating point, we have to use Math.floor to fake integer division.
Subtraction
Subtraction is basically the exact opposite of addition. You loop through each digit and subtract. If the result is negative, borrow a 10 from the next digit. Again, for simplicity we'll assume the numbers are positive, padded to be the same length, and that a > b (if it's not, we can force it by playing with the signs).
var c = { sign: 1, digits: [] }; // We'll store the result in c
var borrow = 0; // We didn't borrow anything yet
for (var i = 0; i < a.digits.length; i++) {
c.digits[i] = a.digits[i] - b.digits[i] - borrow;
if (c.digits[i] < 10) { // Oops, we can't have a negative digit
borrow = 1; // We'll borrow 10 from the next pair of digits
c.digits[i] += 10; // Add the borrowed 10
}
else {
borrow = 0; // We don't need to borrow anything
}
}
// We made sure a < b to make sure we never have to borrow after the last digit, so we're done
With the combination of addition and subtraction, we can handle adding any combination of positive and negative numbers (e.g. to subtract a negative from a positive, pretend both are positive and add them).
In part 2, I'll cover the multiplication algorithm. Division will come in a later post.
