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.

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.

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.

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

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.

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!

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)