Fibonacci Calculator C++

Posted · 3 Comments
Fibonacci sequence using Linked Lists

The fibonacci sequence is as follows :

0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;  \ldots.

Each successive number is equal to the sum of the two preceding numbers. If you wanted to find the 5th number of the sequence it would be 5.

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12
0 1 1 2 3 5 8 13 21 34 55 89 144

This program is implemented with a double linked list. Each Fibonacci number stored as a sequence of integers inside of a list. For example to calculate the 6th number of the Fibonacci sequence it would start out with f1 and f2 lists that have a single node with 1 inside.

Starting at i = 2(first 2 numbers already calculated),

While i < 6
F1 = F1 + F2
i++

If i != 6
F2 = F2 + F1
i++

If i – 1 is even then output F1
If i – 1 is odd then output F2

Fibonacci sequence using Linked Lists

Essentially this continues until the number gets greater than 999,999,999(Because list stores integers). Once the number reaches higher than this it will carry one to next node in list:  total = F1 + F2 + carry

F1 = total mod 1,000,000,000

carry = total / 1,000,000,000

It will then carry over to next node in list. If you have a carry on last node, it might be wise to put carry on end node and create an empty node on other list to keep both lists equal size. All of this is implemented in your add function that adds both the lists and stores in the calling object. I have included my add function so it might be understood a little better.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/****************************************************************
* List addition operator - Adds each item in each node for 2 lists
* Stores values in calling object.
****************************************************************/

void List::add(List &right)
{
int count = numItems;

int total;
int carry = 0;
for (int i = 0; i < count; i++)
{
//Perform addition and carry
total = this->getData(i) + right.getData(i) + carry;
carry = total / 1000000000;

//Result is stored and node that was in it's place is removed
this->insert(total % 1000000000, i);
this->remove(i + 1);

//If carry on Last node add new Node to calling object with carry
if (carry == 1  && i == count - 1)
{
this->insert(carry, i + 1);
// Add node with zero to maintain equal list size
right.insert(0, i + 1);
}
}
return;
}

Took about 5 seconds to calculate a 12,345. This can be modified to calculate larger fibonacci numbers by using even larger digits with a library like the NTL or GMP.