Working with large integers in JavaScript

[2012-07-05] numbers, dev, javascript, jsint, jslang
(Ad, please don’t block)
In JavaScript, one has at most 53 bits for integers. This blog post explains how to work with large integers, by encoding them in strings.

JavaScript only supports 53 bit integers

All numbers in JavaScript are floating point which means that integers are always represented as
sign × mantissa × 2exponent
The mantissa has 53 bits. You can use the exponent to get higher integers, but then they won’t be contiguous, any more. For example, you generally need to multiply the mantissa by two (exponent 1) in order to reach the 54th bit. However, if you multiply by two, you will only be able to represent every second integer: 
    > Math.pow(2, 53)  // 54 bits
    9007199254740992
    > Math.pow(2, 53) + 1
    9007199254740992
    > Math.pow(2, 53) + 2
    9007199254740994
    > Math.pow(2, 53) + 3
    9007199254740996
    > Math.pow(2, 53) + 4
    9007199254740996
Rounding effects during the addition make things unpredictable for odd increments (+1 versus +3). The actual representation is a bit more complicated [1], but this explanation should help you understand the basic problem.

Example: Twitter JSON data

The 53 bit limit matters whenever an API returns 64 bit numbers. For example, the Twitter API encodes tweets in JSON as follows: 
    {"id": 10765432100123456789, "id_str": "10765432100123456789", ...}
What is going on here? Why has the integer-valued property id been duplicated as the string-valued property id_str? IDs in Twitter are 64 bits long. While JSON is a text format and can represent integers of arbitrary size, you lose precision in JavaScript once numbers are parsed: 
    > parseInt("10765432100123456789")
    10765432100123458000
Therefore, if you want to preserve the value of an ID in JavaScript, you need to store it in a string. Languages that have 64 bit unsigned integers can use the property id and don’t need id_str.

Working with large integers in JavaScript

We can represent integers of arbitrary size as strings. But then we can’t perform arithmetic operations such as addition and division. Those have to be implemented. The JavaScript library strint (“string-encoded integers”) is one such implementation. In the following subsections, we look at the algorithms that have been used. The main goal was to make things easy to understand, not to make them fast. Hence, the algorithms work equally well for humans, on paper – memories of high school might come back.

Working with signs

A number is considered negative if it is prefixed with a minus sign, which is the dash (-) in JavaScript. Hence computing the absolute value of a string-encoded integer is simple: Remove a prefixed dash if there is one.

Comparisons

Comparing two positive integers x and y is simple: Prefix the shorter integer with enough zeros so that both integers have the same number of digits. Then use string comparison. For example, without padding, 3 is greater than 12: 
    > "3" > "12"
    true
With padding, everything works correctly: 
    > "03" > "12"
    false
If one or both of the integers can be negative, you have to look at four cases:
  • (positive, positive): Compare as explained above.
  • (positive, negative): The first operand is greater than the second operand.
  • (negative, positive): The second operand is greater than the first operand.
  • (negative, negative): Compute the absolute values of the operands, compare them (as positive numbers), return the boolean negation of the result.

Addition and subtraction

For general addition and subtraction, one first implements two operations:
  • Positive addition: both operands are positive
  • Positive subtraction: The first operator (minuend) is greater than the second operator (subtrahend)
Both are easy to do, by adding or subtracting digit by digit with carry-over, from right to left. General addition is implemented by examining the signs of the operands:
  • (positive, positive): add the operands, as explained above.
  • (negative, negative): add the absolute values of both operands, negate the result.
  • (positive, negative): Subtract the absolute value of the smaller operand from the absolute value of the larger operand. Invert the sign if the larger operand is negative.
  • (negative, positive): Handle the same as (positive, negative).
General subtraction is handled by performing general addition with a negated second operand.

Multiplication

General multiplication builds on a foundation of single-digit multiplication.

Single-digit multiplication

Single-digit multiplication means multiplying an arbitrary positive integer with a single digit. Such a multiplication can be performed digit by digit, with carry-over. For example: 
     396 * 7
       2     ←     6*7 = 42 (2, carry over 4)
      7      ← 4 + 9*7 = 67 (7, carry over 6)
     7       ← 6 + 3*7 = 27 (7, carry over 2)
    2        ← 2 + 0*7 =  2
    ----
    2772
One worry is that the carry-over might overflow. However, the largest possible carry-over is always 8. At the beginning, the largest carry-over one can produce is 8: 
    9*9 = 81
Even with that carry-over and assuming again the worst case of 9*9, one can only produce a carry-over of 8: 
    8 + 9*9 = 89

General multiplication

For general multiplication of two positive integers, we multiply each digit of the second operand with the first operand. We then add up the results, while taking the power of ten of the second-operand digit into consideration. For example: 
        23958233 * 5830
    ------------
        00000000 = 23958233 *    0
       71874699  = 23958233 *   30
     191665864   = 23958233 *  800
    119791165    = 23958233 * 5000
    ------------
    139676498390
If one or both of the operands are negative, we multiply the absolute values and, in the former case, invert the sign.

Division

When performing the division 
    x / y
for two positive integers x and y, one repeatedly performs the following steps. The result is computed via a variable r, which is initialized with 0. During each step, x is decremented, while r is incremented. We (mentally) write y underneath x and align their leftmost digits.
  1. Is y > x? Then we are done, x is the remainder, r is the result.
  2. Is y less or equal to the digits that start above it and continue until the leftmost digit of x? Then subtract y from the digits above it as often as you can. Increment r by one for each subtraction. Continue with step 1.
  3. Otherwise, perform a “shift”: Move y one digit to the right, multiply r by 10. Continue with step 2.
To understand how this works, it’s best to look at an example. We use the following notation: 
    x = r
    y
The current position of the digits of y within the digits of x is marked by a pipe symbol (|). The following steps divide 290 by 15. 
    290 = 0   // digits above y larger, can subtract
    15

    140 = 1   // digits above y smaller, must shift
    15

    140 = 10  // digits are 140, can subtract 9 times
     15

      5 = 19  // y > x, we are done: result 19, remainder 5
     15
For general division, one divides the absolute values of the operands and makes the usual sign-related adjustments.

Using the strint library

Let’s put the library to use. Remember that without it, we get the following wrong result: 
    > 9007199254740992 + 1
    9007199254740992
Strint computes the correct result: 
    > var strint = require("./strint");
    > strint.add("9007199254740992", "1")
    '9007199254740993'
Other operations that are available:
  • lt(x, y): is x < y (“less than”)?
  • le(x, y): is x ≤ y (“less or equal”)?
  • gt(x, y): is x > y (“greater than”)?
  • ge(x, y): is x ≥ y (“greater or equal”)?
  • eq(x, y): is x = y (“equals”)?
  • add(x, y)
  • sub(x, y)
  • mul(x, y)
  • div(x, y)
  • abs(x)
  • isNegative(x)
  • isPositive(x)
  • negate(x)

References

This post is part of a series on numbers.
  1. How numbers are encoded in JavaScript