Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #5374

Re: Recursion or iteration (was Fibonacci series recursion error)

Show all headers | View raw

On May 14, 2:48 am, Mark Dickinson <dicki...@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?

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Recursion or iteration (was Fibonacci series recursion error) Hans Mulder <hansmu@xs4all.nl> - 2011-05-12 00:06 +0200
  Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-13 04:11 -0700
    Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-13 07:55 -0600
    Re: Recursion or iteration (was Fibonacci series recursion error) Hans Mulder <hansmu@xs4all.nl> - 2011-05-13 21:46 +0200
  Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-13 14:48 -0700
    Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-14 10:24 -0700
      Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-14 15:19 -0600
        Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-14 20:32 -0700
          Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-15 12:20 -0700
            Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-15 12:29 -0700

csiph-web