Silent Matt » How BigIntegers Work, part 1: Storage, Addition, and Subtraction

Silent Matt » How BigIntegers Work, part 1: Storage, Addition, and Subtraction

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.

Read full article from Silent Matt » How BigIntegers Work, part 1: Storage, Addition, and Subtraction