You can calculate the Fibonacci Sequence by starting with 0 and 1 and adding the previous two numbers, but Binet's Formula can be used to directly calculate any term of the sequence. This short project is an implementation of that formula in Python.

You are probably familiar with the Fibonacci sequence and it's application to the hypothetical breeding habits of rabbits, but you may wish to brush up on the subject by reading the relevant Wikipedia article, as well as the article on Binet and his formula.

Fibonacci number

Jacques Philippe Marie Binet

The formula as presented by Wikipedia is

which can be represented in a way more useful for implementation in a programming language as

Binets Formula

((1 + √5)ⁿ - (1 - √5)ⁿ) / (2ⁿ * √5)

This project will consist on two Python files, one containing functions implementing Binet's Formula and the other containing a short piece of code to demonstrate them. Create a new folder somewhere convenient and within it create the following empty files. You can also download the source code as a zip or clone/download from Github if you prefer.

• binetsformula.py
• main.py

Source Code Links

ZIP File
GitHub

Open binetsformula.py and type or copy/paste this code.

binetsformula.py part 1

import math


def binets_formula(n):

    """
    The central function implementing Binet's Formula
    """

    # pre-calculate sqrt(5) as we use it 3 times
    sqrt5 = math.sqrt(5)

    F_n = int((( (1 + sqrt5) ** n - (1 - sqrt5) ** n ) / ( 2 ** n * sqrt5 )))

    return F_n

After importing math for its sqrt and pow functions we have the function which actually implements Binet's Formula to calculate the value of the Fibonacci Sequence for the given term n. The formula uses √5 no less than three times so I have assigned it to a separate variable, both for efficiency and to make the code slightly more concise.

The next line is Binet's Formula itself, the result of which is assigned to the variable F_n - if you examine it carefully you can see it matches the formula in the form.

((1 + √5)ⁿ - (1 - √5)ⁿ) / (2ⁿ * √5)

Using √5 will force Python to evaluate the formula as a real number so the whole expression is cast to an integer using the int function. Lastly we just need to return F_n.

We can now move on to the second and last function in binetsformula.py.

binetsformula.py part 2

def print_fibonacci_to(n):

    """
    Prints the Fibonacci Sequence to the given term
    using both addition of the previous two terms and
    Binet's Formula.
    """

    if n < 2:

        print("term must be >= 2\n")

    else:

        F_n_minus_2 = 0
        F_n_minus_1 = 1
        F_n_seq = 0
        F_n_Binet = 0

        # print heading and first two hard-coded terms
        print("\n Term Sequential      Binet  OK?\n--------------------------------")
        print("    0        {0:3d}          ~   ~".format(F_n_minus_2))
        print("    1        {0:3d}          ~   ~".format(F_n_minus_1))

        for term in range(2, n):

            # calculate current term both ways
            F_n_seq = F_n_minus_2 + F_n_minus_1
            F_n_Binet = binets_formula(term)

            print("{0:5d} {1:10d} {2:10d}".format(term, F_n_seq, F_n_Binet), end='')

            # Check both are the same!
            if(F_n_Binet == F_n_seq):
                print("   Y")
            else:
                print("   N")

            # Set previous two terms ready for nect iteration
            F_n_minus_2 = F_n_minus_1
            F_n_minus_1 = F_n_seq

The print_fibonacci_to function calculates and prints the values of the Fibonacci Sequence up to and including the given term n. It does this using two methods, the conventional way of adding the two previous terms and also using Binet's Formula. It also checks the two match, as they always should.

After checking that n is > 2 we declare variables to hold the previous two terms of the sequence, and the current term as calculated sequentially and using Binet's formula. We then print out some column headings and the first two terms before getting to the main part of the function: a for loop from 2 to the required term.

In this loop we calculate the term firstly by adding the two previous terms, and then by calling the binets_formula function. These are then printed, followed by a Y/N indicator of whether the two are the same - hopefully the "else" will never be used. Lastly we change the the variables holding the previous two terms ready for the next iteration.

That's the main coding finished so we just need a short function to try it out. Type or copy/paste this code into main.py.

main.py

import binetsformula


def main():

    """
    Binet's formula calculates any term of the Fibonacci
    Sequence. Here we just call a function to demo it.
    """

    print("---------------------------")
    print("| codedrome.com           |")
    print("| Calculating Any Term of |")
    print("| the Fibonacci Sequence  |")
    print("| Using Binet's Formula   |")
    print("---------------------------")

    binetsformula.print_fibonacci_to(16)


main()

After printing a heading the main function simply calls the binetsformula.print_fibonacci_to function - don't forget to import binetsformula at the top.

The code is now finished so enter the following in your terminal to run it.

Run

python3.7 main.py

The output is

Program Output

---------------------------
| codedrome.com           |
| Calculating Any Term of |
| the Fibonacci Sequence  |
| Using Binet's Formula   |
---------------------------

 Term Sequential      Binet  OK?
--------------------------------
    0          0          ~   ~
    1          1          ~   ~
    2          1          1   Y
    3          2          2   Y
    4          3          3   Y
    5          5          5   Y
    6          8          8   Y
    7         13         13   Y
    8         21         21   Y
    9         34         34   Y
   10         55         55   Y
   11         89         89   Y
   12        144        144   Y
   13        233        233   Y
   14        377        377   Y
   15        610        610   Y