Recursion or iteration (was Fibonacci series recursion error)

[rusi]

On May 12, 3:06 am, 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,
> )
>
> 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

Bravo! Can you explain this?

The tightest way I knew so far was this:
The 2x2 matrix
0 1
1 1
raised to the nth power gives the nth fibonacci number. [And then use
a logarithmic matrix mult]
Your version is probably tighter than this.

Yet one could argue that this is 'cheating' because you (and I) are
still solving the power problem.

What I had in mind was to use fib results like:
f_(2n) = f_n^2 + f_(n+1)^2
and use these in the same way (from  first principles) like we use the
equation
x^2n = (x*x)^n
to arrive at a logarithmic power algo.