Hey guys,

The below working function returns the sum of all Fibonacci sequence numbers between 0 and a given number. For example the sum of all Fibonacci sequence numbers up to 10 is 1+1+2+3+5+8 = 20.

Is this code in any way inefficient or extremely inefficient maybe ? Does the below solution take into account the tradeoffs between coding time, code maintainability, code efficiency? Please let me know asap.

Thanks for all the help.

--------------------------------------------------------------------------------

#include <iostream>
using namespace std;

int GetSumOfFibonacciNumbers(int nMax);
void Destroy();
int *f = NULL; // Initialising pointer variable for dynamic storage allocation purposes

int main()
{
cout << "Enter the maximum number to include in the fibonacci sequence - ";
int num = 0;
cin >> num;

int sum = GetSumOfFibonacciNumbers(num);
cout << "Sum of the fibonacci sequence numbers upto " << num << " is: " << sum << endl;

Destroy();
}

/* Provide sum of fibonacci sequence numbers upto the maximum number as specified by end user */
int GetSumOfFibonacciNumbers(int nMax)
{
int sum = 0;
int i = 0;

f = new int[nMax+1]; //Allocating space of size(nMax+1) in the array
f[1] = f[2] = 1;
cout << f[1] << endl << f[2] << endl;
sum = f[1] + f[2];

for (i = 3; i <= nMax; i++) //Starting from the third element in the array
{
f[i] = f[i-1] + f[i-2]; //E.g. f[4]=f[3]+f[2]
if (f[i] <= nMax) //Restricting the sequence upto nMax
{
cout << f[i] << endl;
sum = sum + f[i]; //Sum of the fibonacci series upto nMax
}
else
{
break; //Incase the next number in the series is greater than nMax, break the for loop
}
}

return sum;
}

/* Clear memory space used by the pointer variable */
void Destroy()
{
delete [] f;
f = NULL;
}

This is inefficient. To find a Fibonacci number you only need two numbers that go before it and to find a sum of several numbers you only need to know one at a time. The solution should be clear if you can figure out a non recursive method to find nth Fibonacci number without allocating memory for all numbers that go before it. Hint - replace the old values with newer ones to reuse memory.

Thanks for the quick reply.

So the function below will be much better off, since much fewer values are being used ?

--------------------------------------------------------------------------------------------------------------------------

// Fibonacci series generation upto a maximum number

#include <iostream>
using namespace std;
void fibo(int num);

int main()
{
cout << "Enter the fibonacci sequence number...";
int num = 0;
cin >> num;
fibo(num);
}

void fibo(int num)
{

int lPos = 1;
int rPos = 1;
int next = 0;

cout << "Fibonacci sequence upto " << num << " numbers are:" << endl << lPos
<< endl << rPos << endl;

for (int i = 3; i <= num; i++)
{
next = lPos + rPos;
if (next <= num)
{
lPos = rPos;
rPos = next;
cout << rPos << endl;
}
else
{
break;
}
}
}

Sort of. Memory allocation does take some time. I guess there are some other details I could complain about. Do notice, though, that the real performance difference between the two versions in negligible. The second one is just more thought out.

Interesting .. what other details could be changed to make it more efficient? The second code does take less space than the first one but i guess execution time could be more with all the swapping across for the second one and hence performance wise, there is not much difference between the two ..

Since you're not using an array any more, maybe you should replace the for loop with a while loop, since i is now an unneeded variable.



The assignment in the while loop condition will occur even on the last iteration when the expression returns false, so it simplifies your loop.

yeah thats right .. thanks.

Interesting .. what other details could be changed to make it more efficient? The second code does take less space than the first one but i guess execution time could be more with all the swapping across for the second one and hence performance wise, there is not much difference between the two ..

You think a few swaps would be more expensive than allocating megabytes of unnecessary memory every time? A quick test indicates that the first variant is more than twenty times slower than the second one.
Besides, before you go worrying about performance - are you compiling with optimizations enabled (-O3 switch)?

@Athar, where did "megabytes" come from?

Well, the array has nMax elements, which is much more than is actually needed. So if you enter a value like 100,000,000+, a lot of memory is being allocated.

Oh god. I hadn't noticed that. My point was that due to integer size limit, you'd never need to allocate more than 40 or 50 integers..

Jeny Merlyn wrote:
yeah thats right .. thanks.

No. JellyFox is not right. The calculation goes until n and not the nth number.

What do you mean? Mine compiles to the same thing, just without the extra variable needed for the 'for' loop. It was to directly replace this: