> 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.
I agree that the approach "everything is a bigint" plus optimizations where a fixed width int suffices would be nice from the semantic perspective.
However, Javascript has basically the "everything is a floating point number" approach, and bigints would be hard to fit into that (do you want bigfloat as well? do you want to reproduce float arithmetic imprecision, or be precise? Etc.)
However, bigint could internally use just one fixed width number when possible as an optimization - although the current implementation doesn't seem to do this.
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.