How to make Python run as fast (or faster) than Julia

[Steven D'Aprano]

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