On 22/02/2018 19:55, 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,## Advertising

Fibonacci numbers, any linearly recursive sequence for that matter, can be generated in log time. GP/Pari on my Intel I7 computes fibonacci(100000) in less than 1 ms, fibonacci(1000000) in 5ms,

`The simple method involves 1 million additions of numbers with an`

`average length of 100,000 digits. 5ms would be pretty good going.`

`Presumably it uses a faster algorithm. I found this in Python (from`

`stackoverflow):`

def fib(n): v1, v2, v3 = 1, 1, 0 # initialise a matrix [[1,1],[1,0]] print (bin(n)[3:]) for rec in bin(n)[3:]: # perform fast exponentiation of the .... calc = v2*v2 v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3 if rec=='1': v1, v2, v3 = v1+v2, v1, v2 return v2

`fib(1000000) took 200ms seconds in Python 3. Printing the result about`

`another 1.6 seconds. I think now it's down to the efficiency of the big`

`integer library, as little bytecode is being executed.`

-- bartc -- https://mail.python.org/mailman/listinfo/python-list