The fibonacci sequence is as follows :
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
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.
May 18, 2010
Terrific work! This is the type of information that should be shared around the web. Shame on the search engines for not positioning this post higher!
June 16, 2011
That’s pretty cool, bro. Do you think it would run faster/slower if you used floats or doubles instead of ints?
June 16, 2011
Actually since each integer inside the list represents one digit of the full number, using a floating point data type wouldn’t have any benefit.