Click here to Skip to main content
Click here to Skip to main content

A Large Integer Class

, 5 Nov 2013 MIT
Rate this:
Please Sign up or sign in to vote.
Large Integer class acts similar to built-in type

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 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 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:

//======================================================================
// 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 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

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

Bill_Hallahan
Software Developer (Senior)
United States United States
I'm an electrical engineer who has spend most of my career writing software. My background includes Digital Signal Processing, Multimedia programming, Robotics, Text-To-Speech, and Storage products. Most of the code that I've written is in C, C++ and Python. I know Object Oriented Design and I'm a proponent of Design Patterns.
 
My hobbies include writing software for fun, amateur radio, chess, and performing magic, mostly for charities.

Comments and Discussions

 
Buganother bug..... Pinmemberpeilinok14-Oct-14 22:11 
BugBug in void GetBase10NumberString() Pinmemberpeilinok7-Oct-14 22:27 
GeneralRe: Bug in void GetBase10NumberString() PinmemberBill_Hallahan9-Oct-14 16:23 
GeneralRe: Bug in void GetBase10NumberString() PinmemberRosenthal Esq.20-Nov-14 6:45 
QuestionWrong multiplication and division of negative numbers PinmemberMember 109934045-Aug-14 9:27 
AnswerRe: Wrong multiplication and division of negative numbers PinmemberBill_Hallahan8-Aug-14 19:35 
AnswerRe: Wrong multiplication and division of negative numbers [modified] PinmemberBill_Hallahan5-Sep-14 16:12 
QuestionTesting PinmemberFrans_5512912-Nov-13 3:58 
AnswerRe: Testing PinmemberBill_Hallahan12-Nov-13 14:51 
GeneralNice work and a few comments [modified] PinmemberDezhi Zhao5-Nov-13 18:58 
GeneralRe: Nice work and a few comments [modified] PinmemberBill_Hallahan6-Nov-13 13:52 
QuestionNice but how do you test? PinmemberAxel Rietschin3-Nov-13 21:26 
AnswerRe: Nice but how do you test? PinmemberBill_Hallahan4-Nov-13 13:50 
GeneralMy vote of 4 PinprofessionalPaulo Zemek3-Nov-13 18:55 
GeneralRe: My vote of 4 PinmemberBill_Hallahan4-Nov-13 13:50 
QuestionConfused PinprofessionalPaulo Zemek3-Nov-13 18:33 
AnswerRe: Confused PinmemberNemanja Trifunovic4-Nov-13 8:13 
GeneralMessage Removed PinmemberBill_Hallahan4-Nov-13 13:44 
GeneralRe: Confused PinmemberNemanja Trifunovic4-Nov-13 15:51 
AnswerRe: Confused PinmemberBill_Hallahan4-Nov-13 16:54 
GeneralRe: Confused PinprofessionalPaulo Zemek5-Nov-13 2:48 
GeneralRe: Confused PinmemberBill_Hallahan5-Nov-13 13:44 
GeneralRe: Confused PinprofessionalPaulo Zemek5-Nov-13 14:07 
GeneralRe: Confused [modified] PinmemberBill_Hallahan5-Nov-13 15:06 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141220.1 | Last Updated 5 Nov 2013
Article Copyright 2013 by Bill_Hallahan
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid