can multi-core improve single funciton?

[Gerhard Weis]

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 
<steven at 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.