A Large Integer Class

• Download source - 24.3 KB

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 2³¹ - 1 dwords, 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 dwords is cast to be a signed integer. This sets the maximum number to be 2³³ - 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(n²) 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:

//======================================================================
// operator * for integral types.
//======================================================================

//======================================================================
// Multiplication of two instances of this class.
//======================================================================

LargeInteger operator *(const LargeInteger & multiplier_a,
                       const LargeInteger & multiplier_b)
{
   return LargeInteger(multiplier_a) *= multiplier_b;
}

//======================================================================
// Multiplication of an instance of the LargeInteger class and a signed integer.
//======================================================================

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;
}

//======================================================================
// Multiplication of an instance of the LargeInteger class and an unsigned integer.
//======================================================================

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.

// Use a large integer constructor to set 'a' to negative 20.

LargeInteger a = -20;

// Declaring x results in x = 0;

LargeInteger x;

// Increment x to be the value 1.

x++;

// User an equals operator to set x to 123

x = 123;

// User an equals operator to set x to a large magnitude negative number in base 10.

x = "-12345678901234567890123456789012345678901234567890";

// Change the default base to be base 16.  The SetDefaultBase method 
//only affects the constructor and operator equals method that take
a single null-terminated string for their only argument.

x.SetDefaultBase(16);

// User an equals operator to set x to a large number in base 16.

x = "FFFFFFFF00000000FFFFFFFF123456789ABCDEF";

// Another way to set x to the value above.

x.SetValue("FFFFFFFF00000000FFFFFFFF123456789ABCDEF");

// Set the internal number to the binary number 0x07FFFFFFFFFFFFFFFFFFF using
// the SetBinaryValue method.

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.

// After including <iostream>, dump the value one of the ways shown.

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;

//------------------------------------------------------------
// After including <string> in your C++ file, use
// the GetNumberString method.
//-----------------------------------------------------------

std::string number_string;
unsigned int base = 10

x.GetNumberString(number_string, 10);

std::cout << "x = " << number_string.c_str() << std::endl;

//------------------------------------------------------------
// Get a copy of the binary data inside of the LargeInteger
// using the GetBinaryValue method.
//
// First find the required buffer length by passing 0
// for the argument to the GetBinaryValue method.
//------------------------------------------------------------

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 Windows^TM calculator silently truncates the result!

The truncated answer displayed in the Windows^TM calculator can be seen in the result:

C9F2C9CD04674EDEA40000000 

History

• Initial post
• Updated code to fix sign issue in the multiplication and division operations