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

目標(biāo)很簡單，就是實(shí)現(xiàn)大整數(shù)的基本算術(shù)運(yùn)算。

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

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

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

typedef BigIntT<unsigned int> BigInt;

注意這里的 T 不用 unsigned long long，是有原因的（為了方便乘法實(shí)現(xiàn)，見下文）。實(shí)際上如果有模板約束，我希望 T 被限制為 unsigned int, unsigned short, 以及 unsigned char。

另外，這里的數(shù)據(jù)長度將不做限制，也就是這個大數(shù)可以是任意有限的大小。各個 unsigned int 的順序是低位在前，高位在后——這樣，正好與 PC 機(jī)上的字節(jié)順序一致，于是，整塊內(nèi)存布局看上去就是支持這么多字長的機(jī)器上的一個大數(shù)的內(nèi)存。

我想過兩種實(shí)現(xiàn)方式。一個是固定長度，也就是通過模板參數(shù)或者別的什么，限制其長度，也搞符號位、溢出、移位等，然后想點(diǎn)技巧讓兩個 BigInt<100> 相乘返回 BigInt<200>；二是現(xiàn)在的，不限長度，另有變量作為符號標(biāo)記，不提供移位操作，偏算術(shù)方向。

之后，是數(shù)學(xué)運(yùn)算的實(shí)現(xiàn)。雖然都是些小操作，但是數(shù)字一大，性能瓶頸會很突出，特別是乘除。

（完整代碼見：http://xllib.codeplex.com/SourceControl/changeset/view/1689#1160）

一、加。

加法實(shí)現(xiàn)很直接，就是各位相加——同號的情況。每一位如果有溢出，就在后一位加1。這里指的一“位”，是指一個數(shù)據(jù)單位 T，也就是一個 unsigned int，下同。如果遇到異號的兩個數(shù)，把球踢給減法。

二、減。

減法也比較直接。如果兩數(shù)同號，且是大的減小的，就一位一位減。碰到有溢出的，下一位減去1。最后清除所遇的0。如果是小的減大的，就換過來減，改變下結(jié)果的符號；如果兩數(shù)異號，把球踢給加法。

至此，加減實(shí)現(xiàn)完畢。

三、乘。

乘法的實(shí)現(xiàn)大致有三種：硬乘、分治法以及利用離散傅里葉變換。

由于對后兩種的理解不足，現(xiàn)采用硬乘法。硬乘的道理很簡單，就是小時候打豎式的算法（前面的加法減法也是打豎式）。被乘數(shù)的第 i 位和乘數(shù)的第 j 位的結(jié)果，要加在乘積的第 i + j 位。值得注意的是，這里每一位的乘法我用的是默認(rèn)的內(nèi)置類型的乘法，于是出現(xiàn)了上文要求，T至多只能為unsigned int，以保證這里的臨時結(jié)果可以用一個unsigned long long 存下。

請教各位關(guān)于分治法以及FFT法。1、分治法看上去多了好些加減法，它帶來的好處的前提是加減法實(shí)現(xiàn)的很好，可是按上面的加減法，似乎帶不來什么好處（實(shí)際測過結(jié)果很糟，不知是否我做得不對）。2，F(xiàn)FT法本身我沒弄很明白（很慚愧，數(shù)學(xué)系的，卻從來沒有會過傅里葉變換，是從來沒有過，不是曾經(jīng)會過現(xiàn)在忘了= =），不過有個疑問，F(xiàn)FT以及iFFT的過程本身難道不耗性能嗎？

四、除和模。

除法其實(shí)也是打豎式，其實(shí)到這里為止?jié)M篇都是打豎式，哈。除法的麻煩之處是有個試商過程，試商的時候還要乘一下，看上去會很不理想。為了避免一個一個試，很自然的一個優(yōu)化方法是二分，對于unsigned int 一個單位的數(shù)來說，每個單位至多會嘗試32次，然后會有32次大數(shù)乘，32次大數(shù)比較。測試的情況是，對于不是特別大的數(shù)，還算馬馬虎虎過得去。

嘗試過另外一個方式，那就是另一個極端，用真實(shí)的“位”為單位去“試商”——其實(shí)不用試，是1是0直接知道了。以為會好一些，實(shí)際上更差。初步想了想，一個原因，數(shù)據(jù)規(guī)模沒變，二分試商的時候是 32 * n，現(xiàn)在還是 32 * n，原來的32是32次二分，現(xiàn)在的32是一個單位內(nèi)的32次移位。除此之外，原生的unsigned int的乘除法沒有被利用起來。不知是否？

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

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

五、冪和模冪。

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

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

然后觀察指數(shù) 10 的二進(jìn)制表示：1010

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

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

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

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

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

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

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