OFC I would rewrite that as a iterative form (and any Schemer here could :D), but here we are testing performance :D.
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.
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) With scm, using (trace proc):
scm -f fib.scm
call fib 9
call fib 8
call fib 7
call fib 6
call fib 5
retn fib 5
call fib 4
retn fib 3
retn fib 8
call fib 5
call fib 4
retn fib 3
call fib 3
retn fib 2
retn fib 5
retn fib 13
call fib 6
call fib 5
call fib 4
retn fib 3
call fib 3
retn fib 2
retn fib 5
call fib 4
call fib 3
retn fib 2
call fib 2
retn fib 1
retn fib 3
retn fib 8
retn fib 21
call fib 7
call fib 6
call fib 5
call fib 4
retn fib 3
call fib 3
retn fib 2
retn fib 5
call fib 4
call fib 3
retn fib 2
call fib 2
retn fib 1
retn fib 3
retn fib 8
call fib 5
call fib 4
call fib 3
retn fib 2
call fib 2
retn fib 1
retn fib 3
call fib 3
call fib 2
retn fib 1
call fib 1
retn fib 1
retn fib 2
retn fib 5
retn fib 13
retn fib 34
call fib 8
call fib 7
call fib 6
call fib 5
call fib 4
retn fib 3
call fib 3
retn fib 2
retn fib 5
call fib 4
call fib 3
retn fib 2
call fib 2
retn fib 1
retn fib 3
retn fib 8
call fib 5
call fib 4
call fib 3
retn fib 2
call fib 2
retn fib 1
retn fib 3
call fib 3
call fib 2
retn fib 1
call fib 1
retn fib 1
retn fib 2
retn fib 5
retn fib 13
call fib 6
call fib 5
call fib 4
call fib 3
retn fib 2
call fib 2
retn fib 1
retn fib 3
call fib 3
call fib 2
retn fib 1
call fib 1
retn fib 1
retn fib 2
retn fib 5
call fib 4
call fib 3
call fib 2
retn fib 1
call fib 1
retn fib 1
retn fib 2
call fib 2
call fib 1
retn fib 1
call fib 0
retn fib 0
retn fib 1
retn fib 3
retn fib 8
retn fib 21
55
scm -f fib-iter.scm
call fib-iter 1 0 10
call fib-iter 1 1 9
call fib-iter 2 1 8
call fib-iter 3 2 7
call fib-iter 5 3 6
retn fib-iter 55
retn fib-iter 55
retn fib-iter 55
retn fib-iter 55
retn fib-iter 55
55That is, knowing all of these facts, it is still impressive how fast you can get (fib 1000000) using iteration and bignums.
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.
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.
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-...
For lulz, I clocked a dumb loop version.
And... well, serves as an amusing reminder that tree recursion has its downsides. :DEdit: 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.)