can multi-core improve single funciton?

sturlamolden sturlamolden at yahoo.no
Thu Feb 19 01:50:58 CET 2009


On Feb 10, 8:38 am, Paul McGuire <pt... at austin.rr.com> wrote:

> Even worse than linear, the function is recursive, which as I
> understand it, is inherently a no-no when looking for code that is
> parallel-friendly.

There is no way to parallelize Fibonacci numbers computed with linear
time complexity, as we must know fib(n-1) to compute fib(n). But if we
were to use Oyster's recursive version, which has geometric
complexity, one could parallelize with a 'forkjoin' scheme.

Anyhow, this runs in amortized linear time and would be a lot faster:

def fib(n):
   while True:
      try:
         return fib.seq[n]
      except AttributeError:
         fib.seq = [0, 1, 1]
      except IndexError:
         fib.seq.append( fib.seq[-2] +
                          fib.seq[-1] )

S.M.



More information about the Python-list mailing list