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

[Ian Kelly]

On Thu, Feb 22, 2018 at 12:55 PM, Jack Fearnley <jack at alcor.concordia.ca> 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.

To be pedantic, that's not really true; see below.

> GP/Pari on my Intel I7 computes fibonacci(100000) in less than 1 ms,
> fibonacci(1000000) in 5ms, fibonacci(10000000) in 59 ms and finally
> fibonacci(100000000) in 733 ms.

I'm not sure exactly what algorithm that's using, but note that the
growth of these timings is *not* logarithmic. In fact, it's
superlinear.

It's true can generate Fibonacci numbers in log(n) iterations using
linear algebra. As long as multiplication and addition are assumed to
be constant time, then the Fibonacci algorithm is indeed O(log n)
time. However, the numbers in the sequence grow on the order of O(phi
** n) which quickly exceeds what you can fit into a 32-bit integer.
Therefore bigints are quickly required.

The fastest known integer multiplication algorithm is O(n * log n *
log log n). The Fibonacci numbers grow at O(phi ** n) and therefore
require O(log (phi ** n)) = O(n) bits to represent them. Each
iteration therefore requires O(n * log n * log log n) time, and with
O(log n) iterations the total time of the algorithm is thus O(n * (log
n) ** 2 * log log n).

It's still a lot faster than the brute force approach, and aeons
faster than the brute-force recursive approach, but it's not strictly
logarithmic because that part of the analysis is dwarfed by the cost
of the arithmetic involved.