can multi-core improve single funciton?

[Lie Ryan]

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?
> 
> and more, can threads/multi-processors/clusters be used to improve fib?
> 
> thanx

Of course multi-core processor can improve single function using 
multiprocessing, as long as the function is parallelizable. The Fibonacci 
function is not a parallelizable function though.

However, there are ways to improve your fibonacci function. Either put 
off the recursion or implement a memoization. An imperative fibonacci is 
much faster than a naive recursion one because a naive recursive 
fibonacci function is O(2**n) while the imperative one O(n). Memoization 
must be used to help recursive fibonacci to become O(n).