好久沒(méi)寫(xiě)了。這次寫(xiě)前一陣子的一個(gè)大整數(shù)類(lèi)，順便請(qǐng)教幾個(gè)問(wèn)題。

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

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

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

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

typedef BigIntT<unsigned int> BigInt;

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

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

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

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

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

一、加。

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

二、減。

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

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

三、乘。

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

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

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

四、除和模。

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

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

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

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

五、冪和模冪。

對(duì)于冪的實(shí)現(xiàn)，也用二分的思想。比如計(jì)算 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ù)模一下，保證參與乘法的兩個(gè)數(shù)都是“不太大”的。

以上，僅介紹我是怎么做的。至于對(duì)錯(cuò)、有沒(méi)有更好做法，望各位不吝賜教。

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

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

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

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