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

Groups > comp.lang.python > #4336 > unrolled thread

Fibonacci series recursion error

Back to article view | Back to comp.lang.python

Contents

  Fibonacci series recursion error lalit <opposite800@gmail.com> - 2011-04-29 20:22 -0700
    Re: Fibonacci series recursion error Gary Herron <gherron@islandtraining.com> - 2011-04-29 20:41 -0700
    Re: Fibonacci series recursion error Jason Friedman <jason@powerpull.net> - 2011-04-30 03:57 +0000
    Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:45 -0500
      Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:51 -0500
        Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:31 -0500
          Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:14 +0200
            Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 00:08 -0700
      Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-04-30 06:50 +0100
      Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 06:43 +0100
    Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-04-29 23:27 -0600
      Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:35 -0500
        Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:32 +0200
          Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-04-30 16:37 +1000
        Re: Fibonacci series recursion error Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2011-04-30 11:37 +0200
          Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-02 16:50 -0500
            Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:17 +1000
              Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-03 12:10 -0500
                Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 07:41 +1000
                Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-03 16:31 -0600
                Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 09:09 +1000
            Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 16:22 -0600
            Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:42 +1000
            Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-02 18:48 -0700
              Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 12:13 +1000
              Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 15:29 +1000
                Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 00:52 -0700
                  Re: Recursion or iteration (was Fibonacci series recursion error) Dave Angel <davea@ieee.org> - 2011-05-03 06:32 -0400
                    Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 03:51 -0700
                  Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 21:04 +1000
                    Re: Recursion or iteration (was Fibonacci series recursion error) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 12:49 +0000
                      Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 23:02 +1000
                  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
              Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 23:46 -0600

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#4587

On Wed, May 4, 2011 at 8:31 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> A back-of-the-envelope calculation
> shows that with modern technology it would take more than 10 ** 257
> years to complete.

Then I propose that Python be extended to allow for underlying
hardware upgrades without terminating a script. This will be essential
to the finding of answers to these vital questions.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4507

On Mon, May 2, 2011 at 3:50 PM, harrismh777 <harrismh777@charter.net> wrote:
> Thomas Rachel wrote:
>>>
>>> ... because each recursion level 'return' calls fib() twice, and each of
>>> those calls fib() twice, and you get the point...
>>
>> yes - but they are called one after the other, so the "twice" call
>> counts only for execution speed, not for recursion depth.
>
>>>> def fib(n):
>>>>     if n == 1:
>>>>         return(n)
>>>>     else:
>>>>         return (fib(n-1)+fib(n-2))
>
> They *are not* called one after the other in the sense that there is ever
> only one level of recursion with each call (not at all). Take a closer look.
> Each call to fib() forces a double head, and each of those forces another
> double head (now four), and so on...

The branching factor has nothing to do with the maximum stack depth.
If you don't believe me, consider this little script:

import inspect
def maxstack(n):
    if n <= 0:
        return len(inspect.stack())
    else:
        return max(maxstack(n-1), maxstack(n-2))
print maxstack(15)

This prints "17".

Now consider this script, which is similar but singly-recursive:

import inspect
def maxstack(n):
    if n <= 0:
        return len(inspect.stack())
    else:
        return maxstack(n-1)
print maxstack(15)

This also prints "17".  Note: they're the same.

>  the recursion depth exception of the
> OP testifies against your theory.

The OP's recursion depth exception was because a malformed base case
made the recursion infinite.  It had nothing to do with the branching
factor.

[toc] | [prev] | [next] | [standalone]

#4508

On Tue, May 3, 2011 at 8:22 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> They *are not* called one after the other in the sense that there is ever
>> only one level of recursion with each call (not at all). Take a closer look.
>> Each call to fib() forces a double head, and each of those forces another
>> double head (now four), and so on...
>
> The branching factor has nothing to do with the maximum stack depth.
>

Side point: In a massively parallel environment, branching like this
COULD be implemented as a fork. I just don't know of any
implementations of Python that do so. (And of course, it works for
fib() because it needs/uses no global state, which makes the
recursions completely independent. Not all functions are so courteous,
and the compiler can't necessarily know the difference.)

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4513 — Recursion or iteration (was Fibonacci series recursion error)

On May 3, 2:50 am, harrismh777 <harrismh...@charter.net> wrote:
> The thing about this problem that puzzles me, is why we might consider
> recursion for a possible solution in the first place....

This can be answered directly but a bit lengthily.
Instead let me ask a seemingly unrelated (but actually much the same)
question.

Here are two power functions:

def powI(x,n):
    result = 1
    for i in range(0,n):
        result = result * x
    return result

def powR(x,n): return 1 if (n==0) else (x * powR(x, n-1))

What are their space/time complexities?
Which do you prefer?

[toc] | [prev] | [next] | [standalone]

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

On Tue, May 3, 2011 at 11:48 AM, rusi <rustompmody@gmail.com> wrote:
> What are their space/time complexities?
> Which do you prefer?

They're pretty similar actually. If you rework the first one to not
use range() but instead have a more classic C style of loop, they'll
be almost identical:

def powI(x,n):
   result = 1
   while n > 0:
       result *= x
       n-=1
   return result

There's a subtle difference in that powR as you've coded it will
infinite-loop if given a negative exponent, while powI in any form
will simply return 1 (neither is technically correct, fwiw). Other
than that, the only difference is that one keeps its state on the call
stack, the other uses a temporary variable.

Performance would probably benefit from a special syntax meaning
"recurse", which would avoid the LOAD_GLOBAL for the function's name
(plus, things break if you pass recursive functions around after
compiling them - for instance, powR2=powR; def powR(x,n): os.exit() -
but if you do that, then you should expect to see nice bullet-holes in
your foot). However, I do not believe that Python would overall
benefit from any such thing.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

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

On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg <drsalists@gmail.com> wrote:
>
> But the recursive solution has time complexity of O(logn).  The iterative
> solution has time complexity of O(n).  That's a significant difference for
> large n - a significant benefit of the recursive version.

Are you sure? It will produce n function calls and n multiplications,
how is that O(log n)?

Chris Angelico

[toc] | [prev] | [next] | [standalone]

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

On May 3, 10:29 am, Chris Angelico <ros...@gmail.com> wrote:
> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg <drsali...@gmail.com> wrote:
> Doh.

> Usually when someone gives a recursive solution to this problem, it's
> O(logn), but not this time.

> Here's a logn one:

:-) Ok so you beat me to it :D

I was trying to arrive at an answer to the question (by M Harris)
about why anyone would do something like fib recursively. I used power
since that illustrates the case more easily, viz:
A trivial power -- recursive or iterative -- is linear time -- O(n)
A more clever power can be O(log(n))
This more clever power can be trivially derived from the recursive one
as follows:

The recursive O(n) function:
def powR(x,n): return 1 if (n==0) else (x * powR(x, n-1))

is just python syntax for the school algebra (or Haskell) equations:

x^0 = 1
x^(n+1) = x * x^n

Adding one more equation:
x^(2*n) = (x^2)^n = (x*x)^n
Re-python-ifying we get:


def pow(x,n):
    return 1 if (n==0) else pow(x*x, n/2) if even(n) else x*pow(x,n-1)

def even(n): return n % 2 == 0

Can this be done iteratively? Of course but its not so trivial.

[If you believe it is, then try writing a log(n) fib iteratively :D ]

[toc] | [prev] | [next] | [standalone]

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

On 01/-10/-28163 02:59 PM, rusi wrote:
> On May 3, 10:29 am, Chris Angelico<ros...@gmail.com>  wrote:
>> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg<drsali...@gmail.com>  wrote:
>> Doh.
>
>> Usually when someone gives a recursive solution to this problem, it's
>> O(logn), but not this time.
>
>> Here's a logn one:
>
> :-) Ok so you beat me to it :D
>
> I was trying to arrive at an answer to the question (by M Harris)
> about why anyone would do something like fib recursively. I used power
> since that illustrates the case more easily, viz:
> A trivial power -- recursive or iterative -- is linear time -- O(n)
> A more clever power can be O(log(n))
> This more clever power can be trivially derived from the recursive one
> as follows:
>
> The recursive O(n) function:
> def powR(x,n): return 1 if (n=) else (x * powR(x, n-1))
>
> is just python syntax for the school algebra (or Haskell) equations:
>
> x^0 =
> x^(n+1) =  * x^n
>
> Adding one more equation:
> x^(2*n) =x^2)^n = (x*x)^n
> Re-python-ifying we get:
>
>
> def pow(x,n):
>      return 1 if (n=) else pow(x*x, n/2) if even(n) else x*pow(x,n-1)
>
> def even(n): return n % 2 =0
>
> Can this be done iteratively? Of course but its not so trivial.
>
> [If you believe it is, then try writing a log(n) fib iteratively :D ]
>

What I'm surprised at is that nobody has pointed out that the logn 
version is also generally more accurate, given traditional floats. 
Usually getting the answer accurate (given the constraints of finite 
precision intermediates) is more important than performance, but in this 
case they go hand in hand.

DaveA

[toc] | [prev] | [next] | [standalone]

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

On May 3, 3:32 pm, Dave Angel <da...@ieee.org> wrote:

> What I'm surprised at is that nobody has pointed out that the logn
> version is also generally more accurate, given traditional floats.
> Usually getting the answer accurate (given the constraints of finite
> precision intermediates) is more important than performance, but in this
> case they go hand in hand.

Well!!
That's a slant that I was not aware of -- though fairly obvious on
second thought.

Thanks Dave.

[toc] | [prev] | [next] | [standalone]

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

On Tue, May 3, 2011 at 8:32 PM, Dave Angel <davea@ieee.org> wrote:
> What I'm surprised at is that nobody has pointed out that the logn version
> is also generally more accurate, given traditional floats. Usually getting
> the answer accurate (given the constraints of finite precision
> intermediates) is more important than performance, but in this case they go
> hand in hand.

And that, Your Honour, is why I prefer bignums (especially for
integers) to floating point. Precision rather than performance.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

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

On Tue, 03 May 2011 21:04:07 +1000, Chris Angelico wrote:

> And that, Your Honour, is why I prefer bignums (especially for integers)
> to floating point. Precision rather than performance.

I'm intrigued by your comment "especially for integers", which implies 
that you might use bignums for non-integers. Out of curiosity, how would 
you calculate:

sin(sqrt(7)*pi/31)

using bignums?



-- 
Steven

[toc] | [prev] | [next] | [standalone]

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

On Tue, May 3, 2011 at 10:49 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Tue, 03 May 2011 21:04:07 +1000, Chris Angelico wrote:
>
>> And that, Your Honour, is why I prefer bignums (especially for integers)
>> to floating point. Precision rather than performance.
>
> I'm intrigued by your comment "especially for integers", which implies
> that you might use bignums for non-integers. Out of curiosity, how would
> you calculate:
>
> sin(sqrt(7)*pi/31)
>
> using bignums?

REXX uses decimal bignums, although I don't have a high-performance
math library (for sin) that uses anything more than IEEE double
precision. If I coded my own sin algorithm in REXX, I could go to
whatever precision memory (and patience) would allow.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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.

[toc] | [prev] | [next] | [standalone]

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

On Fri, May 13, 2011 at 5:11 AM, rusi <rustompmody@gmail.com> wrote:
> 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.

Oh, nice!  I did it this way once:

V = [0 1]

M =
[0 1]
[1 1]

fib(n) = (V * M ** n)[0]

Since I viewed M as operating on V, it never occurred to me that
multiplying by V is actually unnecessary, but it is obvious in
retrospect.  I think it's just a fortuitous coincidence that it works,
since V sets up the base case and M describes the recursive case.  For
a FIbonacci sequence starting with any other pair of numbers, V would
change, but M would not, and so V would no longer happen to be
identical to the top row of M.

Ian

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

On May 11, 11:06 pm, 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,
> )
> [...]

You can even get away with pairs rather than triples:

----

from collections import namedtuple

Pair = namedtuple('Pair', 'z o')
Pair.__mul__ = lambda self, other: Pair(
    self.z * other.z + self.o * other.o,
    self.z * other.o + self.o * other.z + self.o * other.o,
)

def fib(n):
     f = Pair(0, 1)
     a = Pair(1, 0)
     while n:
         if n & 1:
             a *= f
         f *= f
         n >>= 1
     return a.o

----

I don't see this (or Hans' version) as cheating at all.  This really
*is* the power algorithm, just in a different number system from the
usual one.  For those with a bit of abstract algebra, the above
algorithm is just computing x^n in the ring Z[x] / (x^2 - x - 1).  A
pair 'Pair(a, b)' represents the element 'a + bx' (more precisely, the
image of 'a + bx' under the natural quotient map Z[x] -> Z[x] / (x^2 -
x - 1)) of that ring.  And this *can* be generalised to other
sequences given by a linear recurrence.

Mark

[toc] | [prev] | [next] | [standalone]

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

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?

[toc] | [prev] | [next] | [standalone]

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

On Sat, May 14, 2011 at 11:24 AM, rusi <rustompmody@gmail.com> wrote:
> 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]

Yup, linear.  Assuming you optimize the even case so that it doesn't
actually call fib(n//2) twice, the call tree can be approximated as a
balanced binary tree with height log(n).  The total number of nodes in
the tree is thus O(2 ** log(n)) = O(n).

[toc] | [prev] | [next] | [standalone]

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

On May 15, 2:19 am, Ian Kelly <ian.g.ke...@gmail.com> wrote:
> On Sat, May 14, 2011 at 11:24 AM, rusi <rustompm...@gmail.com> wrote:
> > 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]
>
> Yup, linear.  Assuming you optimize the even case so that it doesn't
> actually call fib(n//2) twice, the call tree can be approximated as a
> balanced binary tree with height log(n).  The total number of nodes in
> the tree is thus O(2 ** log(n)) = O(n).

It would be linear if the base of the log were 2.
I am not sure it is.
You see the naive fib has a complexity which is fib itself. [Earlier
discussion with Steven]
fib is exponential but with radix < 2 [phi = (1 + sqrt(5))/2 ]
This would suggest that this algo is slightly better than linear.

But I have no idea of the exact complexity.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.python

csiph-web