The Algorithms logo
The Algorithms
AboutDonate

Fibonacci Numbers

"""
This is a pure Python implementation of Dynamic Programming solution to the fibonacci
sequence problem.
"""


class Fibonacci:
    def __init__(self) -> None:
        self.sequence = [0, 1]

    def get(self, index: int) -> list:
        """
        Get the Fibonacci number of `index`. If the number does not exist,
        calculate all missing numbers leading up to the number of `index`.

        >>> Fibonacci().get(10)
        [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
        >>> Fibonacci().get(5)
        [0, 1, 1, 2, 3]
        """
        if (difference := index - (len(self.sequence) - 2)) >= 1:
            for _ in range(difference):
                self.sequence.append(self.sequence[-1] + self.sequence[-2])
        return self.sequence[:index]


def main():
    print(
        "Fibonacci Series Using Dynamic Programming\n",
        "Enter the index of the Fibonacci number you want to calculate ",
        "in the prompt below. (To exit enter exit or Ctrl-C)\n",
        sep="",
    )
    fibonacci = Fibonacci()

    while True:
        prompt: str = input(">> ")
        if prompt in {"exit", "quit"}:
            break

        try:
            index: int = int(prompt)
        except ValueError:
            print("Enter a number or 'exit'")
            continue

        print(fibonacci.get(index))


if __name__ == "__main__":
    main()
About this Algorithm

In mathematics, the Fibonacci numbers commonly denoted F(n), form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. The Sequence looks like this:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]

Applications

Finding N-th member of this sequence would be useful in many Applications:

  • Recently Fibonacci sequence and the golden ratio are of great interest to researchers in many fields of

science including high energy physics, quantum mechanics, Cryptography and Coding.

Steps

  1. Prepare Base Matrice
  2. Calculate the power of this Matrice
  3. Take Corresponding value from Matrix

Example

Find 8-th member of Fibonacci

Step 0

| F(n+1)  F(n)  |
| F(n)    F(n-1)|

Step 1

Calculate matrix^1
| 1 1 |
| 1 0 |

Step 2

Calculate matrix^2
| 2 1 |
| 1 1 |

Step 3

Calculate matrix^4
| 5 3 |
| 3 2 |

Step 4

Calculate matrix^8
| 34 21 |
| 21 13 |

Step 5

F(8)=21

Implementation

Video URL

Others