Optimizing manipulation of large arrays and odd behavior with overloaded operator

[krellor]

I haven't wrote in C++ for a long time so I decided to brush up a bit by writing some basic programs. I wrote a class that allows for basic arithmetic of infinitely large numbers (or as much as you have memory for). Here is the code.

class largeInt
{
	friend ostream &operator<<(ostream&, const largeInt &);
	friend largeInt operator+(const largeInt&, const largeInt&);
	friend largeInt operator+(const largeInt&, const string&);
	friend largeInt operator*(const largeInt&, const largeInt&);

	public:
		largeInt(long = 0);
		~largeInt();
		void setInt(unsigned long long int);
		void setInt(string);
	private:
		std::vector <short int> num;
};

largeInt operator+(const largeInt &x, const largeInt &y)
{
	long i = 0;	
	long xPower = x.num.size(), yPower = y.num.size();	
	short int intTemp = 0, intCarry = 0;	 
	largeInt result;			
	vector <short int> xLocal;
	vector <short int> yLocal;

	result.num.clear();	
	xLocal = x.num;	
	yLocal = y.num;	

	if(xPower > yPower)	
	{
		do{	
			yLocal.push_back(0);	
			++yPower;
		}while(xPower > yPower);
	}
	else if(yPower > xPower)		
	{								
		do{
			xLocal.push_back(0);
			++xPower;
		}while(yPower > xPower);
	}

	for(i = 0;i < xPower; ++i)							
	{													
		intTemp = xLocal[i] + yLocal[i] + intCarry;		
		if(9 < intTemp)									
		{
			result.num.push_back(intTemp - 10);
			intCarry = 1;
		}
		else
		{
			result.num.push_back(intTemp);
			intCarry = 0;
		}

		if((xPower - 1) == i && 0 != intCarry)			
		{												
			result.num.push_back(intCarry);
		}
	}
	return result;
}

largeInt operator*(const largeInt &x, const largeInt &y)
{
	long i = 0,j = 0, k = 0, m = 0, z = 0;				
	long xPower = x.num.size(), yPower = y.num.size();	
	short int intTemp = 0, intCarry = 0;				
	largeInt result;									
	string strTemp;									
	stringstream sstTemp;				
	vector <short int> xLocal;					
	vector <short int> yLocal;				
	vector <short int> rLocal;
							
	result.num.clear();				
	xLocal = x.num;					
	yLocal = y.num;					

	if(xPower > yPower)				
	{								
		do{							 
			yLocal.push_back(0);	
			++yPower;
		}while(xPower > yPower);
	}
	else if(yPower > xPower)	
	{								
		do{
			xLocal.push_back(0);
			++xPower;
		}while(yPower > xPower);
	}

	for(i = 0; i < xPower; ++i)						{													
		for(k = 0; k < yPower; ++k)
		{
			rLocal.push_back(xLocal[i] * yLocal[k]);	
		}
	}

	switch (xPower)						
	{									
		case 1:							
			m = k = 0;					
			break;						
		case 2:							
			m = k = 2;						
			break;
		default:
			m = k = xPower + (xPower - 2);
			break;
	}
	for(i = (long)pow(xPower,2.0); i > 0; --i)
	{
		if(i%xPower == 0)				
		{								
			k = m - j;					
			++j;						
		}								
		else							
		{								
			--k;
		}								
		
		strTemp.clear();				
		sstTemp.str("");				
		sstTemp << rLocal[i-1];			
		strTemp = sstTemp.str();		
		if("0" != strTemp)				
		{
			for(z = 0;z < k; ++z)
			{
				strTemp.append("0");	
			}							
		}
		result =  result + strTemp;		
	}
	return result;						
}

In the code above I have the class declaration, and the overloaded addition and multiplication operators. My first question is about odd behavior when using the addition operator. In the driver function:

int main(void)
{
	largeInt x,y;
	x.setInt(3);
	cout << x + 2 << endl;
	return(0);
}

I am adding an integer to a type largeInt, but I have not created an overloaded method that accepts largeInt and numerics as input, only one that inputs largeInts and strings. It compiles and runs fine without even a warning. I am wondering what obvious underpinning of C++ I am forgetting. Is the number being treated as a string and therefore being passed to the other overloaded method? Or is some other default behavior occurring that I am unfamiliar with.

Finally, I am wondering what could be done to speed this code up. It has an awful lot of nested loops, and on large problems is quite slow. For example the following driver function to find 100!

int main(void)
{
	int i = 0;
	largeInt x,r;
	r.setInt(1);
	for(i = 100;i > 0; --i)
	{
		x.setInt(i);
		r = r * x;
		cout << i << ":\t" << r << endl;
	}
	return(0);
}

will take around 7 minutes to run. On windows calculator it takes a fraction of a second. I realize that they are probably doing vastly different things in order to work that fast, but I am curious as to how they deal with such large numbers so quickly, as well as what I could to with this code as is to make it a little bit faster.

This is all a learning exercise for me, so all suggestions are welcome.

Here is a link to a version of the code with comments:
http://shadowsprite.com/files/utils/main.cpp

I included them while making this post but because of width constraints, just made it harder to read.

[Tom Gunn]

I am adding an integer to a type largeInt, but I have not created an overloaded method that accepts largeInt and numerics as input, only one that inputs largeInts and strings. It compiles and runs fine without even a warning.

The largeInt class has an implicit constructor that takes a long type as the parameter. You typed cout << x + 2 << endl; , but what actually happens is cout << x + largeInt(2) << endl; .

[krellor]

I see, thanks for answering that. I knew something must be going on that I couldn't remember. :) So if I were to remove the constructor or the 'long = 0' then it would no longer work I guess. Thanks a bunch.