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 -- http://mail.python.org/mailman/listinfo/python-list
