# can multi-core improve single funciton?

Steven D'Aprano steven at REMOVE.THIS.cybersource.com.au
Tue Feb 10 09:45:37 CET 2009

```On Tue, 10 Feb 2009 18:18:23 +1000, Gerhard Weis wrote:

> Once I have seen Haskell code, that ran fibonacci on a 4 core system.
>
> The algorithm itself basically used an extra granularity paramet until
> which new threads will be sparked. e.g. fib(40, 36) means, calculate
> fib(40) and spark threads until n=36. 1. divide: fib(n-1), fib(n-2)
> 2. divide: fib(n-2), fib(n-3)
> 3. divide: fib(n-3), fib(n-4)
>
> We tried this code on a 4 core machine using only 1 core and all 4
> cores. 1 core wallclock: ~10s
> 4 core wallclock: ~3s

Three seconds to calculate fib(40) is terrible. Well, it's a great saving
over ten seconds, but it's still horribly, horribly slow.

Check this out, on a two-core 2.2 GHz system:

>>> import timeit
>>> timeit.Timer('fib(40)', 'from __main__ import fib').timeit(1)
7.2956085205078125e-05

That's five orders of magnitude faster. How did I do it? I used a better
algorithm.

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.

--
Steven

```