Recursion or iteration (was Fibonacci series recursion error)

[rusi]

On May 14, 2:48 am, Mark Dickinson <dicki... at gmail.com> wrote:

> I don't see this (or Hans' version) as cheating at all.

Yeah sure -- cheating is a strong word :-)

> This really  *is* the power algorithm, just in a different number system from the
> usual one.

Yes that was my point.  If we take the standard logarithmic power algo
as trivial (in the sense that it is well known) then all these
solutions do heavy-lifting to transform fib to power and then use the
'trivial' algo.

A more direct approach would be to use the identities:

f_2n     = f_n ^ 2 + 2*f_n * f_(n-1)
f_(2n-1) = f_n ^ 2 + f_(n-1) ^ 2


The naive python implementation of which is:

def even(n): return n % 2 == 0
def sq(x): return x * x

def fib(n):
    if n==1 or n==2:
        return 1
    elif even(n):
        return sq(fib (n//2)) + 2 * fib(n//2) * fib(n//2 - 1)
    else:
        return sq(fib (n//2 + 1)) + sq(fib(n // 2))

This is a strange algo  -- logarithmic because it halves the n,
exponential because of the double (triple) calls.  [I cannot say I
know how to work out its exact complexity but I would guess its about
linear]

--------------
BTW How do I parse "the ring Z[x] / (x^2 - x - 1)"?
Is this a division ring?