5 Replies - 770 Views - Last Post: 11 October 2018 - 06:26 AM

#1 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 223
  • Joined: 05-January 17

Fibonaaci algorithm, two implementations

Posted 03 October 2018 - 05:31 AM

Hi,

I have been learning about the fibonacci sequence. I've been learning about two different implementations of fibonacci, a short program, and a longer, but faster algorithm.

Short, elegant version:
def fib(n): (excuse my pseudocode :))
if n=0 return 0 #since fib(0)=0
if n=1 return 1 #since fib(1)=1
return fib(n-1) + fib(n-2)

The above implementation is fast for up to n=30, however, for n=100 it will crash for a long while before printing the answer.
I understand the above code.

#More complex implementation
def fib(n):
previousFib=0 currentFib=1
if n=0
return 0
elif n=1
return 1
repeat (n-1) times #I don't understand why repeat for n-1 times
newFib=previousFib+currentFib
previousFib=currentFib
currentFib=newFib
return currentFib

I would hugely appreciate, if someone could explain the above implementation. I don't understand it from
the bold line to the end.


Thanks in advance :)

Is This A Good Question/Topic? 0
  • +

Replies To: Fibonaaci algorithm, two implementations

#2 BetaWar   User is online

  • #include "soul.h"
  • member icon

Reputation: 1567
  • View blog
  • Posts: 8,367
  • Joined: 07-September 06

Re: Fibonaaci algorithm, two implementations

Posted 03 October 2018 - 06:17 AM

Lets take a look at the logic all in context and run through a couple of examples to see if that helps with your understanding.

First, I am going to translate the loop of your second example into actual code (C++, though it will be very similar for a number of languages):
for (int i = 0; i < (n - 1); i++)
{
    newFib = previousFib + currentFib;
    previousFib = currentFib;
    currentFib = newFib;
}


For n = 0 and n = 1, we have a set answer of 0 and 1 respectively, so they aren't very interesting examples. Once we get to n = 2, we start to have a bit more interesting logic taking place.

So, running through that loop we have the variables like so at each step:
i = 0
n = 2 (n - 1 = 1)
newFib = previousFib + currentFib = 0 + 1 = 1
previousFib = currentFib = 1
currentFib = newFib = 1

i = 1, which is equal to (n - 1), so the loop ends.

returns 1

---
i = 0
n = 3 (n - 1 = 2)
newFib = previousFib + currentFib = 0 + 1 = 1
previousFib = currentFib = 1
currentFib = newFib = 1

i = 1
n = 3 (n - 1 = 2)
newFib = previousFib + currentFib = 1 + 1 = 2
previousFib = currentFib = 1
currentFib = newFib = 2

i = 2, which is equal to (n - 1), so the loop ends.

returns 2

---
i = 0
n = 4 (n - 1 = 3)
newFib = previousFib + currentFib = 0 + 1 = 1
previousFib = currentFib = 1
currentFib = newFib = 1

i = 1
n = 4 (n - 1 = 3)
newFib = previousFib + currentFib = 1 + 1 = 2
previousFib = currentFib = 1
currentFib = newFib = 2

i = 2
n = 4 (n - 1 = 3)
newFib = previousFib + currentFib = 1 + 2 = 3
previousFib = currentFib = 2
currentFib = newFib = 3

i = 3, which is equal to (n - 1), so the loop ends.

returns 3

That pattern continues as n increases.

Hopefully that makes sense. I am not sure I am conveying it very well...
Was This Post Helpful? 2
  • +
  • -

#3 baavgai   User is online

  • Dreaming Coder
  • member icon


Reputation: 7317
  • View blog
  • Posts: 15,227
  • Joined: 16-October 07

Re: Fibonaaci algorithm, two implementations

Posted 03 October 2018 - 09:00 AM

View PostchloeCodes, on 03 October 2018 - 07:31 AM, said:

Short, elegant version:


Heh, looks like poorly written python. With that in mind:
def fib(n):
    if n==0: return 0 #since fib(0)=0
    if n==1: return 1 #since fib(1)=1
    return fib(n-1) + fib(n-2)

def fib(n):
    previousFib=0
    currentFib=1
    if n==0:
        return 0
    elif n==1:
        return 1
    for _ in range(n-1):
        newFib=previousFib+currentFib
        previousFib=currentFib
        currentFib=newFib
    return currentFib



Actually, you could do the second one a lot cleaner:
def fib2(n):
    if n in (0,1):
        return n
    prior, result = 0,1
    for _ in range(n-1):
        prior, result = result, prior + result
    return result



Now, why is the recursive version slower? Let's put a trace on that puppy:
def fibr_with_trace(n, depth = 0):
    def trace(msg):
        print('-' * depth, " fib({0})".format(n), msg)
    def fib(n2):
        return fibr_with_trace(n2, depth+1)
    if n in (0,1):
        trace("entry exit: " + str(n))
        return n
    trace("entry")
    result = fib(n-1) + fib(n-2)
    trace("exit: " + str(result))
    return result



Some quick results:
  fib(5) entry
-  fib(4) entry
--  fib(3) entry
---  fib(2) entry
----  fib(1) entry exit: 1
----  fib(0) entry exit: 0
---  fib(2) exit: 1
---  fib(1) entry exit: 1
--  fib(3) exit: 2
--  fib(2) entry
---  fib(1) entry exit: 1
---  fib(0) entry exit: 0
--  fib(2) exit: 1
-  fib(4) exit: 3
-  fib(3) entry
--  fib(2) entry
---  fib(1) entry exit: 1
---  fib(0) entry exit: 0
--  fib(2) exit: 1
--  fib(1) entry exit: 1
-  fib(3) exit: 2
  fib(5) exit: 5



Notice that event though we've calculated fib(2) before, we still keep calculating it. There are languages that are more clever about recursion and use something called memoization to cache results, though that, of course, has its own issues. In a standard imperative language, you just calc again. Also, each call has overhead, so it's not just the extra calculations but the management of memory that will slow you down.

Now, let's trace the non recursive version:
def fib_trace(n):
    if n in (0,1):
        return n
    prior, result = 0,1
    for _ in range(n-1):
        print("fib: {0},{1}".format(prior, result))
        prior, result = result, prior + result
    print("fib: {0},{1}".format(prior, result))
    return result



Result:
fib: 0,1
fib: 1,1
fib: 1,2
fib: 2,3
fib: 3,5



This is basically the difference between a linear progression versus a geometric one.

If you don't understand how values are moving around it is always a nice idea to fire up your language of choice and make it tell you what is going on.

Hope this helps.
Was This Post Helpful? 2
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12399
  • View blog
  • Posts: 45,538
  • Joined: 27-December 08

Re: Fibonaaci algorithm, two implementations

Posted 03 October 2018 - 03:48 PM

Both baavgai and BetaWar did an excellent job illustrating the intuition regarding why Version 2 is more efficient. Let's analyze each version more formally..

Version 1). Let T(n) denote the time complexity of the algorithm. Note that you recursively invoke the function fib(n-1) and fib(n-2). So T(n) = T(n-1) + T(n-2). Our base cases are T(0) = 0 and T(1) = 1. Solving the recurrence, we obtain that T(n) = O( ( (1+sqrt(5))/2 )^n ), which is exponential time.

Version 2) The loop takes a constant number of steps per iteration. There are n iterations. So T(n) = O(n), which is linear time (and far more efficient).

Based on my tutorial, you can actually compute the nth Fibonacci number in a constant number of steps (O(1) time), without computing the previous Fibonacci numbers. My tutorial demonstrates how to derive this formula.
Was This Post Helpful? 0
  • +
  • -

#5 MentalFloss   User is online

  • .
  • member icon

Reputation: 601
  • View blog
  • Posts: 1,566
  • Joined: 02-September 09

Re: Fibonaaci algorithm, two implementations

Posted 03 October 2018 - 07:08 PM

And if you want to explore the Fibonacci sequence further, there's the Mathologer on youtube: https://www.youtube....h?v=e7SnRPubg-g

Very cool stuff.
Was This Post Helpful? 1
  • +
  • -

#6 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 223
  • Joined: 05-January 17

Re: Fibonaaci algorithm, two implementations

Posted 11 October 2018 - 06:26 AM

View PostBetaWar, on 03 October 2018 - 06:17 AM, said:

<Snip>


I can't thank you enough for such a detailed, clear explanation. I was just wondering why previousFib=0 and currentFib=1 is assumed at the beginning of the algorithm.

This post has been edited by macosxnerd101: 11 October 2018 - 06:44 AM
Reason for edit:: Please avoid quoting large posts

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1