5 ms·
This got me interested in other lisps, as well. Looks like sbcl gives (time (fib 40)) to be about 1.7 seconds on my machine. (Ryzen 5 3600x.) For lulz, I clo
by taeric 6y ago
This got me interested in other lisps, as well. Looks like sbcl gives (time (fib 40)) to be about 1.7 seconds on my machine. (Ryzen 5 3600x.)
For lulz, I clocked a dumb loop version.
(defun fib (n)
(loop repeat n
for a = 1 then b
for b = 1 then c
for c = (+ a b)
finally (return a)))
And... well, serves as an amusing reminder that tree recursion has its downsides. :D
Edit: I confess the speed of the loop got me curious and.... javascript has numeric overflow. That would be a hell of a surprise if you weren't expecting it.
Edit2: (I realize overflow isn't the right term, but it is amusing that I can calc the 10000th fib in elisp... not so much in javascript. And yes, even elisp falls over sooner than sbcl does.)
- eddieh 6y agoTry BigInt in JS https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- taeric 6y agoApologies, I should have acknowledged there are ways to get around that today. My guess is most folks writing javascript are not aware of BigInt. And will only become so when it bites them. Granted, this is also true of fixednum in common lisp. At least "biting you" with that should only be performance. (I can't think of many other ways for that one to get you.) Edit: I should further ack that "getting around" it is as simple as adding "n" to one of the constants. So, it is nicely done.
- eddieh 6y agoI don’t think I’ve seen BigInt in the wild Wild West of JS at all, so that’s probably true that most folks are not aware of it. I wonder if there’s some room for improvement since using GMP is pretty standard for most languages. Edit: forgot to link to a BigInt comparison in major language implementations http://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-in-the-west/ http://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-...
- anthk 6y ago>And... well, serves as an amusing reminder that tree recursion has its downsides. :D OFC I would rewrite that as a iterative form (and any Schemer here could :D), but here we are testing performance :D.
- taeric 6y agoAgreed. I didn't mean that necessarily as a criticism of anything. Just hard to have an intuition for just how much it slows down. I suppose there is a bit of something in there about using the right algorithm. But I can understand picking one that will take time for comparing speed. I'm not sure either is really representative of work you expect an editor to do, though. Curse of benchmarks.
- vitus 6y agoThe speed of the naive recursive fib scales with the number it computes, which is roughly 1.6 ^ n (the eigenvalue of the matrix for the recurrence relation is the golden ratio, phi). Intuition: if you were to expand and flatten the recursive calls, you'd end up with something like (+ 1 0 1 1 0 1 1 0 ... 1 0) with exactly (fib n) 1s (base case (fib 1)), and no more than (fib n) 0s (base case (fib 0)). Simple example: (fib 3) = (+ (fib 2) (fib 1)) = (+ (+ (fib 1) (fib 0)) 1) = (+ (+ 1 0) 1) = (+ 1 0 1)
- taeric 6y agoRight. I "know" how tree recursion scales up. It is still neat to "see" the impact on the speed. That is, knowing all of these facts, it is still impressive how fast you can get (fib 1000000) using iteration and bignums.
- vitus 6y agoThere, that runtime is roughly O(n^2) when dealing with bignums, since addition scales linearly with bit length of the operands, and bit length increases linearly with the number of iterations (~0.7 bits per iteration). Which is still not fast -- on my laptop, Python takes about 9s for fib(1000000). But compared to an exponentially-growing function, that's a blink of an eye.