关于超大整数的四则运算

Santa — Sun, 06 May 2007 02:07:00 GMT

有的时候我们需要处理超出int，甚至是int64范围的数字，而用浮点型数字又会存在精度问题，所以就需要设计一种可以存储超大（无上限）的整数的数据结构。前不久我把整个库写出来了，在这里贴一点设计思路。

首先，数字的保存使用int数组。我们所理解的整数表达方式都是10进制的，不过我把进制调整到了10000，就是说数组的每个元素保存了0～9999的一个数字。为什么不用更高的进制呢？比如结合int的上限设计到100000000？这是为了防止在乘法中出现溢出。当然如果想要节省空间，那么设计1亿的上限也还行，不过在乘法时就要做一些有技巧性的处理，会降低效率。因此就只好“空间换时间”了。^_^

然后，数字就从高位到地位保存起来。num[0]保存的相当于“个位”，指标越高保存的位数越高。再用一个bool标识正负号。这样数据结构就差不多了。

接下来要处理输入输出。输出很简单，首先把最高位输出。注意，开头如果是0的话要跳过不输出。但是如果整个数字就刚好是0，那么就要特别小心，注意判断长度。此外还有“-0”这样的情况，小心应付。输出高位之后，地位的数字先转化为字符串（用itoa），然后在前面加0，补足4位。输出注意处理负号。相对而言，输出相当相当容易，小心应付各种可能的输出情况就好了。而输入是很难的，因为我设计的时候考虑到了使用科学记数法输入的方式，比如7.45E+90等等。这样的情况太多了，以至于写了80多行代码就是为了处理输入……列举几个比较麻烦的例子：0E0, 0E+0, 0E-0, +0E0, +0E-0, 7.80000000000000e0000000008,000009.6767E89, 988000000e-3……

加减法也很简单，注意进位借位就行了。其实只要把加法写好了，减法就是a+(-b)而已。

核心是乘法。我们小学时用的乘法是O(n^2)时间的，如果数字位数比较大就很慢了，我曾经试过1千位的两个数字相乘，大约花了10秒钟，已经很慢了。曾经有高手提起过FFT（Fast Fourier Transformation，快速傅立叶变换），这种算法可以在O(nlogn)时间内完成，也就是说两个1千位的数字相乘可以在毫秒级别完成，相当理想的算法！但是我知道现在还是没有找到这个算法的详细内容，如果看此贴的朋友了解的话，麻烦传授一下，谢了！我现在用的是Divide and Conquer（分治），时间复杂度O（n^1.58），相对传统算法快了一点点，1千位数的乘法可以在500毫秒内完成，还算凑合吧……

除法（还有求余数），则是在乘法的基础上发展的。其实就是“猜测”的办法。从位数估计出商的上下限，然后用2分。复杂度比乘法高logn量级。注意可以先判断一下除数是不是10的整数次幂，如果是的话直接移动数组元素即可。10整数次幂的乘法也应当用移位实现，O(n)时间，最快。

Santa 2007-05-06 10:07 发表评论

First touch of MFC

Santa — Sat, 05 May 2007 15:25:00 GMT

今天写了有生以来的第一个MFC程序，一边看着MSDN一边写……
不过写的好勉强啊……为了将word文本转换成txt，我就用模拟鼠标点击来操纵整个菜单……
这算是开了个头了，以后再加油……

Santa 2007-05-05 23:25 发表评论

Trying Ubuntu

Santa — Sun, 29 Apr 2007 01:09:00 GMT

昨晚好不容易把Ubuntu装上了，感觉挺好，英文版很漂亮，而且功能应该是很强的吧。要开始学bash了呢。

Santa 2007-04-29 09:09 发表评论

C++博客-Santa's Tech-Blog

关于超大整数的四则运算

First touch of MFC

Trying Ubuntu