sturlamolden <sturlamol...@yahoo.no> wrote:
> On Feb 10, 8:38?am, Paul McGuire <pt...@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 <n...@craig-wood.com> -- http://www.craig-wood.com/nick
--
http://mail.python.org/mailman/listinfo/python-list
