2010-08-21 00:00:00
好久没写了。这次写前一阵子的一个大整数类，顺便请教几个问题。
目标很简单，就是实现大整数的基本算术运算。
首先，是数据存储方式问题。简单明了点可以用直接的数字字符串，但缺点是，一个字节256个信息点只用了10个（或16个，如果用16进制的话），浪费空间，而且增大了数据规模。于是考虑用尽空间，使用整个 unsigned int 作为一个单位，也就是 2^32 进制。定义如下：
1template <typename T>
2class BigIntT
3{
4protected:
5 Array<T> m_aValue;
6};
之所以搞了个 template，一是装B，二是为了模板而模板——没有 cpp，直接 include，使用方便。然后定义一个默认的特化：
1typedef BigIntT<unsigned int> BigInt;
注意这里的 T 不用 unsigned long long，是有原因的（为了方便乘法实现，见下文）。实际上如果有模板约束，我希望 T 被限制为 unsigned int, unsigned short, 以及 unsigned char。
另外，这里的数据长度将不做限制，也就是这个大数可以是任意有限的大小。各个 unsigned int 的顺序是低位在前，高位在后——这样，正好与 PC 机上的字节顺序一致，于是，整块内存布局看上去就是支持这么多字长的机器上的一个大数的内存。
我想过两种实现方式。一个是固定长度，也就是通过模板参数或者别的什么，限制其长度，也搞符号位、溢出、移位等，然后想点技巧让两个 BigInt<100> 相乘返回 BigInt<200>；二是现在的，不限长度，另有变量作为符号标记，不提供移位操作，偏算术方向。
之后，是数学运算的实现。虽然都是些小操作，但是数字一大，性能瓶颈会很突出，特别是乘除。
（完整代码见：http://xllib.codeplex.com/SourceControl/changeset/view/1689#1160）
一、加。
加法实现很直接，就是各位相加——同号的情况。每一位如果有溢出，就在后一位加1。这里指的一“位”，是指一个数据单位 T，也就是一个 unsigned int，下同。如果遇到异号的两个数，把球踢给减法。
二、减。
减法也比较直接。如果两数同号，且是大的减小的，就一位一位减。碰到有溢出的，下一位减去1。最后清除所遇的0。如果是小的减大的，就换过来减，改变下结果的符号；如果两数异号，把球踢给加法。
至此，加减实现完毕。
三、乘。
乘法的实现大致有三种：硬乘、分治法以及利用离散傅里叶变换。
由于对后两种的理解不足，现采用硬乘法。硬乘的道理很简单，就是小时候打竖式的算法（前面的加法减法也是打竖式）。被乘数的第 i 位和乘数的第 j 位的结果，要加在乘积的第 i + j 位。值得注意的是，这里每一位的乘法我用的是默认的内置类型的乘法，于是出现了上文要求，T至多只能为unsigned int，以保证这里的临时结果可以用一个unsigned long long 存下。
请教各位关于分治法以及FFT法。1、分治法看上去多了好些加减法，它带来的好处的前提是加减法实现的很好，可是按上面的加减法，似乎带不来什么好处（实际测过结果很糟，不知是否我做得不对）。2，FFT法本身我没弄很明白（很惭愧，数学系的，却从来没有会过傅里叶变换，是从来没有过，不是曾经会过现在忘了= =），不过有个疑问，FFT以及iFFT的过程本身难道不耗性能吗？
四、除和模。
除法其实也是打竖式，其实到这里为止满篇都是打竖式，哈。除法的麻烦之处是有个试商过程，试商的时候还要乘一下，看上去会很不理想。为了避免一个一个试，很自然的一个优化方法是二分，对于unsigned int 一个单位的数来说，每个单位至多会尝试32次，然后会有32次大数乘，32次大数比较。测试的情况是，对于不是特别大的数，还算马马虎虎过得去。
尝试过另外一个方式，那就是另一个极端，用真实的“位”为单位去“试商”——其实不用试，是1是0直接知道了。以为会好一些，实际上更差。初步想了想，一个原因，数据规模没变，二分试商的时候是 $$ 32n $$，现在还是 $$ 32n $$，原来的32是32次二分，现在的32是一个单位内的32次移位。除此之外，原生的unsigned int的乘除法没有被利用起来。不知是否？
后来又想到一个方法，其实不用这么多次试商，试一两次就够了，关键是利用原生的除法。比如，$$ 8000 \div 213 $$，如果我们事先已经知道了一位数的除法，在算百位上的上的时候，我们会直接考虑 $$ 8 \div 2 $$是多少，于是直接考虑商4，然后再算下 $$ 21 \times 4 $$ 有没有超过80，有的话就把商减1，商3。这个时候只进行了一次大数乘法，而商已经基本确定了。除数个位上的3，以及更低位（如果还有）上的数，即便有进位，也会加到十位，而十位的加法对百位的影响只有1，已经很难构成对最后的商的影响了。到这里，将这个数位上的商和整个除数乘起来（如果还是比被除数大，就再减一），于是这位上的上确定了。测试结果，跟二分试商相比，在2048bit级别的大数上，快了8-10倍左右。
模和除基本没什么区别，只是返回的东西不一样。
五、幂和模幂。
对于幂的实现，也用二分的思想。比如计算 $$ a^{10} $$，可以转化成先算 $$ a^{5} $$，然后自乘一次。$$ a^{5} $$，可以转化成先算 $$ a^{2} $$，然后自乘、再乘一次 a。$$ a^{2} $$，就是自乘一次。最后，变成：
$$ ((a^2)^2a)^2 $$，或者看成 $$ (((1^2a)^2)^2a)^2 $$
然后观察指数 10 的二进制表示：1010
规律是，以 1 为起始，从高位到低位看指数，遇到1就平方再乘底数，遇到0就单单平方。
至于模幂，就在每次平方前/后，把底数模一下，保证参与乘法的两个数都是“不太大”的。
以上，仅介绍我是怎么做的。至于对错、有没有更好做法，望各位不吝赐教。
最后，做了个简单的性能测试——做RSA运算：
（plain = 12345; encoded = 0; decoded = 0;）
计算以下两行的运行时间。
1encoded = plain.ExpMod(d, n);
2decoded = encoded.ExpMod(e, n);
在我机器（Win7 32bit，Intel E5200 没超频）上的测试结果如下——
512位：0.040s.
1024位：0.250s.
2048位：1.495s.
2048位的情形，已经有很明显的等待了。不知道一般来说现在2048bit的RSA性能是怎样的，一秒钟能计算多少次？
首发：http://www.cppblog.com/Streamlet/archive/2010/08/21/124133.html