ES2020: BigInt – arbitrary precision integers

[2017-03-19] dev, javascript, es2020, numbers
(Ad, please don’t block)

Warning: This blog post is slightly outdated. Tread carefully.

The ECMAScript proposal “BigInt: Arbitrary precision integers in JavaScript” by Daniel Ehrenberg is currently at stage 3. This blog post gives an overview.

Update 2017-07-27: Update to reflect the name change from Integer to BigInt.

Rationale  

Given that the ECMAScript standard only has a single type for numbers (64-bit floating point numbers) it’s amazing how far JavaScript engines were able to go in their support for integers: fractionless numbers that are small enough are stored as integers (usually within 32 bits, possibly minus bookkeeping information).

However, JavaScript can only safely represent integers with up to 53 bits plus a sign. Sometimes, you need more bits. For example:

  • Twitter uses 64-bit integers as IDs for tweets (source). In JavaScript, these IDs have to be stored in strings.
  • Financial technology uses so-called big ints (integers with arbitrary precision) to represent sums of money.

Core parts of the proposal  

The proposal is about adding a new primitive type for big ints to JavaScript. Given that implicit integers (Array indices etc.) will continue to exist separately, they will be called BigInts.

Core parts of the proposal are:

  • Literals for BigInts: Each literal is a series of digits, suffixed with an n. For example: 123n
  • typeof returns 'bigint' for BigInt values:
    > typeof 123n
'bigint'
  • Operators such as + and * are overloaded and work with BigInts. The number of bits used to store values is increased as necessary, automatically.
  • There is a wrapper constructor BigInt for BigInts, which is similar to Number for Numbers and other wrapper constructors.

Next, we will look at a first example and then will examine all aspects of the proposal in detail.

A first example  

This is what using BigInts looks like (example taken from the proposal’s readme):

/**
 * Takes a BigInt as an argument and returns a BigInt
 */
function nthPrime(nth) {
  function isPrime(p) {
    for (let i = 2n; i < p; i++) {
      if (p % i === 0n) return false;
    }
    return true;
  }
  for (let i = 2n; ; i++) {
    if (isPrime(i)) {
      if (--nth === 0n) return i;
    }
  }
}

BigInt literals  

Like Number literals, BigInt literals support several bases:

  • Decimal: 123n
  • Hexadecimal: 0xFFn
  • Binary: 0b1101n
  • Octal: 0o777n

Negative BigInts are produced by prefix the unary minus operator: -0123n

Operator overloading  

The general rule for binary operators is:

You can’t mix Numbers and BigInts: If one operand is a BigInt, the other one can’t be a Number.

If you do mix them, a TypeError is thrown:

> 2n + 1
TypeError

The reason for this rule is that there is no general way of coercing a Number and a BigInt to a common type: Numbers can’t represent BigInts beyond 53 bits, BigInts can’t represent fractions. Therefore, the exceptions warn you about typos that could change the results of computations in unexpected ways.

To see why, let’s look at an example: 9007199254740991 is the highest integer that Numbers can represent safely. You can see that if you try adding 1 to the “unsafe” 9007199254740992

> 9007199254740992 + 1
9007199254740992

If 9007199254740992n + 1 were interpreted as a Number (due to coercion), you would get wrong results.

Additionally, disallowing mixed operand types keeps operator overloading simple, which is helpful should overloading be extended further in the future.

The following sections explain what operators are available for BigInts.

Arithmetic and ordering  

  • Binary +, binary -, *, ** work as expected.

  • /, % round towards zero (think Math.trunc()).

    > 1n / 2n
0n

  • Ordering operators <, >, >=, <= work as expected.

  • Unary - works as expected. Unary + is not supported for BigInts, because much code (incl. asm.js) relies on it coercing its operand to Number.

Bit operators  

For bit operators, A negative sign is interpreted as an infinite two’s complement. E.g.:

  • -1 is ...111 (ones extend infinitely to the left)
  • -2 is ...110 (ones extend infinitely to the left)

That is, a negative sign is more of an external flag and not represented as an actual bit.

The following bit operators exist:

  • Bitwise operators |, &, ^ for BigInts work analogously to their Number versions.

  • Signed shift operators <<, >> for BigInts work analogously to their Number versions. Note that here, too, both operands need to be BigInts.

Bit operators for Numbers limit their operands to 32 bits. All operators (except for unsigned right shift >>>) interpret the highest (31st) bit as a sign:

> Math.pow(2,30) | 0
1073741824
> Math.pow(2,31) | 0
-2147483648
> (Math.pow(2,32)-1) | 0
-1

You can shift a positive Number left so that the highest (31st) bit is set and it becomes negative:

> Math.pow(2,30) << 1
-2147483648

With BigInts, that can never happen, because they are not limited to specific number of bits and there is therefore no sign bit.

There is no unsigned right shift operator >>> for BigInts, because its semantics are: “shift in” a zero, replace the highest bit with a zero. First, there is no highest bit. Second, with the infinite sequence of ones prefixing negative values, you’d have to insert a zero somewhere, which makes no sense. Thus, preserving the sign is the natural (and only) thing to do for BigInts and there is no >>> operator.

One last illustration of how negative bit operands work: For both Numbers and BigInts, however often you signed-shift -1 to the right, the result is always -1:

> -1 >> 20
-1
> -1n >> 20n
-1n

Equality  

Lenient equality (==) and inequality (!=) are coercing operators, which makes them difficult to adapt to BigInts. At the moment, comparing Numbers and BigInts throws an exception:

> 0n == 0
TypeError

Alas, lenient equality coerces booleans to Numbers, meaning that exceptions are thrown, too:

> 0n == false
TypeError

Strict equality (===) and inequality (!==) only consider values to be equal if they have the same type. Therefore, adapting them to BigInts is simple:

> 0n === 0
false

The wrapper constructor BigInt  

Similar to Numbers, BigInts have the associated wrapper constructor BigInt(). It works as follows:

  • BigInt(x): convert arbitrary values x to BigInt. This works similarly to Number(), but:

    • A TypeError is thrown if x is either null or undefined.
    • Instead of returning NaN for Strings that don’t represent BigInts, a SyntaxError is thrown.

  • new BigInt(): throws a TypeError.

This is what using BigInt() looks like:

> BigInt(undefined)
TypeError
> BigInt(null)
TypeError

> BigInt(false)
0n
> BigInt(true)
1n

> BigInt(123)
123n

> BigInt('123')
123n
> BigInt('123n')
SyntaxError
> BigInt('abc')
SyntaxError

BigInt methods  

BigInt.prototype holds the methods “inherited” by primitive BigInts:

  • BigInt.prototype.toLocaleString(reserved1?, reserved2?)
  • BigInt.prototype.toString(radix?)
  • BigInt.prototype.valueOf()

Utility functions  

  • BigInt.asUintN(width, theInt)
    Casts theInt to width bits (unsigned). This influences how the value is represented internally.

  • BigInt.asIntN(width, theInt)
    Casts theInt to width bits (signed).

  • BigInt.parseInt(string, radix?)
    Works similarly to Number.parseInt(), but throws a SyntaxError instead of returning NaN:

    > BigInt.parseInt('9007199254740993', 10)
9007199254740993n
> BigInt.parseInt('abc', 10)
SyntaxError

    For comparison, this is what Number.parseInt() does:

    > Number.parseInt('9007199254740993', 10)
9007199254740992
> Number.parseInt('abc', 10)
NaN

Casting and 64-bit integers  

Casting allows you to create integer values with a specific number of bits. If you want to restrict yourself to just 64-bit integers, you have to always cast:

const int64a = BigInt.asUintN(64, 12345n);
const int64b = BigInt.asUintN(64, 67890n);
const result = BigInt.asUintN(64, int64a * int64b);

Coercing BigInts to other primitive types  

This table show what happens if you convert BigInts to other primitive types:

Convert to Explicit conversion Coercion (implicit conversion)
boolean Boolean(0n) → false !0n → true
Boolean(int) → true !int → false
number Number(int) → OK +int → TypeError
string String(int) → OK ''+int → OK

Still under discussion: Should the result of String() applied to a BigInt should have the suffix 'n'? At the moment, it works like this:

> String(123n)
'123'

TypedArrays and DataView operations for 64-bit values  

BigInts make it possible to add 64 bit support to Typed Arrays and DataViews:

  • New Typed Array constructors:
    • Uint64Array
    • Int64Array
  • New DataView methods:
    • DataView.prototype.getInt64()
    • DataView.prototype.getUint64()

BigInts and JSON  

BigInts in JSON data will probably be handled similarly to other unsupported data such as symbols:

> JSON.stringify(123n)
undefined
> JSON.stringify([123n])
'[null]'

Future  

There will probably be a library with functions and constants for BigInts (think Math, but for BigInts instead of Numbers).

Implementors of JS engines are optimistic that BigInts will be able to efficiently support integers with various bit sizes. But one could, in principle, introduce subtypes of BigInt (Uint64, Uint8, ...).

Beyond BigInts  

We’ll probably eventually see support for:

  • Custom value types (compared by value; think: primitive types user-defined via classes)
  • Operator overloading
  • Custom number literal syntax

The following features may be added to JavaScript and could be based on these mechanisms.

  • Decimal data type: for base-10 arithmetic, which is useful for representing sums of money and results of scientific measurements.
  • Rational data type: representing fractions (1/3 etc.) without rounding.
  • Complex numbers
  • Vectors and matrices
  • And more

FAQ: BigInts  

How do I decide when to use Numbers and when to use BigInts?  

My recommendations:

  • Use Numbers for up to 53 bits and for Array indices. Rationale: They already appear everywhere and are handled efficiently by most engines (especially if they fit into 31 bits). Appearances include:
    • Array.prototype.forEach()
    • Array.prototype.entries()
  • Use BigInts for large numeric values: If your fraction-less values don’t fit into 53 bits, you have to choice but to move to BigInts.

All existing web APIs return and accept only Numbers and will only upgrade to BigInt on a case by case basis

Why not just increase the precision of Numbers in the same manner as is done for BigInts?  

One could conceivably split Number into Integer and Double, but that would add many new complexities to the language (several Integer-only operators etc.). I’ve sketched the consequences in a Gist.

Conclusions  

It is great to see support for integers beyond 53 bits being planned for JavaScript. Supporting various bit sizes via the single type BitInt is an interesting experiment. It’d be great if it worked out.

With BigInts, we get a glimpse at what JavaScript would be like if it had had exceptions from the start (they were introduced in ES3): using the wrong operands for some of the operators throws exceptions now.

Further reading  

Acknowledgement. Thanks to Daniel Ehrenberg for reviewing this blog post.