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:
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__
On 2009-02-11 08:01:29 +1000, Steven D'Aprano
ste...@remove.this.cybersource.com.au said:
On Tue, 10 Feb 2009 22:41:25 +1000, Gerhard Weis wrote:
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