# Python 3 - Fibonacci Implementation

I wrote a function returning the n-th Fibonacci number in Python 3:

# Functions returns the nth Fibonacci number F_n
# Parameters: n >= 0, (Optional: F_0, F_1)
def fibonacci(n, f0=0, f1=1):
if n == 0:
return f0

while n > 1:
f0, f1 = f1, f0 + f1
n -= 1

return f1


Here are a few things I noticed and want to get a review on:

• Is the notation clear? The functions returns the n-th Fibonacci number, but n=0 returns the first Fibonacci number (this is a special case)
• I'm new to Python and any general style guide is welcome.
• Performance: The function isn't intended to be used under incredible performance pressure, but I always try to look what's at the horizon. This implementation should run way faster than an recursive (or even memoized recursive) implementation, but what can be done to improve performance? I tried using the explicit formula including the golden ratio, but accuracy lost in using floating point numbers resulted in wrong return values after some n.
• Dec 20, 2017 at 18:45

• I don't see why you need to special case n == 0. The

def fib(....):
for _ in range(n):
f0, f1 = f1, f0 + f1
return f0


seems cleaner, even though it does one extra addition.

• The Fibonacci are well defined in the negative domain as well. For example, $F_{-1}$ can be derived from the same recurrence ($F_1 = F_0 + F_{-1}$), etc, so handling negative n in this particular problem is a bit trickier.

• Performance wise, yes it is possible to compute the nth number in $O(\log{n})$ time, either by matrix exponentiation, or by exploiting the

$F_{2n-1}=F_{n}^{2}+F_{n-1}^{2}\\F_{2n}=(F_{n-1}+F_{n+1})F_{n}$

identities.

• How could an iterative implementation using the stated identities look like? I just wrote a recursive function using the identities. It was way faster than the previous recursive implementation, but still slower than the normal iterative implementation. Dec 20, 2017 at 1:22
• @user7802048 It is essentially a (matrix) exponentiation by squaring. Compute the path from 1 to n by either doubling, or incrementing by 1. In other words, a binary representation of n.
– vnp
Dec 20, 2017 at 1:24
• Isn't it possible to do without matrix exponentiation, just using the identities above? Dec 20, 2017 at 1:26
• Those identities are awesome! It's the first time I see them. Thanks! Dec 20, 2017 at 10:44
• This question is related. The answer by Paul Hankin I found particularly illuminating. Dec 20, 2017 at 18:43

I've never heard of the identities mentioned by @vnp. Here are different ways to use them.

# Naive, recursive implementation

def recursive_fibonacci(n):
if n < 3:
return [0, 1, 1][n]
elif n % 2 == 0:
m = n // 2
return (recursive_fibonacci(m - 1) + recursive_fibonacci(m + 1)) * recursive_fibonacci(m)
else:
m = (n + 1) // 2
return recursive_fibonacci(m) ** 2 + recursive_fibonacci(m - 1) ** 2


It seems to return the correct result:

>>> recursive_fibonacci(100000) == fibonacci(100000)
True


Note that its performance is horrible compared to the basic iterative approach, though. The goal would be to achieve O(log(n)) complexity by calculating f(n) from f(n//2) but it fails because it uses 2 or 3 recursive calls at each step.

By adding a print(' ' * l + str(n)) line, it's possible to see the steps for f(10):

10
4
1
3
2
1
2
6
2
4
1
3
2
1
2
3
2
1
5
3
2
1
2


# With caching

To avoid calculating the same values again and again, caching can be used:

from functools import lru_cache

@lru_cache(maxsize=1024)
def recursive_fibonacci(n):
if n < 3:
return [0, 1, 1][n]
elif n % 2 == 0:
m = n // 2
return (recursive_fibonacci(m - 1) + recursive_fibonacci(m + 1)) * recursive_fibonacci(m)
else:
m = (n + 1) // 2
return recursive_fibonacci(m) ** 2 + recursive_fibonacci(m - 1) ** 2


Here are the steps for fibonacci(1000):

1000
499
250
124
61
31
16
7
4
1
3
2
9
5
8
15
30
14
6
63
32
17
62
126
64
33
125
249
501
251
500


# Iterative O(log N)

@JamesKPolk mentioned a related question. The linked article describes a recursive O(log N) solution, which calculates two following Fibonacci values at each step.

It's possible to rewrite this method in an iterative way by converting the integer to a list of bits:

def fibonacci(n):
f_n, f_n_plus_1 = 0, 1
for i in range(n.bit_length() - 1, -1, -1):
f_n_squared = f_n * f_n
f_n_plus_1_squared = f_n_plus_1 * f_n_plus_1
f_2n = 2 * f_n * f_n_plus_1 - f_n_squared
f_2n_plus_1 = f_n_squared + f_n_plus_1_squared
if n >> i & 1:
f_n, f_n_plus_1 = f_2n_plus_1, f_2n + f_2n_plus_1
else:
f_n, f_n_plus_1 = f_2n, f_2n_plus_1
return f_n


No caching needed, no recursion and a O(log N) complexity. For n = 1E6, this function requires around 100 ms while the basic approach requires almost 20s.

• Why not use the basic iterative version for n<100 or so? It should be faster, as recursion in python is often slow. Dec 20, 2017 at 19:09
• @OscarSmith: You're right. I updated the answer with an iterative solution. Dec 21, 2017 at 21:53
• Instead of doing both the div and the mod (the // and the %) use the divmod() function Dec 22, 2017 at 6:36
• @Snowbody ahah, you always write the same comment. In this case, it wouldn't be very convenient though, and the method isn't fast anyway. Dec 22, 2017 at 8:23
• @EricDuminil I just learned about it and I think it's a hidden gem of python. Yes I am a little overenthusiastic about it. Dec 22, 2017 at 15:27

If we use Binet's Fibonacci Number Formula then we can speed it up a lot. The formula is $$\dfrac{\Phi^n-(-\Phi)^{-n}}{\sqrt{5}}\text{}$$

import math

sqrt_five = math.sqrt(5)
Phi = (1 + sqrt_five)/2

def n_fibonacci(num):
return int((Phi**num-(-Phi)**-num)/sqrt_five)


NOTE: This will give an approximation for large numbers

• Would it not be better to once-compute math.sqrt(5) at the start, if we are looking to get the most performance, or does it get automatically get cached? Dec 20, 2017 at 9:24
• Good point, I will add it Dec 20, 2017 at 10:09
• It's Fibonacci, not Fibonnacci or Fibonnaci. While it's good to know that this formula exists and is correct in theory, it's already returning wrong values for n=72. Dec 20, 2017 at 10:33
• It is the value of Phi, it loses accuracy the larger the number you are finding Dec 20, 2017 at 12:35
• @EricDuminil that's not it. Once n is large enough the second term is near-zero and has no contribution to the formula. The bigger problem is that the small inaccuracy in Phi due to limited precision gets magnified when exponentiated. Phi is actually off the correct value by sys.float_info.epsilon or so. On my machine Phi is real Phi + around 4e-16 = real Phi*(1+2.45e-16). So n=72 seems about the right place. Dec 22, 2017 at 16:04

Is the notation clear?

No. Do not re-assign parameters.

f0 stands for F_0 But also F_1, F_2, ... etc during different iterations of the loop.

In the same vein, the index of the calculated Fibonacci goes from 1 to n, but n goes from n to 1. It is not obvious which term in the Fibonacci are we calculating in each iteration.

How would you name the function/parameters to be more clear?

A principle of least astonishment implementation could be something along the lines of:

def fibonacci(n, f0=0, f1=1):
f = [0] * (n+1)
f[0], f[1] = f0, f1
for i in range(2, n+1):
f[i] = f[i-1] + f[i-2]
return f[n]


Which is closest to the formal definition you would encounter in a task similar to this.

Still less surprising than the original, but also closer to it:

def fibonacci(n, f0=0, f1=1):
if n == 0:
return f0
curr, prev = f1, f0
while n > 1:
curr, prev = curr + prev, curr
n -= 1

return curr


assuming prev and curr are familiar names to the readers, as i, j are.

• How would you name the function/parameters to be more clear? Dec 20, 2017 at 11:42
• It's hard to imagine a clearer implementation than the one by vnp, which does re-assign parameters. Perhaps the rule should be that you can re-assign parameters if the alternative is to make a variable whose only purpose is to simulate a parameter that you would've assigned to. Or perhaps the rule should be do not re-assign parameters, like you said, but don't be afraid to break the rules sometimes. Dec 20, 2017 at 17:18
• You ought to mention that the [0] * (n+1) uses additional memory in the interests of making the notation clearer. Dec 22, 2017 at 6:36

1. To handle Negative values you can give one more base condition in that method that takes care of it but again if you try to pass any negative values into your method, your method won't break but if will return 1.

2. As long as you have provided comments for this method, then the person reading the method knows what n stands for. But again you can name it more accurately. I learned it the hard way.

3. Your code style looks good to me, no comments on that.

4. I can't think of a faster algorithm than this, only one case that can beat your algorithm is if you have stored all the Fibonacci values into a hashmap, then you can access the nth Fibonacci number in O(1) time.

Hope this helps!

• only one case that can beat your algorithm is... see @vnp's answer for another case that does better than O(n). or the usual closed formula which is another O(1) case. Dec 20, 2017 at 7:48

Another formula I found out about: $$f(n)=[\frac{\phi^n}{\sqrt5}]$$ (square brackets mean rounding to the nearest integer).

from math import sqrt

root_five = sqrt(5)
phi = (root_five + 1) / 2

def fibonacci(n):
return round((phi ** n) / root_five)


Note: only supports the normal fibonacci sequence, use the following function for negative support.

def fibonacci(n):
if n > 0:
return round((phi ** n) / root_five)
elif n % 2:
return round((phi ** -n) / root_five)
else:
return -round((phi ** -n) / root_five)

• Have you tested this? It returns incorrect values for 3,4, and 5. Probably more. Haven't checked. Dec 21, 2017 at 23:42
• Hmm. Taking a look. I got it from here Dec 22, 2017 at 15:23
• Oops, I needed to use round instead of int. Thanks for pointing that out! Dec 22, 2017 at 15:25