On May 11, 11:06 pm, 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,
> )
> [...]
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
--
http://mail.python.org/mailman/listinfo/python-list
