## Improved Fibonacci routine

Expand Messages
• Thanks to Phil s hint, I have improved my FibonacciMod routine. My previous routine, using recursion, was inefficient. I see now that the recursion routine
Message 1 of 1 , Mar 25, 2008
Thanks to Phil's hint, I have improved my FibonacciMod routine.

My previous routine, using recursion, was inefficient.

I see now that the recursion routine calculates the same Fibonacci
values many times.

This improved routine calculates each Fibonacci value on the binary

def FibonacciMod(n,z=0):

### Function is based on the identity f_(n + m + 1) = f_n * f_m +
f_(n+1) * f_(m+1)

#{
if z == 0:
#{
v = Fibonacci(n)
return v
#}
if n < 1:
#{
return 0
#}
if n < 3:
#{
return 1
#}

##### Get binary sequence

listbin = []
mm = n + 0
while mm > 1:
#{
listbin.append(mm)
mm = mm//2
#}

lenmm = len(listbin)
p0 = 0
p1 = 1
Fib0 = 0
Fib1 = 1
while lenmm > 0:
#{
lenmm = lenmm - 1
target = listbin[lenmm]

if target == p0 + p1 + 1:
#{
Fibnext0 = (Fib0 * Fib0 + Fib1 * Fib1)%z
Fib2 = (Fib0 + Fib1)%z
Fibnext1 = (Fib0 * Fib1 + Fib1 * Fib2)%z
p0 = target - 1
p1 = target + 0
Fib0 = Fibnext0 + 0
Fib1 = Fibnext1 + 0

continue
#}

if target == 2 * p1 + 1:
#{
Fib2 = (Fib0 + Fib1)%z
Fibnext0 = (Fib0 * Fib1 + Fib1 * Fib2)%z
Fibnext1 = (Fib1 * Fib1 + Fib2 * Fib2)%z
p0 = target - 1
p1 = target + 0
Fib0 = Fibnext0 + 0
Fib1 = Fibnext1 + 0
continue
#}

#}
return Fib1
#}
Your message has been successfully submitted and would be delivered to recipients shortly.