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

Groups > comp.lang.python > #5290

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

Show all headers | View raw

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.

Yet one could argue that this is 'cheating' because you (and I) are
still solving the power problem.

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.

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