can multi-core improve single funciton?

[Nick Craig-Wood]

sturlamolden <sturlamolden at yahoo.no> wrote:
>  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] )

Or something which runs in O(1)...

from gmpy import mpf, mpz, digits
from math import log, sqrt

root5_float = sqrt(5)
phi_float = (1 + root5_float) / 2
log_phi_float = log(phi_float)
log_root5_float = log(root5_float)
log2 = log(2)

def fibonacci_noniterative(n):
    """
    Work out n'th Fibonacci number in an noniterative fashion using Binet's formula
    """
    # Work out magnitude of answer
    bits = int(((n * log_phi_float - log_root5_float) / log2)*1.1)
    if bits < 0:
        bits = 0
    root5 = mpf(5, bits).sqrt()
    phi = (mpf(1, bits) + root5) / mpf(2, bits)
    f_n = phi**n / root5
    f_n = mpz(f_n + mpf(1, bits) / mpf(2, bits))
    return long(f_n)

It runs in O(1) if the O we are talking about is large integer
arithmetic.  It actually runs in more like O(log(n)**1.5) time.  It is
a lot faster than the iterative approach too which runs in
O(log(n)**2) for any n > ~40.

Times to calculate F(n)

         n,  iterative, noniterative
         1,   0.000003,   0.000016
         2,   0.000003,   0.000014
         4,   0.000003,   0.000012
         8,   0.000003,   0.000016
        16,   0.000004,   0.000009
        32,   0.000007,   0.000010
        64,   0.000014,   0.000010
       128,   0.000032,   0.000011
       256,   0.000072,   0.000014
       512,   0.000157,   0.000019
      1024,   0.000361,   0.000031
      2048,   0.000881,   0.000066
      4096,   0.002504,   0.000178
      8192,   0.007640,   0.000521
     16384,   0.025362,   0.001572
     32768,   0.090633,   0.004701
     65536,   0.342724,   0.014132
    131072,   1.335723,   0.045194
    262144,   5.273360,   0.111201
    524288,  20.791205,   0.301488
   1048576,  82.617938,   0.833644

Here is the rest of the program just in case anyone wants to play

def fibonacci_iterative(n):
    """
    Work out n'th Fibonacci number in an iterative fashion
    """
    a, b = 0, 1
    while n > 0:
        a, b = a + b, a
        n -= 1
    return a

if __name__ == "__main__":
    # warmup
    fibonacci_noniterative(100)
    print "         n,  iterative, noniterative"
    for e in range(30):
        i = 2 ** e
        t0 = time()
        f_iterative = fibonacci_iterative(i)
        t_iterative = time() - t0
        t0 = time()
        f_noniterative = fibonacci_noniterative(i)
        t_noniterative = time() - t0
        print "%10d, %10.6f, %10.6f" % (i, t_iterative, t_noniterative)
        if f_iterative != f_noniterative:
            print "Calculation error"
            print "iterative", f_iterative
            print "non iterative", f_noniterative
            print "difference", f_iterative-f_noniterative

-- 
Nick Craig-Wood <nick at craig-wood.com> -- http://www.craig-wood.com/nick