一个大整数类
4.61/5 (17投票s)
大整数类行为类似于内置类型
引言
本文档旨在为他人提供 `LargeInteger` 类。此类能够处理包含数千位甚至更多位数字的整数值。该类重载了所有数学、逻辑、移位和比较运算符，以便可以在表达式中使用该类。此类还为基本的有符号和无符号整数类型提供了构造函数和等于运算符。
理论上最长的整数长度是 231 - 1 个 `dword`，其中 `dword` 是 4 字节。此限制是因为，在代码的某些地方，32 位 `dword` 数组的无符号整数索引被转换为有符号整数。这会将最大数字设置为 233 - 4 字节长，或大约 80 亿字节长！
此限制在我今天的任何计算机上都不是问题，因为实际的时间和内存限制将在远远超出此理论限制之前限制最大整数长度。
目前没有错误检查代码来查看最大索引值是否超过限制。如果这是个问题，请通过将参数设置为 `0` 来调用 `GetBinaryValue` 方法来检查数字的长度。下面有一个如何使用此方法的示例。
此外，该类还提供了从 `string` 或缓冲区设置大整数以及获取大整数内容的方法。
该类还重载了 `istream` 和 `ostream` 方法。目前，`istream` 方法尚未经过测试。将非常长的整数输入大整数的最实用方法是使用包含整数值的 `null` 终止字符 `string`。下面有一些如何执行此操作的示例。
背景
我写这个类已经超过 15 年了。我没有完成所有代码的调试，就把代码放在了一边。我只在几周前才重新开始工作。代码中使用的一些算法，例如将十进制值转换为八进制的方法，来自 Knuth 的“Seminumerical Algorithms”。
我将继续改进此代码。目前，代码仅适用于 ASCII 构建。此外，乘法方法是一个简单的 O(n2) 方法，对于只有几千位数字的乘数来说还可以，但对于一百万位数字的数字来说太慢了。最终，我将采用 Schönhage-Strassen 算法或非常相似的算法，这将允许在合理的时间内计算非常大的整数的乘法。
文件列表
- TLargeInteger.cpp - 一个简单的大整数测试程序
- LargeInteger.cpp - 大整数类实现文件
- LargeInteger.h - 大整数类定义文件
- TLargeInteger.vcproj - Visual Studio 2008 项目文件
- TLargeInteger.sln - Visual Studio 2008 解决方案文件
关于代码
该代码提供了如何在 C++ 中重载算术和逻辑运算的示例。
以下运算符方法实现了以单个 `LargeInteger` 作为参数的基本算术运算。
operator +=(const LargeInteger & addend);
operator -=(const LargeInteger & subtrahend);
operator *=(const LargeInteger & addend);
operator /=(const LargeInteger & multiplier);
所有其他算术运算符都基于这些方法实现。为了使其更清晰，下面展示了其他乘积运算符的实现，它们无论是直接还是间接使用 `operator *=`。
//======================================================================
// 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;
}
我认为这是最简单的实现，但并不一定是最高效的实现方法。
逻辑运算也做了同样的事情。请参阅代码中的 `operator |=` 示例。
Using the Code
在 C++ 文件中包含 `LargeInteger.h` 文件后，以下是一些将 `LargeInteger` 设置为某个值的方法。
// 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);
以下是一些获取或显示大整数中数字的方法。
// 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);
}
计算就像其他内置类型一样进行。
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;
如果发生内存分配错误、`LargeInteger` 除数导致的除零错误或其他错误，则会抛出 `LargeIntegerException`。`LargeIntegerException` 类定义在 `LargeInteger.h` 文件中，并派生自 `std::exception`。使用单一异常类型处理多种错误类别相当简单。将来，我可能会通过提供更多异常类来改进异常代码。所有此类类都将派生自 `LargeIntegerException`，以便使用当前 `LargeInteger` 类的客户端代码无需修改。
关注点
由于以下测试用例，我在调试乘法代码时花费了不必要的额外时间
C9F2C9CD04674EDEA40000000 = 38D7EA4C68000 * 38D7EA4C68000
请注意，两个乘数相同，并且都以 `000` 结尾。我省略了这些零以使数字变小，并使用 Windows 上的计算器程序（选择十六进制模式）来计算以下乘积。
38D7EA4C68 * 38D7EA4C68
计算器显示的产品是“2C9CD04674EDEA4”，这与我的程序的結果不符。我的测试程序是正确的，WindowsTM 计算器会默默地截断结果！
WindowsTM 计算器中显示的结果（截断后的答案）可以在结果中看到
C9F2C9CD04674EDEA40000000
历史
- 初次发布
- 更新了代码以修复乘法和除法运算中的符号问题