开发学院软件开发VC 可用于数论计算的无符号大整数类 阅读

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

 2010-01-23 20:32:23 来源:WEB开发网   
核心提示:四、数据的输出定义了ToDecStr()和ToHexStr()两个成员分别用于将其转换为十进制和十六进制字符串输出,五、处理0除和越界异常自定义了一个CMyException异常类,可用于数论计算的无符号大整数类(2),越界是指由于机器字长的影响,使得内存(包括虚拟内存)的大小有限,6、根据商1的位数,得到应相减的减数

四、数据的输出

定义了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、返回结果。

Tags:用于 数论 计算

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接