can multi-core improve single funciton?

[Steven D'Aprano]

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.



-- 
Steven