C++ RSS C++ RSS

Optimizing manipulation of large arrays and odd behavior with overloaded operator

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Dec 2008
Posts: 12
Reputation: krellor is an unknown quantity at this point 
Solved Threads: 0
krellor krellor is offline Offline
Newbie Poster

Optimizing manipulation of large arrays and odd behavior with overloaded operator

 
0
  #1
Sep 14th, 2009
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.

C++ Syntax (Toggle Plain Text) 
  1. class largeInt
  2. {
  3. 	friend ostream &operator<<(ostream&, const largeInt &);
  4. 	friend largeInt operator+(const largeInt&, const largeInt&);
  5. 	friend largeInt operator+(const largeInt&, const string&);
  6. 	friend largeInt operator*(const largeInt&, const largeInt&);
  7.  
  8. 	public:
  9. 		largeInt(long = 0);
  10. 		~largeInt();
  11. 		void setInt(unsigned long long int);
  12. 		void setInt(string);
  13. 	private:
  14. 		std::vector <short int> num;
  15. };
  16.  
  17. largeInt operator+(const largeInt &x, const largeInt &y)
  18. {
  19. 	long i = 0;	
  20. 	long xPower = x.num.size(), yPower = y.num.size();	
  21. 	short int intTemp = 0, intCarry = 0;	 
  22. 	largeInt result;			
  23. 	vector <short int> xLocal;
  24. 	vector <short int> yLocal;
  25.  
  26. 	result.num.clear();	
  27. 	xLocal = x.num;	
  28. 	yLocal = y.num;	
  29.  
  30. 	if(xPower > yPower)	
  31. 	{
  32. 		do{	
  33. 			yLocal.push_back(0);	
  34. 			++yPower;
  35. 		}while(xPower > yPower);
  36. 	}
  37. 	else if(yPower > xPower)		
  38. 	{								
  39. 		do{
  40. 			xLocal.push_back(0);
  41. 			++xPower;
  42. 		}while(yPower > xPower);
  43. 	}
  44.  
  45. 	for(i = 0;i < xPower; ++i)							
  46. 	{													
  47. 		intTemp = xLocal[i] + yLocal[i] + intCarry;		
  48. 		if(9 < intTemp)									
  49. 		{
  50. 			result.num.push_back(intTemp - 10);
  51. 			intCarry = 1;
  52. 		}
  53. 		else
  54. 		{
  55. 			result.num.push_back(intTemp);
  56. 			intCarry = 0;
  57. 		}
  58.  
  59. 		if((xPower - 1) == i && 0 != intCarry)			
  60. 		{												
  61. 			result.num.push_back(intCarry);
  62. 		}
  63. 	}
  64. 	return result;
  65. }
  66.  
  67. largeInt operator*(const largeInt &x, const largeInt &y)
  68. {
  69. 	long i = 0,j = 0, k = 0, m = 0, z = 0;				
  70. 	long xPower = x.num.size(), yPower = y.num.size();	
  71. 	short int intTemp = 0, intCarry = 0;				
  72. 	largeInt result;									
  73. 	string strTemp;									
  74. 	stringstream sstTemp;				
  75. 	vector <short int> xLocal;					
  76. 	vector <short int> yLocal;				
  77. 	vector <short int> rLocal;
  78.  
  79. 	result.num.clear();				
  80. 	xLocal = x.num;					
  81. 	yLocal = y.num;					
  82.  
  83. 	if(xPower > yPower)				
  84. 	{								
  85. 		do{							 
  86. 			yLocal.push_back(0);	
  87. 			++yPower;
  88. 		}while(xPower > yPower);
  89. 	}
  90. 	else if(yPower > xPower)	
  91. 	{								
  92. 		do{
  93. 			xLocal.push_back(0);
  94. 			++xPower;
  95. 		}while(yPower > xPower);
  96. 	}
  97.  
  98. 	for(i = 0; i < xPower; ++i)						{													
  99. 		for(k = 0; k < yPower; ++k)
  100. 		{
  101. 			rLocal.push_back(xLocal[i] * yLocal[k]);	
  102. 		}
  103. 	}
  104.  
  105. 	switch (xPower)						
  106. 	{									
  107. 		case 1:							
  108. 			m = k = 0;					
  109. 			break;						
  110. 		case 2:							
  111. 			m = k = 2;						
  112. 			break;
  113. 		default:
  114. 			m = k = xPower + (xPower - 2);
  115. 			break;
  116. 	}
  117. 	for(i = (long)pow(xPower,2.0); i > 0; --i)
  118. 	{
  119. 		if(i%xPower == 0)				
  120. 		{								
  121. 			k = m - j;					
  122. 			++j;						
  123. 		}								
  124. 		else							
  125. 		{								
  126. 			--k;
  127. 		}								
  128.  
  129. 		strTemp.clear();				
  130. 		sstTemp.str("");				
  131. 		sstTemp << rLocal[i-1];			
  132. 		strTemp = sstTemp.str();		
  133. 		if("0" != strTemp)				
  134. 		{
  135. 			for(z = 0;z < k; ++z)
  136. 			{
  137. 				strTemp.append("0");	
  138. 			}							
  139. 		}
  140. 		result =  result + strTemp;		
  141. 	}
  142. 	return result;						
  143. }

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:

C++ Syntax (Toggle Plain Text) 
  1. int main(void)
  2. {
  3. 	largeInt x,y;
  4. 	x.setInt(3);
  5. 	cout << x + 2 << endl;
  6. 	return(0);
  7. }

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!

C++ Syntax (Toggle Plain Text) 
  1. int main(void)
  2. {
  3. 	int i = 0;
  4. 	largeInt x,r;
  5. 	r.setInt(1);
  6. 	for(i = 100;i > 0; --i)
  7. 	{
  8. 		x.setInt(i);
  9. 		r = r * x;
  10. 		cout << i << ":\t" << r << endl;
  11. 	}
  12. 	return(0);
  13. }

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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2009
Posts: 681
Reputation: Tom Gunn has much to be proud of Tom Gunn has much to be proud of Tom Gunn has much to be proud of Tom Gunn has much to be proud of Tom Gunn has much to be proud of Tom Gunn has much to be proud of Tom Gunn has much to be proud of Tom Gunn has much to be proud of Tom Gunn has much to be proud of Tom Gunn has much to be proud of 
Solved Threads: 132
Tom Gunn's Avatar
Tom Gunn Tom Gunn is offline Offline
Practically a Master Poster

Re: Optimizing manipulation of large arrays and odd behavior with overloaded operator

 
0
  #2
Sep 15th, 2009
•
•
•
•
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; .
-Tommy (For Great Justice!) Gunn
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2008
Posts: 12
Reputation: krellor is an unknown quantity at this point 
Solved Threads: 0
krellor krellor is offline Offline
Newbie Poster

Re: Optimizing manipulation of large arrays and odd behavior with overloaded operator

 
0
  #3
Sep 15th, 2009
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.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array arrays based beginner binary bitmap c++ c/c++ calculator char char* class classes code coding compile compiler console conversion convert count data database delete deploy developer dll download dynamiccharacterarray email encryption error file forms fstream function functions game getline givemetehcodez graph gui homeworkhelp homeworkhelper iamthwee ifstream input int java lib linker list loop looping loops map math matrix memory multiple news node number numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference rpg sorting string strings temperature template text text-file tree url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC