can multi-core improve single funciton?

Gerhard Weis gerhard at proclos.com
Tue Feb 10 13:41:25 CET 2009


> def fib(n, a=1, b=1):
>     if n==0:
>         return a
>     elif n==1:
>         return b
>     return fib(n-1, b, a+b)
> 
> 
> And for the record:
> 
>>>> fib(500)
> 225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626L
timeit.Timer('fib(500)', 
> 
>>>> 'from __main__ import fib').timeit(1)
> 0.00083398818969726562
> Less than a millisecond, versus millions of years for the OP's algorithm.
> I know which I would choose. Faster hardware can only go so far in hiding
> the effect of poor algorithms.

I agree to 100% to this.

btw. the timeings are not that different for the naive recursion in 
OP's version and yours.
fib(500) on my machine:
	OP's: 0.00116 (far away from millions of years)
	This here: 0.000583
	Gabriel's while loop: 0.000246

The fastest algorithm I've found does fib(1000000) in .25seconds on my machine.
However, I have not found a way to parallelize this algorithm and I 
think it is not possible.

To come back to the original question. Yes it is possible; however 
there are quite some restrictions about it. In case of the naive 
recursion it was possible to get a speedup of more than 3 times on a 4 
core machine. With the highly optimised version mentioned above, I had 
no success in utilizing more than one core.

As conclusion I would say, Yes, a single function can profit from 
multiple cores, but sometimes a better algorithm delivers better 
results than using more cores. However, it is possible that a slower 
but parallelizable algorithm might outperform the best serial 
algorithm, with enough cores :).

Gerhard




More information about the Python-list mailing list