On Thu, 22 Feb 2018 19:55:08 +0000, Jack Fearnley wrote:
> I realize that this thread is about benchmarking and not really about
> generating fibonacci numbers, but I hope nobody is using this code to
> generate them on a 'production' basis,
>
> Fibonacci numbers, any linearly recursive sequence for that matter, can
> be generated in log time.
That is not what your timing results show. Your timing results are
*worse* than linear, not better. In fact, they look more like N log N:
N Your time ∝ N ∝ log N ∝ N log N
(-actual-) (----------predicted---------)
100000 <1? 0.5 4.2 0.4
1000000 5 5 5.0 5.0
10000000 59 50 5.8 58.3
100000000 733 500 6.7 666.7
1000000000 ? 5000 7.5 7500.0
I don't know what algorithm your version of Fibonacci is using, but if it
is the one which uses matrix multiplication, then it is logarithmic in
the number of *steps*, but each step doesn't take constant time. As the
numbers involved get larger, the cost of each multiplication and addition
becomes higher.
Big O analysis is never a substitute for actual timing measurements, and
the assumption behind Big O analysis, namely that only some operations
take time, and always constant time, is never correct. It is only an
approximation to the truth, and as you can see, something which is
algorithmically Big O logarithmic can turn out to scale worse than
linearly once you actually measure the times.
--
Steve
--
https://mail.python.org/mailman/listinfo/python-list
