Adding BigInts to V8
v8project.blogspot.com
v8project.blogspot.com
Why not use a faster algorithm, like the Karatsuba algorithm[1] or the Toom-Cook[2] algorithm?
It follows that, for sufficiently large n, Karatsuba's
algorithm will perform fewer shifts and single-digit
additions than longhand multiplication, even though its
basic step uses more additions and shifts than the
straightforward formula. For small values of n, however,
the extra shift and add operations may make it run
slower than the longhand method. The point of positive
return depends on the computer platform and context.
As a rule of thumb, Karatsuba is usually faster when
the multiplicands are longer than 320–640 bits.
From your [1]: "As a rule of thumb, Karatsuba is usually faster when the multiplicands are longer than 320–640 bits."
Toom-3 doesn't get faster than Karatsuba (couldn't find numbers quickly). See e.g. https://fossies.org/linux/gmp/tune/README for a discussion.
Reminds me of a demo by my algorithms professor. A certain sorting method (I think binary) requires picking a good pivot to keep complexity down. Picking a random pivot point generally gives good results, but results in an O(n^2) algorithm when asymptotically examined. An algorithm for "perfect" point picking (mean of means I believe) was demonstrated. It resulted in a complexity of O(n) (linear). However, the scale to the linear term was 22. Therefore, in nearly every case, picking randomly would outperform it.
I did not realize Karatsuba required such large numbers to outperform. When I first learned about it, I was under the impression that it would be more effective even for barely "large" numbers
If anyone is curious and wants to figure this out, here's my old sci.math post [1].
[1] https://groups.google.com/d/msg/sci.math/MX3MLCQ0zzA/XTqUoZk...
Do you mean as counted in bits? If so, prepend zeroes until they are the same length. Does this negatively affect the algorithm's results?
EDIT: When I say 'prepend' I mean on the MSB end. In typical arithmetic on paper, that'd be adding leading zeroes (prepending) onto the numbers.
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.
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.
[1] https://github.com/scala-js/scala-js/pull/3286/commits/deec9...
https://webapplog.com/decreasing-64-bit-tweet-id-in-javascri...
The JSON use case was even one of the motivations behind BigInt in the first place:
Or perhaps a proposal could be written to give numbers emitted by JSON.parse a "raw" property, so they could be decoded using BigInt?
e.g. so that {"foo": 1234567890123456789012345678901234567890} doesn't lose precision.
Maybe something like `{"x": 10n}`, but at that point, might as well do reviver, especially if you already agreed on a format and use some to parse out class instances vs plain objects.
I think this for the most part is useful for WASM, but also storing/reading/writing to binary buffers as in handling file formats that stores (u)int64s (such as f.ex. CAF on the Mac) and with binary protocol responses from environments such as Java/.Net that already supports bigints (and of course, eventually Node), finance calculations.. nice.
Just curious, how will you deal with things like triple-comparing (`0x1n === 0x1` ?) internally (from the perspective of performance)?
> BigInts [..] are always signed (in ref. to the >>> operator)
Disclaimer: I haven't taken a deep-dive into the BigInt spec yet, but things like this comes to mind (say you want to shift and mask using unsigned 64-bit values):
0xffffffffffffffffn >> 24 => 0xffffffffffffffffn (hmm)
0xffffffffffffffffn >>> 24 => 0x000000ffffffffffn (but won't be supported)
Shifting is specified here: https://tc39.github.io/proposal-bigint/#sec-numeric-types-bi...
When mixing Number and BigInt, abstract equality (==) works fine, but strict equality (===) is always false, since they are two different primitive types.
Most bitwise operators are allowed, so long as all operands are the same type (Number or BigInt). The only exception is zero-fill right shift (>>>) since that doesn't make any sense with respect to BigInts.
From my console: (node 10 with --harmony-bigint)
> 1n == 1
true
> 1n === 1
false
> 12345n >> 1
TypeError: Cannot mix BigInt and other types, use explicit conversions
> 12345n >> 1n
6172n
> 12345n >>> 1n
TypeError: BigInts have no unsigned right shift, use >> insteadYes, I'm aware of this, but I was more asking in the realm of internal performance/optimization (as I sort of point out - and not necessarily because of the comparer). F.ex. they are in all practicality the same integer and in other cases, IIRC (please correct me if I'm wrong), V8 optimizes the native Number that could easily be stored internally as IEEE-754, to actual internal integers when using bit-ops on them (to indicate to the optimizer you handle integers) and so forth.
In this case I was curious if this would be optimized internally so these comparisons could be moved directly to CPU registers as integers (assuming being on a 64-bit arc) and compared there, for example. But, future will tell - I'm equally aware of that optimizations is not first priority at this stage (it's just me excited to see this manifest). It's in any case a welcome and useful feature optimized or not.
apaprocki linked (thanks!) to a method that can do unsigned right-shift via a method (1.1.11 BigInt::unsignedRightShift).
Also, for compile-to-JS versions of languages where the hosted language has BigInts, which now [0] can be more fully equivalent to the non-JS implementations of the same language. I think it's a while before GC-dependent languages will be WASM hosted, but there are a lot that compile to JS.
[0] where “now” is “sometime in the future where this has broad support among browsers”
It seems that I've never had the use case where I exceeded the maximum or minimum integer count. I figure there's a good amount of JavaScript developers that have the same experience.
But good article nonetheless.
Their JSON API works around that limitation by returning IDs as both "id" (a number that may not be representable in Javascript) and "id_str" (the same number in JS-friendly string form).
Does it note that in the spec? I can't find it.
String is the best choice in JSON but ultimately only somewhat less wrong (since string transformations won’t yield meaningful results for an ID either). That’s why GraphQL defines a discrete ID scalar.
In terms of identity an ID is never a number, always a unique value. It should be its own type.
And after seeing a hundred systems break when IDs started to overflow the 32 bit max, or struggle to handle a change to guids, or alphanumeric security codes, or a harmonization with another systems IDs, or freak out when their numbers get exposed through a URL and it turns out keeping leading-0 formatting has something to say: ... use a damned string.
"00123" and 123 are different. Just use a string.
I can imagine this is an especially important advancement for server side JS. Not something I personally care about tho.
If the numbers are random (like IDs) you’ll hit it about every 1000th ID. Solution: IDs are strings not numbers.
For example, this is an incorrect way to compare numbers:
> 0.1 + 0.2 === 0.3
false
a = 0.1 + 0.2
b = 0.3
> Math.abs(a - b) < Number.EPSILON
true
Not knowing about this can cause many issues if you deal with values representing currency.
That kind of equality test should be:
abs( a-b ) < Number.EPSILON * max( abs(a), abs(b) )
It may also be possible to kind of caste precision away by adding a trick value. eg.
a + t == b + t
abs( a-b ) < Number.EPSILON * tA more popular definition is "the smallest number that yields a result different to 1 when added to 1".
This version of adding a rounding value seems to though:
( a-b + rounder ) == rounder
const tetrate = (a, n)=> n=== 0n ? 1n : a(tetrate(a, n - 1n));
While I expected this to take a long time to run for sufficiently large inputs (on my machine tetrate(7n, 3n) takes about 40 seconds to produce ~3.8 * 10 ^ 695974), some inputs immediately throw a "Maximum BigInt size exceeded" error. This isn't surprising, however; as there has to be _some_ practical limit, but I wonder if anyone knows how V8 determines this? Is it based on available RAM? Do (will) other browser implement something similar?
(defun tetrate (a n)
(if (= n 0) 1
(expt a (tetrate a (1- n)))))
(compile 'tetrate)
(time (integer-length (tetrate 7 3))
2 ** (2 ** n)
2**n
2**32
2**64const tetrate = (a, n)=> n=== 0n ? 1n : a * * (tetrate(a, n - 1n));
And I definitely am not getting the same results described. However; it's still possible to get a "Maximum BigInt size exceeded" error, and I wonder if anyone knows how this is determined?
Edit: it looks like I posted the "proper" formula originally, but HN's formatting strips away Javascript's exponentiation operator. So, I'm using "* *" instead.
I've finished my own bigint implementation in the Nim language:
- stack and power-of-2 only for uint256, uint512, uint1024, etc),
- using recursive types (uint128 = 2x uint64, uint256 = 2x uint128).
It is already quite optimized (division using Burnikel and Ziegler recursive division for example), but I want to make sure it works fine.
big_array[0] = 456;
TypeError: Cannot convert 456 to a BigInt
The usual technique is NaN-boxing, where doubles are stored directly and non-doubles are represented with a NaN. A NaN gives you 51 bits to store to store your data. Usually you have a union type, with some bits for the type tag and the rest for data.
A BigInt may require more than 51 bits. So the obvious representation is to reserve a new tag value, and then in the data bits store a pointer to the heap-allocated structure that you describe. This could be a single array or a chunked linked list.
A further change would be to store small BigInts inline in those 51 bits, e.g. by reserving another tag. This would save a heap allocation at the cost of more branching.
If the lsb is unset, then the remaining 31 bits represent a "small integer", a.k.a. a Smi (on 64-bit, the top 32 bits make the Smi, so that they can be read out of memory with a normal 32-bit access).
If the lsb is set, then the remaining bits are the pointer, where the bottom bits have to be masked off to actually dereference it (practically, most accesses are offset-based field accesses anyway, so we just subtract 1 from the field offset). The other bit, the 2nd lsb, has recently started being used as a weak pointer marker.
So, the type tag isn't stored in bits of the pointer, but rather in the object being pointed to, not dissimilar to a vtable. This has the side-advantage that we can swap the type of an object in-place, without having to update pointers to it. BigInts are immutable, so they are stored as a heap object which holds the object tag (actually another pointer to a "map", that's a story for another time), a bitfield that stores sign and length, and then data inline (very similar to how we store strings).
(pointer|0x1) -> [BigIntMap, bitfield (length+sign), digit0, digit1, ...]
That said, for short-lived BigInts, the allocations may not be as expensive as you might think, since the garbage collector is generational and short-lived objects won't leave the nursery.
Most(?) 64-bit CPUs have a 64bit × 64bit → 128bit multiplication instruction; but AFAIK the C++ language doesn't have anything like this.
https://github.com/v8/v8/blob/6.8.137/src/objects/bigint.cc#...
Basically, serialization will throw if there is a BigInt present. But, the .toJSON() callout is supported if a particular environment wants to opt-in to supporting it in some manner.