Re:Adding BigInts to V8
by ScottBurson on Thursday May 03, 2018 @02:53AM
(#16983865)
I tried this in Common Lisp:
(defun tetrate (a n)
(if (= n 0) 1
(expt a (tetrate a (1- n)))))
(compile 'tetrate)
(time (integer-length (tetrate 7 3))
I used 'integer-length' to check that a number of the correct magnitude was produced without actually having 700kB of digits dumped into my REPL buffer. On a new MacBook Pro running SBCL, this took, ah, 624 milliseconds. So there's some room for optimization of the JavaScript implementation :-)Oops! I shouldn't try out new features right before going to bed... Here's the proper formula:
const 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.
Re:Adding BigInts to V8
by TazeTSchnitzel on Thursday May 03, 2018 @07:13AM
(#16984893)
IME it's easy to get an error in bigint libraries if you do something like
2 ** (2 ** n)
for some n greater than a few dozen. Because then you will have 2**n
digits, and the internal value holding the number of digits is limited to 2**32
or 2**64
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?
[0] https://en.wikipedia.org/wiki/Tetration