Introduction
This article is to provide the LargeInteger
class for use by others. This class provides the ability to have integer values that are thousands of digits long, or longer. The class overloads all mathematical, logical, shift, and comparison operators, so that the class can be used in expressions. The class also has both constructors and equals operator for the basic signed and unsigned integer types.
The theoretical longest integer length is 231 - 1 dword
s, where a dword
is 4 bytes. This limitation is because, in some places in the code, the unsigned integer index into an array of 32-bit dword
s is cast to be a signed integer. This sets the maximum number to be 233 - 4 bytes long, or approximately 8 billion bytes long!
This limitation is not an issue on any computer I have today, because other practical concerns involving both time and memory limit the maximum integer length well before this theoretical limit will be reached.
There's currently no error checking code to see if the maximum index value exceeds the limit. If this is a concern, check the length of the number by calling the GetBinaryValue
method with an argument of 0
. There is an example of how to use this method below.
In addition, the class provides methods to set the large integer from either a string
or a buffer, and to get the large integer contents.
The class also overloads istream
and ostream
methods. At present, the istream
methods are not tested. The most practical way to enter a very long integer into a large integer is to use a null
-terminated character string
that contains the integer value. There are examples of how to do this below.
Background
I wrote this class over 15 years ago. I didn't finish debugging all of the code, and put the code aside. I only started working on it again a few weeks ago. Some of the algorithms used in the code, such as the way to convert base 10 values to base 8, are from Knuth's "Seminumerical Algorithms".
I will be working on this code to improve it further. Currently, the code only works for ASCII builds. Also, the multiplication method is a simple O(n2) method, which is okay for multiplicands with a few thousand digits, but too slow for numbers with a million digits. Eventually, I'll be incorporating the Schönhage-Strassen algorithm, or something very similar, which will allow multiplying very large integers in a reasonable amount of time.
List of Files
- TLargeInteger.cpp - A simple large integer test program
- LargeInteger.cpp - The large integer class implementation file
- LargeInteger.h - The large integer class definition file
- TLargeInteger.vcproj - A Visual Studio 2008 Project file
- TLargeInteger.sln - A Visual Studio 2008 Solution file
About the Code
The code provides an example of how to overload arithmetic and logical operations in C++.
The following operator methods implement the basic arithmetic operations that take a single LargeInteger
as an argument.
operator +=(const LargeInteger & addend);
operator -=(const LargeInteger & subtrahend);
operator *=(const LargeInteger & addend);
operator /=(const LargeInteger & multiplier);
All other arithmetic operators are implemented in terms of these methods. To make this clearer, the implementation for other product operators, all that either directly, or indirectly, use operator *=, are shown below:
LargeInteger operator *(const LargeInteger & multiplier_a,
const LargeInteger & multiplier_b)
{
return LargeInteger(multiplier_a) *= multiplier_b;
}
LargeInteger operator *(const LargeInteger & x_multiplier,
int multiplier)
{
return x_multiplier * LargeInteger(multiplier);
}
LargeInteger operator *(int multiplier,
const LargeInteger & x_multiplier)
{
return x_multiplier * multiplier;
}
LargeInteger operator *(const LargeInteger & x_multiplier,
unsigned int multiplier)
{
return x_multiplier * LargeInteger(multiplier);
}
LargeInteger operator *(unsigned int multiplier,
const LargeInteger & x_multiplier)
{
return x_multiplier * multiplier;
}
I believe this is the simplest implementation, although not necessarily the most efficient way to implement the operations.
The same thing is done for logical operations. See operator |=
in the code for one example.
Using the Code
After including file LargeInteger.h in your C++ file, here are some ways to set a LargeInteger
to a value.
LargeInteger a = -20;
LargeInteger x;
x++;
x = 123;
x = "-12345678901234567890123456789012345678901234567890";
a single null-terminated string for their only argument.
x.SetDefaultBase(16);
x = "FFFFFFFF00000000FFFFFFFF123456789ABCDEF";
x.SetValue("FFFFFFFF00000000FFFFFFFF123456789ABCDEF");
char number_array[10] = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F };
x.SetBinaryValue(&number_array[0], 10);
Here are some ways to either get or display the number in a large integer.
std::cout << "Base 10 value of x = " << x << std::endl;
std::cout << "Base 8 value of x = " << std::oct << x << std::endl;
std::cout << "Base 10 value of x = " << std::dec << x << std::endl;
std::cout << "Base 16 value of x = " << std::hex << x << std::endl;
std::string number_string;
unsigned int base = 10
x.GetNumberString(number_string, 10);
std::cout << "x = " << number_string.c_str() << std::endl;
unsigned int length = x.GetBinaryValue(0);
char * buffer_ptr = new char [length];
if (buffer_ptr != 0)
{
x.GetBinaryValue(buffer_ptr);
}
Calculations are done like any other built-in type.
LargeInteger x = "12345678901234567890"
unsigned int y = 4;
LargeInteger z = x * y;
z = z + 42;
LargeInteger k = "987654321098765432109876543210987654321";
z = z - k;
z = -z / 5;
LargeInteger divisor = "123456789";
x = z / divisor;
If a memory allocation error, a divide-by-zero error with a LargeInteger
divisor, or other errors occur, then a LargeIntegerException
will be thrown. The LargeIntegerException
class is defined in file LargeInteger.h and is derived from std::exception
. It's somewhat simplistic to use a single exception type for multiple categories of errors. In the future, I might improve the exception code by providing more exception classes. All such classes will be derived from LargeIntegerException
, so that client code that uses the current LargeInteger
class won't have to be modified.
Points of Interest
I spent unnecessary extra time debugging the multiplication code because of the following test case:
C9F2C9CD04674EDEA40000000 = 38D7EA4C68000 * 38D7EA4C68000
Notice the two multiplicands are the same, and end in 000
. I omitted those zeros to make the numbers smaller and I used the calculator program on Windows, with hex-mode selected, to compute the following product.
38D7EA4C68 * 38D7EA4C68
The calculator displayed the product "2C9CD04674EDEA4
", which doesn't match the result of my program. My test program is correct, the WindowsTM calculator silently truncates the result!
The truncated answer displayed in the WindowsTM calculator can be seen in the result:
C9F2C9CD04674EDEA40000000
History
- Initial post
- Updated code to fix sign issue in the multiplication and division operations