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 calculate directly any term of the sequence. This short project is an implementation of the formula in C.

Binet's Formula

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

Binet's Formula

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

Coding

In some projects on this site I will split out major pieces of code into separate .h and .c files, but with the shortest and simplest I will just use one source code file. This will be one of the latter so just create a new folder and within it create an empty file called binetsformula.c and then paste in the following code. You can also download the source code as a zip or from Github if you prefer.

Source Code Links

ZIP File
GitHub

binetsformula.c

#include<stdio.h>
#include<math.h>

//--------------------------------------------------------
// FUNCTION PROTOTYPES
//--------------------------------------------------------
void print_fibonacci_to(int n);
int binets_formula(int n);

//--------------------------------------------------------
// FUNCTION main
//--------------------------------------------------------
void main(void)
{
    puts("-------------------");
    puts("| codedrome.com   |");
    puts("| Binet's Formula |");
    puts("-------------------\n");

    print_fibonacci_to(8);
}

As you can see we have prototypes for two functions. The first, print_fibonacci_to, will calculate and print each Fibonacci number sequentially up to the term given by the argument n. It will also call the second function, binets_formula, to calculate the term directly and print it next to the sequentially calculated term so we can check they are the same.

Paste or type the print_fibonacci_to function given below into your file.

binetsformula.c

//--------------------------------------------------------
// FUNCTION print_fibonacci_to
//--------------------------------------------------------
void print_fibonacci_to(int n)
{
    if(n < 2)
    {
        printf("term must be >= 2\n");
    }
    else
    {
        int F_n_minus_2 = 0;
        int F_n_minus_1 = 1;
        int F_n = 0;
        int F_n_Binet = 0;

        printf("Calculating Fibonacci numbers\nsequentially and using Binet's Formula\n\n");
        printf(" Term Seq Binet OK?\n------------------------------------\n");

        printf(" 0 %3d ~ ~\n", F_n_minus_2);
        printf(" 1 %3d ~ ~\n", F_n_minus_1);

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

            F_n_Binet = binets_formula(i);

            printf("%5d %12d %12d", i, F_n, F_n_Binet);

            if(F_n_Binet == F_n)
                printf(" Y\n");
            else
                printf(" N\n");

            F_n_minus_2 = F_n_minus_1;
            F_n_minus_1 = F_n;
        }
    }
}

After checking that n > 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.

Finally we need the binets_formula function, so type or paste the following at the end of your code.

binetsformula.c

//--------------------------------------------------------
// FUNCTION print_fibonacci_to
//--------------------------------------------------------
int binets_formula(int n)
{
    // as we use sqrt(5), pre-calculate it to make the formula look neater
    double sqrt5 = sqrt(5);

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

    return F_n;
}

You probably noticed earlier that √5 is used three times in the formula so I decided to assign it to a variable. This is probably overkill in a case as simple as this, but it is a sound principle to introduce.

The code is now finished so we can compile and run it. Enter the following in your terminal to compile

Compiling

gcc binetsformula.c -std=c11 -lm -o binetsformula

and then the following to run

Running

./binetsformula

The output is

Program Output

-------------------
| codedrome.com   |
| Binet's Formula |
-------------------

Calculating Fibonacci numbers
sequentially and using Binet's Formula

 Term          Seq        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

I have only shown up to the 8th term here but of course you can change the argument in main to any number you wish. If you suffer from leporiphobia it's best not to go too much higher though: the thought of all those rabbits might give you nightmares.