Recursion or iteration (was Fibonacci series recursion error)

[Mark Dickinson]

On May 11, 11:06 pm, Hans Mulder <han... at xs4all.nl> wrote:
> 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,
> )
> [...]

You can even get away with pairs rather than triples:

----

from collections import namedtuple

Pair = namedtuple('Pair', 'z o')
Pair.__mul__ = lambda self, other: Pair(
    self.z * other.z + self.o * other.o,
    self.z * other.o + self.o * other.z + self.o * other.o,
)

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

----

I don't see this (or Hans' version) as cheating at all.  This really
*is* the power algorithm, just in a different number system from the
usual one.  For those with a bit of abstract algebra, the above
algorithm is just computing x^n in the ring Z[x] / (x^2 - x - 1).  A
pair 'Pair(a, b)' represents the element 'a + bx' (more precisely, the
image of 'a + bx' under the natural quotient map Z[x] -> Z[x] / (x^2 -
x - 1)) of that ring.  And this *can* be generalised to other
sequences given by a linear recurrence.

Mark