sign × mantissa × 2exponentThe 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 9007199254740996Rounding effects during the addition make things unpredictable for odd increments (+1 versus +3). The actual representation is a bit more complicated , but this explanation should help you understand the basic problem.
Example: Twitter JSON dataThe 53 bit limit matters whenever an API returns 64 bit numbers. For example, the Twitter API encodes tweets in JSON as follows:
ComparisonsComparing 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" 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.
Addition and subtractionFor 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)
- (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).
MultiplicationGeneral multiplication builds on a foundation of single-digit multiplication.
Single-digit multiplicationSingle-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 ---- 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
General multiplicationFor 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 ------------ 139676498390If one or both of the operands are negative, we multiply the absolute values and, in the former case, invert the sign.
DivisionWhen performing the division
x / yfor 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.
- 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 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 15For general division, one divides the absolute values of the operands and makes the usual sign-related adjustments.
Using the strint libraryLet’s put the library to use. Remember that without it, we get the following wrong result:
> 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)