12
\$\begingroup\$

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.
\$\endgroup\$
11
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user7802048 Dec 20 '17 at 1:22
  • \$\begingroup\$ @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. \$\endgroup\$ – vnp Dec 20 '17 at 1:24
  • \$\begingroup\$ Isn't it possible to do without matrix exponentiation, just using the identities above? \$\endgroup\$ – user7802048 Dec 20 '17 at 1:26
  • \$\begingroup\$ Those identities are awesome! It's the first time I see them. Thanks! \$\endgroup\$ – Eric Duminil Dec 20 '17 at 10:44
  • 1
    \$\begingroup\$ This question is related. The answer by Paul Hankin I found particularly illuminating. \$\endgroup\$ – James K Polk Dec 20 '17 at 18:43
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Why not use the basic iterative version for n<100 or so? It should be faster, as recursion in python is often slow. \$\endgroup\$ – Oscar Smith Dec 20 '17 at 19:09
  • \$\begingroup\$ @OscarSmith: You're right. I updated the answer with an iterative solution. \$\endgroup\$ – Eric Duminil Dec 21 '17 at 21:53
  • \$\begingroup\$ Instead of doing both the div and the mod (the // and the %) use the divmod() function \$\endgroup\$ – Snowbody Dec 22 '17 at 6:36
  • \$\begingroup\$ @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. \$\endgroup\$ – Eric Duminil Dec 22 '17 at 8:23
  • 1
    \$\begingroup\$ @EricDuminil I just learned about it and I think it's a hidden gem of python. Yes I am a little overenthusiastic about it. \$\endgroup\$ – Snowbody Dec 22 '17 at 15:27
5
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Ziyad Edher Dec 20 '17 at 9:24
  • \$\begingroup\$ Good point, I will add it \$\endgroup\$ – 13ros27 Dec 20 '17 at 10:09
  • \$\begingroup\$ 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. \$\endgroup\$ – Eric Duminil Dec 20 '17 at 10:33
  • 1
    \$\begingroup\$ It is the value of Phi, it loses accuracy the larger the number you are finding \$\endgroup\$ – 13ros27 Dec 20 '17 at 12:35
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Snowbody Dec 22 '17 at 16:04
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ How would you name the function/parameters to be more clear? \$\endgroup\$ – user7802048 Dec 20 '17 at 11:42
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Arthur Tacca Dec 20 '17 at 17:18
  • \$\begingroup\$ You ought to mention that the [0] * (n+1) uses additional memory in the interests of making the notation clearer. \$\endgroup\$ – Snowbody Dec 22 '17 at 6:36
3
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – abuzittin gillifirca Dec 20 '17 at 7:48
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Have you tested this? It returns incorrect values for 3,4, and 5. Probably more. Haven't checked. \$\endgroup\$ – Oscar Smith Dec 21 '17 at 23:42
  • \$\begingroup\$ Hmm. Taking a look. I got it from here \$\endgroup\$ – Solomon Ucko Dec 22 '17 at 15:23
  • \$\begingroup\$ Oops, I needed to use round instead of int. Thanks for pointing that out! \$\endgroup\$ – Solomon Ucko Dec 22 '17 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.