Recursion or iteration (was Fibonacci series recursion error)

[Hans Mulder]

On 13/05/2011 13:11, rusi wrote:
> 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.

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