[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
### 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` 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:
`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:
### Addition and subtraction

For general addition and subtraction, one first implements two operations:
### 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:
### 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:
### Division

When performing the division
`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.
`y` within the digits of `x` is marked by a pipe symbol (`|`). The following steps divide 290 by 15.
## Using the strint library

Let’s put the library to use. Remember that without it, we get the following wrong result:
## References

This post is part of a series on numbers.

sign × mantissa × 2The 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:^{exponent}

> 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 9007199254740996Rounding 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.

{"id": 10765432100123456789, "id_str": "10765432100123456789", ...}What is going on here? Why has the integer-valued property

> parseInt("10765432100123456789") 10765432100123458000Therefore, 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

> "3" > "12" trueWith padding, everything works correctly:

> "03" > "12" falseIf 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.

- Positive addition: both operands are positive
- Positive subtraction: The first operator (minuend) is greater than the second operator (subtrahend)

- (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).

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 ---- 2772One 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 = 81Even 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

23958233 * 5830 ------------ 00000000 = 23958233 * 0 71874699 = 23958233 * 30 191665864 = 23958233 * 800 119791165 = 23958233 * 5000 ------------ 139676498390If one or both of the operands are negative, we multiply the absolute values and, in the former case, invert the sign.

x / yfor two positive integers

- Is
`y > x`? Then we are done,`x`is the remainder,`r`is the result. - 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. - Otherwise, perform a “shift”: Move
`y`one digit to the right, multiply`r`by 10. Continue with step 2.

x = r yThe current position of the digits of

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 15For general division, one divides the absolute values of the operands and makes the usual sign-related adjustments.

> 9007199254740992 + 1 9007199254740992Strint 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)`