可用于数论计算的无符号大整数类

一起学习

可用于数论计算的无符号大整数类


作者/缪元虎

下载源代码


前些日子，无意中访问到三思科学网，里面介绍了许多数论问题，这也是我儿时的爱好，于是就利用空闲时间编写了一个用于数论计算的无符号大整数类。

一、类的基本结构

Class CUSuperInt

{

public:

       //构造及析构函数

       CUSuperInt();

       CUSuperInt(DWORD dwValue);

       CUSuperInt(char* pszVal);

       CUSuperInt(CUSuperInt& x);   

       virtual ~CUSuperInt();

protected:

       DWORD *pValue;         //指向一个DWORD数组，用于存放数值

       DWORD len;                //DWORD数组的长度

       DWORD last;               //数组中的有效长度

};      

类名为CUSuperInt，第二个字母表示无符号的意思。当然只要你通过增加一个表示符号的成员，再经简单扩充即可变成有符号大整数类。
pValue指向的DWORD数组采用动态分配策略，当数组长度不够时，采用成倍分配的策略，即长度变为2*len。(这也许不是一个最好的分配方案，但可以简化设计)
last成员指示数组中数据的有效长度，这样可以减少一些不必要的运算量。last成员最小值为1，当last＝1时实际就已蜕变为了一个DWORD了。

二、构造函数
类定义了四个构造函数，其中有一个构造函数的参数是一个字符串指针，它表示将一个字符串转换为一个CUSuperInt类。这样的字符串可以是十进制或十六进制的字符串，表示方式跟C语言的规范差不多，如"12345678901"，"0x123456789abcdef"，前者表示十进制数，后者表示十六进制数。同时为了在应用中方便，也允许数字字符串中间用空格来分节，如"12345 567890"、"0x123 4567 89ab cdef"等。

三、重载运算符
重载了赋值运算符，可以将DWORD，字符串，以及CUSuperInt赋值给一个CUSuperInt对象。
重载了加减乘除等四则运算，以及＋＋，――运算符。不过注意对于/=运算返回值为余数，商在左操作数中。而对于/运算返回商，余数丢失。
重载了%运算符，可以计算模。
重载了比较运算符，可以进行比较运算，返回一个bool值。
定义了一个Dobule()成员用于乘以2的n次方,有用逻辑左移算法。
定义了一个Half()成员用于除以2的n次，采用逻辑右移算法，所以这个函数将丢失余数。

四、数据的输出
定义了ToDecStr()和ToHexStr()两个成员分别用于将其转换为十进制和十六进制字符串输出。

五、处理0除和越界异常
自定义了一个CMyException异常类。
越界是指由于机器字长的影响，使得内存(包括虚拟内存)的大小有限，自定义了一个上界，当数据越过时抛出一个越界异常。
事实上一个win32程序可用的内存空间名义上有4G，实际除了操作系统和一些额外开销，不足2G，一个DWORD占4字节，所以最大长度为2G/4= 0x20000000;加上要运算，肯定有多个数，考虑MaxLen为0x1000000比较合适，这时能表示的数表示成十进制数能超过1.6亿位，已经非常大了。这个长度计算公式是MaxLen * 32位 * log(2) / log(10) 1;

六、使用
如同整数一样可以进行加减乘除四则运算和比较。如果你处理的数很大时，一般建议你在程序中要处理异常。例子代码见源程序。另外建议将你的程序优先级设置得低些，因为数值运算是非常耗CPU资源的。

七、优化
优化要从算法和代码上进行。在代码上，核心代码尽量用内联汇编代码编写，以提高速度。对于一些经常使用的函数，可以考虑采用VC和汇编混合编写的方法，程序中使用了这样一个例子，即对meccpy函数用汇编编写。（系统提供的这个函数因为要考虑按DWORD对齐的问题，使得代码长了一些。但本程序中不用考虑这个问题，所以重新编写。当然也可使用内联汇编的方式，但从编译得到的汇编代码看，在函数体内开始几句语句有点多余。所以用纯汇编编写更加简单）
在算法上，由于作者水平有限，参考书籍也有限，不能找到最好的算法。下面简单介绍一下除法
和ToDecStr()采用的算法。

除法采用二进制除法：

它是这样进行的（设被除数为a，除数为x，商为r）：

• 1、 首先计算r的长度并扩展，令r.last为计算得到的长度，还要将r.pValue指向的DWORD数组清0。
• 2、 建立一个减数数组XX[32], 其值依次为x,，2*x,，4*x，8*x，……
• 3、 如果a
• 4、 根据a和x的长度，计算出r的最高可能商十进制1的位数。然后判断该位能否商1
• 5、 如果不能商1，则r的下一位肯定能商1。
• 6、 根据商1的位数，得到应相减的减数数组号nXX
• 7、 a的高n个DWORD减XX[nXX],(其中n为XX[nXX]的有效长度)。
• 8、 r的相应位置1
• 9、 跳到上面的第3步
• 10、 返回结果。

ToDecStr()的算法分析：

基本算法是将数除以10，得到的余数为最低位。这样反复进行，直到结束，就可计算结果。
但对于一个长度很长的CUSuperInt对象，除法是非常耗时间的，为了尽量减少除法的次数，将除数设为1000000000（这根据一个DWORD能表示的最大十进制数为429467295，其位数有10位而定的），这样每除一次，得到的余数是一个不大于9位十进制位的数，然后将其转换成十进制字符串，作为低9位。

八、问题
各种运算的正确性，尚需在使用过程中得到进一步的验证。因为数大了，我们不大可能用手工或计算器来验证，所以只能从算法上保证运算的正确性。
进一步的优化，如对两个CUSuperInt相乘，可以全部用内联汇编编写。
由于代码中使用了大量的汇编，而在代码中未涉及段寄存器，适用的程序只能是Win32程序。（作者水平有限，不知做出这样的判断是否正确，请读者指正）。
本代码在VC6.0＋WinMe以及WinXP环境下调试运行正确。

　 下载本文示例代码


可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类可用于数论计算的无符号大整数类