Fibonacci numbers using doubly linked lists

[Kevin2341]

I'm writing up a program to generate the nth fibonacci number, and I have the program working like a charm up till the 46th fibonacci number.

The general idea is that we are storing an incredible large number in a double linked list with the format as such...

[digits n-9 to n] <--> ... <--> [19-27] <--> [10-18] <--> [1-9]

Each node stores a maximum of 9 digits (999,999,999 is the largest allowed value for a node).

My issue occurs on numbers in which involve multiple nodes, hence why Fib#46 wont' work because it is the sum of:
Fib#44 = 701,408,733
Fib#45 = 1,134,903,170

I figure my issue (segfaulting by the way), is a result of attempting to access non existing nodes, but I'm not 100% sure where it is.

***Note: within my code I use var_name.empty(), our .empty function returns 1 if not empty and 0 if empty hence the weird counter intuitive logic.

Does anyone have any suggestions for what I can do?

#include <iostream>
#include <iomanip>
#include "list.h" //My doubly linked list class


List calcSum(List lhs, List rhs)
{
	List sum;
	
	sum.insert(0,0);
	
	int v1, v2, nodeSum;
	int temp1, temp2, tempSum;
	
	while (lhs.empty())
	{
		//Retrieve last position value
		temp1 = lhs.getNumItems() - 1;
		temp2 = rhs.getNumItems() - 1;
		tempSum = 0;
		
		//Retrieve item at end of each list (least significant num)
		if (lhs.empty())
			v1 = lhs.getData(temp1);
		else
			v1 = 0;
		
		if (rhs.empty())
			v2 = rhs.getData(temp2);
		else
			v2 = 0;
			
		nodeSum = sum.getData(0);
		
		//Remove the last nodes
		lhs.remove(temp1);
		rhs.remove(temp2);
		sum.remove(0);

		nodeSum += (v1 + v2);
		
		if (nodeSum >= 1000000000)
		{
			int intQuotient = nodeSum / 1000000000;
			sum.insert(nodeSum % 1000000000, 0);
			sum.insert(intQuotient, 0);
		}
		else
		{
			cout << "inserting " << nodeSum << endl;
			sum.insert(nodeSum, 0);
		}
	}
	
	return sum;
}

int main(int argc, char** argv)
{
	int fibNum;
	
	if (argc == 2)
	{
		char* value = argv[1];
		fibNum = atoi(value);
	}
	else
	{
		cout << "Enter a fibonacci number to find: ";
		cin >> fibNum;
	}
	
	List f1, f2, f3;
	f1.insert(1,0);
	f2.insert(1,0);

	for (int i = 3; i <= fibNum; i++)
	{
		f3 = calcSum(f2, f1);
		f1 = f2;  //f1 becomes f2
		f2 = f3; //f2 becomes 'f3'
		//f(n) = f(n-1) + f(n-2)
	}
	
	while (f3.empty())
	{
		int loc = f3.getNumItems() - 1;
		
		if (loc != 0)
			cout << setw(9) << setfill('0') << f3.getData(loc);
		else
			cout << f3.getData(loc);
			
		f3.remove(loc);
	}
	
	return 0;
}

[Gkneeus]

Sorry if I am totally wrong but I did not bother to read the program.

you said

My issue occurs on numbers in which involve multiple nodes, hence why Fib#46 wont' work because it is the sum of:
Fib#44 = 701,408,733
Fib#45 = 1,134,903,170 

why don't you just use long, or if you need to long long.

[Kevin2341]

Because when you read numbers like the Fib#1000, or Fib#5000, you have several hundreds of digits that cannot be represented by unsigned long long ints.

And also the goal is to store the large numbers in a linked list

[cire]

The normal way to do this would be to use a:

class BigInt
{
public:

private:
    // internals none of the client code has to know about
    // we may make use of any container here
};

with appropriate operations defined or operators overloaded. Where the goal is to treat a BigInt like a number and not something stored in a linked list.

That said, in your calcSum function you seem to take some delight in accessing members of a list for which the method empty returns true. Seems suspicious.