Code Efficiency

[Jeny Merlyn]

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;
}

[hamsterman]

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.

[Jeny Merlyn]

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;
}
}
}

[hamsterman]

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.

[Jeny Merlyn]

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 ..

[JellyFox]

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.

while ( (next = lPos + rPos) <= num )
{
	lPos = rPos;
	rPos = next;
	cout << rPos << endl;
}	

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

[Jeny Merlyn]

yeah thats right .. thanks.

[Athar]

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)?

[hamsterman]

@Athar, where did "megabytes" come from?

[Athar]

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.

[hamsterman]

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..

[coder777]

Jeny Merlyn wrote:

yeah thats right .. thanks.

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

[JellyFox]

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:

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