How to make Python run as fast (or faster) than Julia
bartc
bc at freeuk.com
Thu Feb 22 16:05:36 EST 2018
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,
>
> 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
More information about the Python-list
mailing list