Fibonacci numbers are a sequence of integers. The first two of these numbers are 0 and 1. The next number is formed by adding the previous two numbers. That is, each subsequent number is the sum of the previous two. The first sixteen Fibonacci numbers are:

By definition, this is done recursively. In symbolic form, Fibonacci numbers are defined as follows: 

where n is the index. 

Implementation

The code is:

<?php
    function fibonacciDynamic($n) {
        if ($n == 0)
            return [0];
        if ($n == 1)
            return [0, 1];
        $noOperations = 2;
            
        $v = [0, 1];
        for ($i=2; $i < $n; $i++) {
            $nextNo = $v[$i - 1] + $v[$i - 2];
            $v[] = $nextNo;    //push_back
            $noOperations++;
        }

        echo "No. of operations: " . $noOperations . "\n";
        return $v;
    }

    $vtr = fibonacciDynamic(16);
    echo "Fibonacci numbers: ";
    for ($i=0; $i < count($vtr); $i++) {
        echo $vtr[$i] . ', ';
    }
    echo "\n";
?>

The output is:

    No. of operations: 16

    Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 

Enumeration of the Fibonacci numbers has been done, by simply using a basis of dynamic programming. The values F₂ , F₃ , . . . , F_n have been calculated based on the previously calculated two numbers (it is sufficient to remember only the first two values).

Fast Algorithm for a particular Fibonacci Number

With the above approach, in order to get the Fibonacci number corresponding to a particular index, all the previous Fibonacci numbers have to be obtained first. For example, in order to obtain the Fibonacci number, 13 corresponding to the index, 7, the previous Fibonacci numbers:  0, 1, 1, 2, 3, 5, 8 have to be obtained first. The following formula can be used to produce a particular Fibonacci number, when given the corresponding zero based index: 

In the formula, each of the bracketed term is raised to the power n, and it is not √5 that is raised to the power n. F_n is a Fibonacci number such as 13, corresponding to the zero based index, n = 7. A PHP statement to implement the above formula for n = 50001 is:

        F50001 = (Math.pow(((1+Math.sqrt(5))/2), 50001) - Math.pow(((1-Math.sqrt(5))/2), 50001) )/Math.sqrt(5);

This means the math.h library has to be included for the power function, pow() and the square root function, sqrt(). The reader should avoid using this formula whenever he/she can. This is because on the right hand side, double or float numbers are required while on the left hand side, a long integer is required.

Conclusion

In symbolic form, Fibonacci numbers are defined as follows: 

They can be coded like that in O(n) time. To produce one Fibonacci number, use the formula: