Black lives matter

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

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)`