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