Recursion or iteration (was Fibonacci series recursion error)

[Hans Mulder]

On 03/05/2011 09:52, rusi wrote:

> [If you believe it is, then try writing a log(n) fib iteratively :D ]

It took me a while, but this one seems to work:

from collections import namedtuple

Triple = namedtuple('Triple', 'hi mid lo')
Triple.__mul__ = lambda self, other: Triple(
     self.hi * other.hi + self.mid * other.mid,
     self.hi * other.mid + self.mid * other.lo,
     self.mid * other.mid + self.lo * other.lo,
)

def fib(n):
     f = Triple(1, 1, 0)
     a = Triple(1, 0, 1)
     while n:
         if n & 1:
             a *= f
         f *= f
         n >>= 1
     return a.mid


-- HansM