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
So there is a signifcant speedup, but I guess, this only works with
Haskell out of the box.
I have not tried it, but I think you can simulate Haskell's behaviour,
by caching the results of fib(n).
(We tried the same algorithm in Java. While it utilized all 4 cores,
there was no speedup. This is why I think, that result caching is the
only way to speedup fibonacci.
cheers
Gerhard
On 2009-02-10 17:34:54 +1000, Steven D'Aprano
<ste...@remove.this.cybersource.com.au> said:
On Tue, 10 Feb 2009 14:28:15 +0800, oyster wrote:
I mean this
[code]
def fib(n):
if n<=1:
return 1
return fib(n-1)+fib(n-2)
useCore(1)
timeit(fib(500)) #this show 20 seconds
useCore(2)
timeit(fib(500)) #this show 10 seconds [/code]
Is it possible?
What does useCore(n) mean?
and more, can threads/multi-processors/clusters be used to improve fib?
No. The best way to improve fib is to improve fib, not to try running it
on faster hardware.
Your algorithm makes *many* recursive calls to fib() for each call:
fib(1) => 1 function call
fib(2) => 3 function calls
fib(3) => 5 function calls
fib(4) => 9 function calls
fib(5) => 15 function calls
fib(6) => 25 function calls
fib(7) => 41 function calls
fib(8) => 67 function calls
fib(9) => 109 function calls
...
fib(34) => 18454929 function calls
fib(35) => 29860703 function calls
fib(36) => 48315633 function calls
...
fib(498) => 1.723e+104 function calls
fib(499) => 2.788e+104 function calls
fib(500) => 4.511e+104 function calls
Calling fib(500) the way you do will make more than 450 thousand billion
billion billion billion billion billion billion billion billion billion
billion function calls. You claim that you calculated it in just 20
seconds. On my PC, it takes over a minute to calculate fib(38). I
estimate it would take over five hours to calculate fib(50), and fib(100)
would probably take 16 million years. I call shenanigans.
--
http://mail.python.org/mailman/listinfo/python-list
