On May 12, 3:06 am, Hans Mulder <han...@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.
--
http://mail.python.org/mailman/listinfo/python-list
