| by Arround The Web | No comments

Fibonacci Numbers in Python Language

“If 0 is added to 1, the answer would be 1. If the answer 1 and the addend (not the augend) are added together, the new answer would be 2. If this new answer and its addend are added together, the answer would be 3. If this new answer and its addend are added together, the answer would be 5.”

Fibonacci numbers are a particular sequence where the first value is pre-declared as 0 and the second value is pre-declared as 1. The rest of the numbers are produced from these two by adding the previous two numbers. All Fibonacci numbers are positive integers, beginning from 0. The first twelve Fibonacci numbers and how they are obtained are 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

Without the sum expressions, these Fibonacci numbers can be put in a table as follows:

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

The first row has the Fibonacci numbers. The second row has zero-based indexes, assuming that the Fibonacci numbers are in an array.

Fibonacci numbers can be produced in O(n) time and 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 a corresponding index. That is why it 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 Python.

Formula for a Fibonacci Number

The formal definition of a Fibonacci number is:

where Fn is the Fibonacci number at the zero-based n<supth index. 0 and 1 are pre-declared. The last line shows how the rest of the numbers are produced from the first two. It shows that the immediate previous two numbers are added to give the current number.

Producing Fibonacci Numbers in O(n) Time

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

The Python function to produce the first n Fibonacci numbers is:

def fibonacci(n):
    arr = [0] * (n)
    arr[1] = 1
    for i in range(2, n):
        arr[i] = arr[i - 1] + arr[i - 2]
    return arr

It begins by creating an array of n elements, all initialized to zeros. This array will hold the Fibonacci numbers. The first Fibonacci number, 0, is already there. The second Fibonacci number, 1, is assigned by the next statement (in the function). Then there is the for-loop, which begins from index 2 to just before n. It has the statement:

arr[i] = arr[i - 1] + arr[i - 2]

This adds the immediate previous two numbers.

Code to call the function and print the first twelve Fibonacci numbers can be:

N = 12
A = fibonacci(N)
for i in range(N):
print (A[i], end=’ ‘)
print()

The output is:

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

Producing One Fibonacci Number in Constant Time

There is a mathematical formula that relates a zero-based index to its corresponding Fibonacci number. The formula 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 Python code for this formula is:

import math

def fibNo(n):
    FibN = (((1+math.sqrt(5))/2)**n - ((1-math.sqrt(5))/2)**n) / math.sqrt(5)
    return FibN

The math module was imported. It has the square root function. The operator, ** is used for power. The function fibNo() implements the formula directly. A suitable call and printing for the fibNo() function is:

N = 11
ret = fibNo(N)
print(ret)

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 different Fibonacci numbers are required for different n indexes, the function fibNo() has to be called once for each of the n index to return the different corresponding Fibonacci numbers. The following program does this for the zero-based indexes, 7 to 9 (inclusive) :

import math

def fibNo(n):
    FibN = (((1+math.sqrt(5))/2)**n - ((1-math.sqrt(5))/2)**n) / math.sqrt(5)
    return FibN
     
for i in range(7, 10):
    print(fibNo(i), end=' ')
print()

The output is:

13.000000000000002 21.000000000000004 34.00000000000001

Note the way the for-loop has been coded in Python. The first index is 7. The next index is 8, and the last index is 9. 10 in the range argument is 9 + 1. The value in the position of 10 has to be the last zero-based index plus 1. The first argument, 7, is the start zero-based index.

Conclusion

Fibonacci numbers are a particular sequence of whole numbers (positive integers). It begins with 0, followed by 1 unconditionally. The rest of the numbers are developed from there by adding the immediate previous two numbers.

To obtain the first n Fibonacci numbers, accept 0 and 1 as the first two, then for the rest, use a for-loop with a statement like:

arr[i] = arr[i - 1] + arr[i - 2]

which adds the immediate previous two numbers.

To obtain just one Fibonacci number from a zero-based index n, use the formula:

Share Button

Source: linuxhint.com

Leave a Reply