Calculating any Term of the Fibonacci Sequence Using Binet’s Formula in JavaScript

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

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


Binet's Formula

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

Binets Formula

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

This project consists of a JavaScript file called binetsformula.js as well as an HTML page and a few ancilliary files. You can also download them as a zip from the Downloads page or clone/download from Github if you prefer.

Source Code Links

ZIP File
GitHub

This is the binetsformula.js code.

binetsformula.js

window.onload = function()
{
    writeToConsole("Binet's Formula<br/>", "console");
    writeToConsole("---------------<br/>", "console");

    printFibonacciTo(16);
}


function printFibonacciTo(n)
{
    if(n < 2)
    {
        writeToConsole("term must be >= 2<br/>");
    }
    else
    {
        let F_n_minus_2 = 0;
        let F_n_minus_1 = 1;
        let F_n = 0;
        let F_n_Binet = 0;

        writeToConsole("<br/>Calculating Fibonacci numbers sequentially and using Binet's Formula<br/><br/>", "console");
        writeToConsole("Term Seq Binet OK?<br/>------------------<br/>", "console");

        writeToConsole("   0" + padNumber(F_n_minus_2, 4) + "     ~  ~<br/>", "console");
        writeToConsole("   1" + padNumber(F_n_minus_1, 4) + "     ~  ~<br/>", "console");

        for(let i = 2; i <= n; i++)
        {
            F_n = F_n_minus_2 + F_n_minus_1;

            F_n_Binet = BinetsFormula(i);

            writeToConsole(padNumber(i, 4) + padNumber(F_n, 4) + padNumber(F_n_Binet, 6), "console");

            if(F_n_Binet === F_n)
            {
                writeToConsole("  Y<br/>", "console");
            }
            else
            {
                writeToConsole("  N<br/>", "console");
            }

            F_n_minus_2 = F_n_minus_1;
            F_n_minus_1 = F_n;
        }
    }
}


function BinetsFormula(n)
{
    // pre-calculate Math.sqrt(5) as we use it three times
    let sqrt5 = Math.sqrt(5);

    return Math.round(( Math.pow((1 + sqrt5), n) - Math.pow((1 - sqrt5), n) ) / ( Math.pow(2, n) * sqrt5 ));
}


function padNumber(number, width)
{
    let padded = number.toString();

    for(let i = 0, l = width - padded.length; i < l; i++)
    {
        padded = " " + padded;
    }

    return padded;
}

window.onload

Here we just print a heading and call the next function, printFibonacciTo.

printFibonacciTo

Firstly we check that n is more than 1. If so we declare a few variables to hold the current and previous two numbers in the Fibonacci series, these being used to calculate the series by conventional addition. We also need a variable for the terms calculated with Binet's Formula.

We then print the first two values, 0 and 1, of the Fibonacci Series before entering a for loop which will calculate subsequent values by addition and with Binet's Formula. These are printed out and we then check that the two values for the term are the same. They always will be of course so this is just to demonstrate that.

Finally we shift the values of the two variables holding previous terms up by 1.

BinetsFormula

This is a simple function which as you an see implements Binet's Formula which is repeated below.

Binets Formula

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

padNumber

A little utility function to pad the values so they are right-aligned.

Viewing the Result

The code is now finished so open binetsformula.htm in your browser which looks like this.