JavaScript

Fibonacci Numbers With JavaScript

“JavaScript is now ECMAScript. The development of JavaScript is continued as ECMAScript. The reserved word “javascript” is still used, just for backward compatibility.”

Meaning of Fibonacci Numbers

Fibonacci numbers are a particular sequence of positive integers, beginning from 0. Whole numbers are positive integers. So, a Fibonacci number is a particular sequence of whole numbers or natural numbers, beginning from 0. In this sequence, the first two numbers are 0 and 1, in that order. The rest of the numbers are developed from there by adding the previous two numbers. The first twelve Fibonacci numbers are obtained as follows:

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

In other words, the first twelve Fibonacci numbers are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Of course, the thirteenth number would be: 144 = 55 + 89. Fibonacci numbers may be imagined to be in an array, like so:

0 1 1 2 3 5 8 13 21 34 55 89

An array has indexes. In the following table, the second row shows the corresponding zero-based indexes for the Fibonacci numbers in an array:

0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11

With zero-based indexes, if there are twelve elements, then the last index is 11.

Fibonacci numbers can be produced in O(n) time or in O(1) time. In these time complexity expressions, n means n main operations, and 1 means 1 main operation. With O(n), n Fibonacci numbers are produced, beginning from 0. With O(1), one Fibonacci number is produced from the corresponding index. That is why O(1) takes just one main operation instead of n main operations.

The aim of this article is to explain how to produce Fibonacci numbers, either way, using JavaScript, which is actually ECMAScript today.

Coding Environment

The node.js environment will not be used as the reader might have anticipated. Instead, the browser will be used for interpretation of the code and displaying the results. The script (code) should be written in a text editor file, which should be saved with the extension “.html.” The script should have as minimum code:

    <!DOCTYPE HTML>
    <html>
    <head>
       <title>Fibonacci Numbers with JavaScript</title>
    </head>
    <body >
    <script type='text/ecmascript'>
   
    </script>
    </body>
    </html>

This is an approximate minimum code a web page needs. All coding for this article goes in-between the tags, <script type=’text/ecmascript’> and </script>.

To run the code written (added), just double-click the icon of the filename, and the browser of the computer will open it.

Definition of a Fibonacci Number

There is a mathematical definition for a Fibonacci number. It is defined as follows:

Where Fn is a Fibonacci number corresponding to a zero-based index, n.

The first two numbers: 0 and 1, are pre-declared, in that order. The last line of this function shows how the rest of the numbers originate from the first two numbers in their order.

This definition is also one of the formulas for the Fibonacci number.

Producing Fibonacci Numbers in O(n) Time

If n is 1, then only 0 would be displayed as a Fibonacci number. If n is 2, then 0 and 1 would be displayed as Fibonacci numbers, in that order. If n is 3, then 0, 1, and 1 would be displayed as Fibonacci numbers in that order. If n is 4, then 0, 1, 1, and 2 would be displayed as Fibonacci numbers, in that order. If n is 5, then 0, 1, 1, 2, and 3 would be displayed as Fibonacci numbers, in that order. If n is 6, then 0, 1, 1, 2, 3, and 5 would be displayed as Fibonacci numbers, in that order – and so on.

The ECMAscript function to generate the first n Fibonacci integers (numbers) is:

    <script type='text/ecmascript'>
        function fibonacci(A) {
            n = A.length;
            if (n > 0)
                A[0] = 0;
            if (n > 1)
                A[1] = 1;
            for (i=2; i<n; i++) {  //n=0 and n=2 have been considered
                currNo = A[i - 1] + A[i - 2];
                A[i] = currNo;
            }
        }

The closing script tag has not been shown. The function receives an array. The first two Fibonacci numbers are assigned at their position. The for-loop iterates from the zero-based index, 2 to just below n. The most important statement in the for-loop is:

currNo = A[i – 1] + A[i – 2];

This adds the immediate previous two numbers in the array to have the current number. By the time the fibonacci() function finishes executing, all the elements of the array are the first n Fibonacci numbers. A suitable code to call the fibonacci() function and display the Fibonacci numbers is:

        N = 12;
        arr = new Array(N);
        fibonacci(arr);
        for (i=0; i<N; i++)
            document.write(arr[i] + ' ');
        document.write("<br>");
    </script>

This code shows the closing script tag. The code is typed below the above code. The output displayed on the web page is:

0 1 1 2 3 5 8 13 21 34 55 89

as expected.

Producing One Fibonacci Number in O(1) Time

O(1) is constant time. It refers to one main operation. Another mathematical formula to produce a Fibonacci number is:

Note that on the right-hand side of the equation, it is not the square root of 5 that is raised to the power n; it is the expression in parentheses that is raised to the power n. There are two such expressions.

If n is 0, Fibn would be 0. If n is 1, Fibn would be 1. If n is 2, Fibn would be 1. If n is 3, Fibn would be 2. If n is 4, Fibn would be 3 – and so on. The reader can verify this formula mathematically by substituting different values for n and evaluating. n is a zero-based index in this formula. The result is the corresponding Fibonacci number.

The ECMAScript (JavaScript) code for this formula is:

    <script type='text/ecmascript'>
        function fibNo(n) {
            FibN = (Math.pow((1+Math.sqrt(5))/2, n) - Math.pow((1-Math.sqrt(5))/2, n)) / Math.sqrt(5);
            return FibN;
        }

The closing script tag has not been shown. Note how the power (pow) and square root (sqrt) predefined functions have been used. In ECMAScript (JavaScript), the Math module does not have to be imported. The function fibNo() implements the formula directly. A suitable call and display for the fibNo() function on the web page are:

        N = 11;
        ret = fibNo(N);
        document.write(ret);
    </script>

The code shows the closing script tag. The output is:

89.00000000000003

It is possible to remove the unnecessary decimal digits from the answer. However, that is a discussion for some other time.

If more than one Fibonacci number is required, then the code has to call the formula once for each zero based corresponding n index.

Conclusion

Fibonacci numbers are a particular sequence of positive integers, beginning from 0. Whole numbers are positive integers. So, a Fibonacci number is a particular sequence of whole numbers or natural numbers, beginning from 0. In this sequence, the first two numbers are 0 and 1, in that order. These first two numbers are just defined as such. The rest of the numbers are developed from there by adding the immediate previous two numbers.

After producing the first two Fibonacci numbers, in order to produce the rest of the Fibonacci numbers, to end up with a total of n numbers, a for-loop has to be used with the statement:

currNo = A[i – 1] + A[i – 2];

This adds the immediate last two Fibonacci numbers to have the current Fibonacci number.

When given a zero-based index, to have the corresponding Fibonacci number, use the formula:

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.