3 ms·

The 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 t

by vitus 6y ago

The 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 ago
Right. 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 ago
  There, 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.
anthk 6y ago
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 55

by vitus 6y ago

taeric 6y ago

Right. 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 ago
There, 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.

anthk 6y ago

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 55