Run Time Code Degeneration

[mrshah]

Hi. I've ran into a problem of my code "degenerating" during execution.

Its an array based problem. I'm trying to work with numbers that are "too big" to store readily, so I'm placing each individual digit as an element of an array. To start off, it works fine if I'm only calculating the first 50 digits. (The current code is set to just work up to 10, just to see if it works). However, past 50 it produces the wrong answers, and I cannot figure out why.

I set up a recursive function so it would add together the prior number kind of like how people do by hand (column by column, carrying the one, etc..).

Are there limits to how well arrays work in this situation? I appreciate any assistance.

// global digits - start with a small sample to verify code
int digits = 10;
int term = 3;
int hold, sum;
int i = digits - 1;
int past[10], present[10],future[10]; // three arrays to create fib. seq.

// global functions, declared post main
void addFibonacci(int*, int*, int*);
void resetSequence(int*, int*, int*);
void showTime(int*);
				  
int main()
{
	clock_t runtime = clock();
	
	// set the "F1" and "F2" terms equal to 1 to start the process
	past[i] = present[i] = 1;
	
	addFibonacci(past, present, future);
	showTime(future);	
	cout << endl;
		
	// the term itself will be to large to print easily
	cout << "Term with " << digits << " digits is: " << term << endl;
	
	cout << "Runtime: " << (clock()-runtime)/CLOCKS_PER_SEC;
}

//recursive function (I think I labled it pretty well with variable names)
void addFibonacci (int* pastArray, int* presentArray, int* futureArray)
{
	while ( i >= 0)
	{
		if (presentArray[0] == 1)
		{
			i = -1;
		}
		else
		{
			hold = pastArray[i] + presentArray[i];
			sum = hold;
			if (hold >= 10)
			{
				if (i < 0) break;
				sum -= 10;
				futureArray[i] = sum;
				pastArray[i-1] += 1;
				i--;
				if (i < 0) break;
				addFibonacci(pastArray, presentArray, futureArray);
			}
			if (hold > 0)
			{
				if (i < 0) break;
				futureArray[i] = hold;
				i--;
				if (i < 0) break;
				addFibonacci(pastArray, presentArray, futureArray);
			}
			if (hold == 0)
			{
				if (i < 0) break;
				term++;
				resetSequence(pastArray, presentArray, futureArray);
				showTime(presentArray);
				if (i < 0) break;
			}
		}
		
	}
}

// after finding a number, start over and reset the fib number positions
void resetSequence (int* pastArray, int* presentArray, int* futureArray)
{
	i = digits - 1;
	
	for (int j = 0; j < digits; j++)
	{
		pastArray[j] = presentArray[j];
		presentArray[j] = futureArray[j];
	}
}

void showTime (int* presentArray)
{
	for (int k = 0; k < digits; k++)
	{
		cout << presentArray[k];
	}
	cout << endl;
}

[mrshah]

Any thoughts? I cannot for the life of me figure out what is wrong with my Fibonacci array.

[cire]

Whatever you're trying to do with the arrays doesn't seem obvious to me. There are no comments concerning algorithms. Why is hold a global variable?

Is one array supposed to represent one number? In what way? What does digits represent? What does term represent?

[mrshah]

I'll work on adding better comments as I write code (thanks for pointing that out).

The idea is to set up an 3 arrays and add them the first two together to produce a value to store in the 3rd in the same "column":

0 1 2
[0] [0] [1] - "old" array
[0] [0] [1] - "present" array
------------- (when added they would be stored in the new array)
[0] [0] [2] - "future" array

I would reset the arrays here such that:

old (set equal to) present
present (set equal to) future
future = cleared

Then, I start the adding process over again. If the numbers in one column are > 10, I +1 to the value of the column to the left.

"hold" is a global variable because I wanted to access it from the functions that I was writing outside of the main (probably shouldn't have done that).

Each array represent a fibonacci number. Term represents what fibonacci number it's calculated. It knows when a fib# has been made because when it shifts columns to add together, they add to zero (meaning no digits were present).

I'll try to be more clear in the future.

[cire]

So...

digits and the number of elements in each array should never differ?
Each element of each array should never hold a value higher than 9 outside of AddFibonacci?

How familiar are you with classes and operator overloading?

[mrshah]

Yes! "digits" and the length of the array / number of elements are the same. (I tried to use the variable to initialize the array, but that doesn't work unless its inside the main, apparently)

Each element in the array has to be 0-9. When adding, if it is > 10, I subtract 10 and +1 to the next column (in essence, carrying the one to the next "tens" place).

I understand the syntax for classes and operator overloading, but a novice (I started to read up on OOP just a few days ago). I can try to rewrite the code from scratch with classes instead. I'm guessing the problem isn't an obvious fix in this case. I'm in no rush, just interested in learning. Maybe shouldn't have picked C++ as the first one, but, well, I'm enjoying it so far.

[cire]

You remember that first question I asked?

Whatever you're trying to do with the arrays doesn't seem obvious to me. There are no comments concerning algorithms. Why is hold a global variable?

Consider:

			hold = pastArray[i] + presentArray[i];
			sum = hold;
			if (hold >= 10)
			{
				if (i < 0) break;
				sum -= 10;
				futureArray[i] = sum;
				pastArray[i-1] += 1;
				i--;
				if (i < 0) break;
				addFibonacci(pastArray, presentArray, futureArray);
			}
			if (hold > 0)
			{
				if (i < 0) break;
				futureArray[i] = hold;
				i--;
				if (i < 0) break;
				addFibonacci(pastArray, presentArray, futureArray);
			}
			if (hold == 0)
			{
				if (i < 0) break;
				term++;
				resetSequence(pastArray, presentArray, futureArray);
				showTime(presentArray);
				if (i < 0) break;
			}

In resetSequence, one of the things you do is reset i. So when you're unwinding those recursive calls after resetSequence is called, and hold has been changed by how many calls? Execution falls through an if block it shouldn't and screws you up. If you simply change line 41 by adding int in front of hold (it'll hide the gobal one) and then check out the results, I think you'll be happy with them.

[Gaminic]

Recursion rule nr1: be wary of variables outside of the function scope!

By the way, it seems a bit wasteful to use an entire int for [0,9]. Why not save yourself some space (and recursion levels) by setting a higher limit per individual int? The logic remains the same, just the overflow value changes (>= 100/1000/10000..0 instead of >= 10).

[mrshah]

Thank you cire, I just compiled and its working beautifully. Brilliant eye for detail. Still need some practice with running recursive functions, so I'll keep at it.

Thank you Gaminic, that's a really simple and beautiful idea. I'm still thinking in terms of "let's make the computer do something I can do, and just repeat X number of times." I forget that it can do so much more.

I appreciate the help!