Why we should care: JavaScript’s unique Number type
Handling large integers in JavaScript requires care. JavaScript treats numeric variables as a single type called Number.
Unlike other programming languages, JavaScript does not divide numbers into real and integer types such as float and int or storage sizes such as short, int, and long. JavaScript’s Number type seems to use the IEEE-754 64-bit floating point number representation.
This property is very convenient for most casual calculations. However, handling large integers requires slightly different care than other programming languages. Especially in environments like competitive programming or coding tests, you may fail.
How big is a large integer?
Bitwise operations: 32 bits
As explained in the previous article, JavaScript treats numbers as 32-bit integers when performing bitwise operations. Therefore, we can observe a strange phenomenon in which the following equation is true without errors:
1 | 1 << 32 === 1 |
If you want bitwise operations wider than 32 bits, you should use the BigInt type.
Numeric operations: 53 bits
JavaScript does not distinguish between real numbers and integers, but precision decreases when numbers grow larger than a certain level. To be more precise, if the calculation result requires more than 53 bits when expressed as an integer, we should not treat the result as an integer. For example, the following expression is true in JavaScript:
1 | 9007199254740992 + 1 === 9007199254740992 |
Therefore, if we want exact integer arithmetic, we must check whether the result is between Number.MIN_SAFE_INTEGER and Number.MAX_SAFE_INTEGER. If we wish exact integer arithmetic beyond that range, we should consider the BigInt type.
Limitations of BigInt
ECMAScript 2020 introduced the BigInt type for arbitrary precision integer calculations. It solved the problem of handling large integers but also has limitations.
Incompatible with Number type
The BigInt type is incompatible with the Number type. For example, 1n + 1 will raise a TypeError. Therefore, we need to check the types of both operands of binary operators and cast one of them if needed.
You also cannot use Math.* functions since Math.* functions are defined for the Number types. You can’t use JSON.stringify either.
BigInt operations take too long time sometimes
The current implementation of BigInt operations is in a best-effort manner without any restrictions. In theory, it has the advantage of being able to compute any large integer. However, in reality, if the result is too large, it may cause the JavaScript engine to stop. You can experience your JavaScript engine hanging with the following simple command:
1 | s = BigInt(1e9 + 7) |
Therefore, unless you have to use the BigInt type, it is better to use the Number type.
Pitfalls of integer handling in JS
Migrating bit-masking code from other programming languages
In the case of C/C++ or Java, bitwise operation assumes 64-bit. Python allows bitwise operations even on large numbers of bits. However, the bitwise operation of the JavaScript’s Number type is limited to 32 bits. So, we should refactor the implementation to the BigInt type if the number of bits to be processed exceeds 32.
Modular arithmetic including multiplication
In competitive programming, some problems require modular arithmetic. In most cases, the base decimal is at most 32 bits. Therefore, there is no problem if we implement modulo arithmetic operations with the Number type. However, if the algorithm requires multiplication, you must consider whether the multiplication result exceeds 53 bits.
For example, 10^9 + 7, a widely used prime number as modulo base, requires 30 bits. The multiplication of two numbers can be 60 bits, more than 53 bits. Therefore, we should consider the BigInt type to implement multiplication.