好久沒寫了。這次寫前一陣子的一個大整數類，順便請教幾個問題。

目標很簡單，就是實現大整數的基本算術運算。

首先，是數據存儲方式問題。簡單明了點可以用直接的數字字符串，但缺點是，一個字節256個信息點只用了10個（或16個，如果用16進制的話），浪費空間，而且增大了數據規模。于是考慮用盡空間，使用整個 unsigned int 作為一個單位，也就是 2^32 進制。定義如下：

template <typename T>
class BigIntT
{
protected:
    Array<T> m_aValue;
};

之所以搞了個 template，一是裝B，二是為了模板而模板——沒有 cpp，直接 include，使用方便。然后定義一個默認的特化：

typedef 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直接知道了。以為會好一些，實際上更差。初步想了想，一個原因，數據規模沒變，二分試商的時候是 32 * n，現在還是 32 * n，原來的32是32次二分，現在的32是一個單位內的32次移位。除此之外，原生的unsigned int的乘除法沒有被利用起來。不知是否？

后來又想到一個方法，其實不用這么多次試商，試一兩次就夠了，關鍵是利用原生的除法。比如，8000除以213，如果我們事先已經知道了一位數的除法，在算百位上的上的時候，我們會直接考慮8除以2是多少，于是直接考慮商4，然后再算下21*4有沒有超過80，有的話就把商減1，商3。這個時候只進行了一次大數乘法，而商已經基本確定了。除數個位上的3，以及更低位（如果還有）上的數，即便有進位，也會加到十位，而十位的加法對百位的影響只有1，已經很難構成對最后的商的影響了。到這里，將這個數位上的商和整個除數乘起來（如果還是比被除數大，就再減一），于是這位上的上確定了。測試結果，跟二分試商相比，在2048bit級別的大數上，快了8-10倍左右。

模和除基本沒什么區別，只是返回的東西不一樣。

五、冪和模冪。

對于冪的實現，也用二分的思想。比如計算 a 的 10 次方，可以轉化成先算 a 的 5 次方，然后自乘一次。a 的 5 次方，可以轉化成先算 a 的 2 次方，然后自乘、再乘一次 a。a 的 2 次方，就是自乘一次。最后，變成：

((a ^ 2) ^ 2 * a) ^ 2，或者看成 (((1 ^ 2 * a) ^ 2) ^ 2 * a) ^ 2

然后觀察指數 10 的二進制表示：1010

規律是，以 1 為起始，從高位到低位看指數，遇到1就平方再乘底數，遇到0就單單平方。

至于模冪，就在每次平方前/后，把底數模一下，保證參與乘法的兩個數都是“不太大”的。

以上，僅介紹我是怎么做的。至于對錯、有沒有更好做法，望各位不吝賜教。

最后，做了個簡單的性能測試——做RSA運算：
（plain = 12345; encoded = 0; decoded = 0;）
計算以下兩行的運行時間。
encoded = plain.ExpMod(d, n);
decoded = encoded.ExpMod(e, n);

在我機器（Win7 32bit，Intel E5200 沒超頻）上的測試結果如下——

512位：0.040s.
1024位：0.250s.
2048位：1.495s.

2048位的情形，已經有很明顯的等待了。不知道一般來說現在2048bit的RSA性能是怎樣的，一秒鐘能計算多少次？