Fibonacci was an Italian mathematician who introduced this subject to European mathematics, but the similar array was mentioned even before his time.
There are two definitions of Fibonacci numbers with slight variation. Both are pretty similar but little different at the same time.
First:
0, 1, 1, 2, 3, 5, 8, …
Second:
1, 1, 2, 3, 5, 8, …
If you look closer at the above sequence, each number is constructed as the sum of previous two numbers. The first two numbers are: zero and one (or one and one).
For this article, we’ll use the first definition.
Fibonacci(0) = 0,
Fibonacci(1) = 1,
Fibonacci(2) = Fibonacci(0) + Fibonacci(1) = 0 + 1 = 1
Fibonacci(3) = Fibonacci(1) + Fibonacci(2) = 1 + 1 = 2
Fibonacci(4) = Fibonacci(2) + Fibonacci(3) = 1 + 2 = 3
…
Fibonacci(n) = Fibonacci(n-2) + Fibonacci(n-1).
Implementation of Fibonacci Number
There are many ways you could create the array of Fibonacci, but I will show two most common methods.
The first approach is to use the recursive implementation. For this, you should spot the pattern and apply it to the function as shown below.
long long
FibonacciElement( long long n)
{
if (n==0) return 0;
if (n==1) return 1;
return FibonacciElement(n-2) + FibonacciElement(n-1);
}
Now, I strongly recommend you to take 8-th element of the Fibonacci sequence and calculate it with binary tree structure in the textbook or in some program that will be suitable for that task.
As you analyze it you should notice that there are elements that are calculated few times, this is one of the reasons why this approach will be slower, that problem could be solved if you use compiler that has memorization built in, sometimes you need to use few adjustments.
The second approach will not use the self calling of the function as shown below:
long long
FibonacciElement2( long long n)
{
long long Previous = 0,
PPrevious = 1;
long long i=2, Curent;
while( i <= n)
{
Curent = PPrevious + Previous;
PPrevious = Previous;
Previous = Curent;
++i;
}
return Curent;
}
Recursive implementation is usually slower than those which don’t have self called functions. And that is another discussion, we will not enter into that matter, but I think that it would be good time for the short story.
#include <iostream>
using namespace std;
long long FibonacciElement1(long long);
long long FibonacciElement2(long long);
int
main(void)
{
cout<<"Calculate Fibonacci element"<<endl
<<"enter the n -";
long long int lliN; cin>>lliN;
cout<<"With recursion F(n) ="<<FibonacciElement1(lliN)<<endl
<<"Iterative solution F(n)="<<FibonacciElement2(lliN)<<endl;
int iRespond; cin>>iRespond;
return EXIT_SUCCESS;
}
long long
FibonacciElement1( long long n)
{
if (n==0) return 0;
if (n==1) return 1;
return FibonacciElement1(n-2) + FibonacciElement1(n-1);
}
long long
FibonacciElement2( long long n)
{
long long Previous = 0,
PPrevious = 1;
if( n==0) return 0;
if( n==1) return 1;
long long i=1, Curent;
while( i <= n)
{
Curent = PPrevious + Previous;
PPrevious = Previous;
Previous = Curent;
++i;
}
return Curent;
}
We have discussed what Fibonacci numbers are, and we have seen two ways to calculate them.
I recommend that you do further research on this subject by digging little deeper. This algorithm has some practical application as well.
Additional Exercises:
- Create and display first n Fibonacci numbers, use first and second definition.
- Display n-th Fibonacci number: in binary form, in hexadecimal form and in octal form.
- Create the vector with n Fibonacci numbers.
- Construct similar array like Fibonacci array but use: a and b, as first two numbers.
- Form the sequence that is like the Fibonacci array, with tree first elements equal to: 1, 1 and 1.
- Approximate n-th Fibonacci number with some approximation formula, and if you could create one on your own it would be even better.
- Find the sum of first n Fibonacci numbers.
My name is Ramesh Natarajan. I will be posting instruction guides, how-to, troubleshooting tips and tricks on Linux, database, hardware, security and web. My focus is to write articles that will either teach you or help you resolve a problem. Read more about
Comments on this entry are closed.
Wow that sure is alot of code for such a simple algorithm. In Ruby for example, the same code above can be replaced by the following one-liner:
f = ->(x){ x 8
So I’d say that while C/C++ is good for many things, this is definitely not one of them.
The question is not how to implement it, but what practical and/or useful real life benefit does it provide? Seems like a waste of time.
@cybernard
See here ya’ll
http://en.wikipedia.org/wiki/Fibonacci_number#Applications
cybernard you are so wrong about topic. Just google “fibonacci numbers in nature” and see how it is beneficial, next to you, and how wrong you are.
The fibonacci sequence grows about as fast as n squared, but it doesn’t require any multiplications to compute. It’s thus useful on small or low-power processors where addition is fas and multiplication is slow. One of many things it’s useful for is implementing exponential backoff and retry in communication. In normal use, you compute fibonacci(n), already knowing fibonacci(n-1) and fibonacci(n-2). This computation requires only a single addition.
The fibonacci sequence is one of those obscure corners of math that you can live your whole life without knowing, but once you know it, you use it over and over again.
C++ Style Notes
The Fibonacci sequence is only defined over positive integers. The argument to FibonacciElement1() should be unsigned. As coded, FobonacciElement1() will run away dangerously for any negative value of n.
Your computer is not big enough to compute the fibonacci sequence recursively for large values of n, because the stack will have n stack frames on it. Even the iterative computation would take too long for large values of n. I recommend coding FibonacciElement1() with an argument of type “unsigned”, which is “unsigned int”. Since fibonacci(n) is approximately equal to n squared, you have to decide whether you want to attempt to run this code for large n. If you do, your result type has to have about twice as many bits as your argument type. Since this is infeasible as noted above, it’s reasonable for it to return “unsigned” as well.
Here’s a revised version that is safer. Note the recursive version is still wastefully inefficient. You may recode FibonacciElement2() as an exercise :-).
unsigned
FibonacciElement1a(unsigned n)
{
if (n==0) return 0;
if (n==1) return 1;
return FibonacciElement1(n-2) + FibonacciElement1(n-1);
}
@cybernard, Well, your statement is very vague and I just don’t have enough information to have any conclusion what so ever. When you say “waist of time” this is like something that make me wonder!
@Deniz Gezmis, You really understand the thing, just read the article, do the exercises and if you come up with something interesting sare with others.
@Seattle C++, You have a lot of knowledge and wery sharp eye for detailes to. Good work. One more thing, there is a approximation for n-th element of the Fibbonachi array, if you need that to I could post it, but with more carefull search that thing should be found on Internet. Happy Hacking People!!!
Does anybody know the formula for estimation of ciphers of n-th Fibbonachi! Tried google and some others but just would not show it.
@Kiffin Well if you say something like f=->{x8 is it olready bilt in so that you just call the some thing, or did you add some library long before and now you have forgoten about it or somethin like that. Well then you could say that if somebody is developing the numericall algorithms in C++ that is vaist of time just because ther are the progams like Matlab and some other ones. Be more specific!
@Kiffin well I habe never meet any Kiffins eather but I have noticed that you have mention copy destructor on your site. Please could you be more elaborat on this one because I have never seen that thing eather, there are copy constructors but I have never heard of copy destructor, have heard of virtual ones. Interesting subject indead!
Sorry, but the code I added in my comment got botched because of the special characters. Does
codework?f = ->(x){ x < 2 ? x : f[x-1] + f[x-2] }puts f[5]From point of wiev that you cold create faster code, I would disagree! The aproximation algorithm is way easier to implement and faster, saves memory and so on. This is more exercize thing, as you might notice.
This is one array of cyphers it has something to do with Fibonachi array to, it is for execize>0112358314593471897639213… one more thing to do with it is to check is it periodicall or not. Have funn!
Well aproximation would bit that line any time, speed or what so ever!
template struct Fibonacci
{
enum { value = (Fibonacci::value + Fibonacci::value) };
};
template struct Fibonacci
{
enum { value = 1 };
};
template struct Fibonacci
{
enum { value = 1 };
};
template struct Fibonacci
{
enum { value = 1 };
};
int main()
{
int x = Fibonacci::value;
cout << x << endl;
int x
}
Ok, so>
For task like computing fibnacci numbers you can still use recursive algorithm without coputational explosion. What you need is to be able to return more than one value. In C++ you can use structures like vectors.
See following rework of the code that can compute fibonacci numbers recursively withhout problems described in article. This version is as fast as iterative version.
#include <iostream> #include <vector> using namespace std; vector<long long> FibonacciElement(long long); int main(void) { cout<<"Calculate Fibonacci element"<<endl <<"enter the n - "; long long int lliN; cin>>lliN; cout<<"With recursion F(n) ="<<FibonacciElement(lliN)[1]<<endl; int iRespond; cin>>iRespond; return 0; } vector<long long> FibonacciElement( long long n) { if (n==0) return vector<long long> { 0, 0 }; if (n==1) return vector<long long> { 0, 1 }; vector<long long> fib = FibonacciElement(n-1); long long tmp = fib[0]; fib[0] = fib[1]; fib[1] = fib[0] + tmp; return fib; }Nice stuff!
THX a lot FOK!
Even do it is done before it will improve the article!
One more clarification, when I think about the recurzion I like to think about tree different points of view, yes there are some other points of view but somehow they are not so important> what is mathematical definition of recursion, you will see the difference if you anayze the n! definition, the secont is how programmer code it, you have nicely presnted one more way that will produce the code that has less calculations, the third and it might be the most importent is how it is translated into executable bfile withsome optimizations it could be very fast but it coud be done more on that fild if that thiong is not done a. The next big thing is mutithreading, but that is another big topicc.
And if did not say that, when you apply the selfcaled function there are a lot of copies of that function, the stack gets overused, this is traditional view of point, if this could be avoided to then you could really writte nice code and get the very fast results… endles story indead. expanation of the recursion in two steps> 1. look at the second step for information what is the recursion. 2. if you have not get it yet return back to the first step. This is bit funny. Fore real thing there is formal matematical definition to!
One more coment on this subject, it has a lot of applications in real life, but there is one more thing to go with this article, and this way it would not be said. Well, you could array-s for big numbers, then you could calculate the Fibonacci elemente even beyond the limits of the long long int, the unsigned one, or any data type that would be provided to you by defaults…
@duskoKoscica yes, you are right, for such calculations might be recurisve algorithm bit of problem. Too deep recursion is always problem and can cause troubles. I would prefer your iterative version over my recursive.
What I wanted to show with my code was that some tasks require returning more than one value. And for such case it is useful to use complex data types.
In some languages, like perl, it is possible to return just arrays of data.
I have read that some functional programming languages do function call results caching. So if you e.g. call fib(5), then on call fib(6) it will just calculate sum of two cached values for fib(5) and fib(4). I think that this problem is perfect fit for such feature.
@Fok I am very thankfull for your information, the way to calculate the Fib in the way you have shown is great thing. Recursion is great to. But there are some solutions that are good from point of speed, and some are just intelectual teazers, you should learn feaw of them to. In my next article about prime numbers it is just the path for the people to look for other ways. In the way this was just the small push toward the goal each of readers shoule achieve. Because we are not the same and we have some preferences, the result should be different but it is the way thing work!
And one more thing about Fib nums. There is very easy way to check if the given number is Fib num. Try to google it.