Python 3 - Fibonacci Implementation

Question

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.

• President James K. Polk: See also Applying Fibonacci Fast Doubling Identities

Answer 1

• 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.

• user7802048: 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.
• vnp: @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.
• user7802048: Isn't it possible to do without matrix exponentiation, just using the identities above?
• Eric Duminil: Those identities are awesome! It's the first time I see them. Thanks!
• President James K. Polk: This question is related. The answer by Paul Hankin I found particularly illuminating.

Answer 2

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.

• Oscar Smith: Why not use the basic iterative version for n<100 or so? It should be faster, as recursion in python is often slow.
• Eric Duminil: @OscarSmith: You're right. I updated the answer with an iterative solution.
• Snowbody: Instead of doing both the div and the mod (the // and the %) use the divmod() function
• Eric Duminil: @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.
• Snowbody: @EricDuminil I just learned about it and I think it's a hidden gem of python. Yes I am a little overenthusiastic about it.

Answer 3

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

• Ziyad Edher: 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?
• 13ros27: Good point, I will add it
• Eric Duminil: 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.
• 13ros27: It is the value of Phi, it loses accuracy the larger the number you are finding
• Snowbody: @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.

Answer 4

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.

• user7802048: How would you name the function/parameters to be more clear?
• Arthur Tacca: 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.
• Snowbody: You ought to mention that the [0] * (n+1) uses additional memory in the interests of making the notation clearer.

Answer 5

Let me Answer few questions that you have asked above

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!

• abuzittin gillifirca: 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.

Answer 6

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)

• Oscar Smith: Have you tested this? It returns incorrect values for 3,4, and 5. Probably more. Haven't checked.
• Solomon Ucko: Hmm. Taking a look. I got it from here
• Solomon Ucko: Oops, I needed to use round instead of int. Thanks for pointing that out!