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

可用于数论计算的无符号大整数类
代码下载



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

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<x，则结果已得到，进行下面第10步
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环境下调试运行正确。