Calculating Fibonacci Numbers

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Calculating Fibonacci Numbers

Nitin Verma

May 30, 2020

The Fibonacci Sequence is deﬁned as:

F1 = 1 F2 = 1 Fn = Fn− 2 + Fn− 1 ∀n > 2 (1)

So its ﬁrst few terms are:

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14
F_n	1	1	2	3	5	8	13	21	34	55	89	144	233	377

Given an integer n > 2, we need to write a program to calculate F_n.

Fibonacci numbers grow very fast with n and cannot be represented in 64-bits for n larger than 93:

F94 = 19740274219868223167 264 − 1 = 18446744073709551615

So such a program needs to use additional software mechanism to represent these large numbers and perform operations on them. In this article, we do not discuss about handling large numbers and only write programs with integer type “long” in C. These programs can be adapted to use data-types and operations for large numbers, while keeping the algorithm same.

[Next]