2 ms·
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
by 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 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.