Page 1 of 1

# 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 Reputation: 1647
• Posts: 8,510
• 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...

### #3 baavgai • • Dreaming Coder
•   Reputation: 7505
• Posts: 15,553
• Joined: 16-October 07

## Re: Fibonaaci algorithm, two implementations

Posted 03 October 2018 - 09:00 AM chloeCodes, 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.

### #4 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,863
• 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.

### #5 MentalFloss Reputation: 619
• Posts: 1,590
• 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.

## Re: Fibonaaci algorithm, two implementations

Posted 11 October 2018 - 06:26 AM BetaWar, 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

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }