On 13/05/2011 13:11, rusi wrote:
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.
My method is just a thinly disguised version of your method: your 2x2
matrices are symmetrical, i.e. the number in the upper right is equal
to the number in the lower left. So I can save some memory and some
CPU time by working with only three numbers.
Yet one could argue that this is 'cheating' because you (and I) are
still solving the power problem.
That's true.
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.
To compute f(4n) this way, you need to compute both f(2n) and f(2n+1)
first, and to compute those, you need f(n) and f(n+1) and f(n+2)....
I think I can construct an O(log(n)**2) algorithm this way.
And it would still be 'cheating', because we'd still use some special
property of the Fibonacci sequence to reduce our problem to the power
problem. I think this sort of cheating can't be avoided: there is no
general method to compute recurrent sequences faster than O(n);
Fibonacci is just a special case.
-- HansM
--
http://mail.python.org/mailman/listinfo/python-list
