> we allocate an object in memory. We make it large enough to hold all the BigInt’s bits, in a series of chunks, which we call “digits”

In the Lisp world, the halfwords or words or whatever that a bignum's bits are divided into are called "bigits". At least, this is the term I heard around MIT in the late 1970s. I always thought it was cute.

Anyway, I'm glad to see this. I think all garbage-collected languages should provide arbitrary-precision integers as the default integer type, as Lisp has for decades. This certainly goes for interpreted languages like JavaScript, Python (which did adopt this policy at some point), Ruby, and even, I would argue, Java and C#. This, for example, is to me not a bug in the algorithm, but in the language, as it wouldn't happen in Common Lisp: https://research.googleblog.com/2006/06/extra-extra-read-all...

(Bounded integer types are available in Common Lisp, but it would be strange to use them for the bounds in a binary search algorithm, whose runtime is almost certain to be dominated by the comparison function. In any case their use would require a conscious choice on the part of the programmer.)

The sad thing about the way that Java and now JavaScript implement BigInts is that they're a separate type from ordinary integers, rather than having a single type that automatically changes between an immediate representation ("fixnums"), for integers that fit into a machine word less a few tag bits, and an allocated representation ("bignums") for larger integers. The latter provides the semantic benefits of arbitrary-precision integers at a much smaller runtime cost than if they're all allocated.