30 ms·

As someone who likes to play around with math, it's "fun" to be able to implement functions that output large numbers, such as tetration [0]; which can be writt

As someone who likes to play around with math, it's "fun" to be able to implement functions that output large numbers, such as tetration [0]; which can be written as: 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 https://en.wikipedia.org/wiki/Tetration

ScottBurson 8y ago
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 :-)
TazeTSchnitzel 8y ago
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
johnhenry 8y ago
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.

ScottBurson 8y ago

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 :-)

TazeTSchnitzel 8y ago

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

johnhenry 8y ago

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.