大數(shù)相乘畢業(yè)論文

1、<p><b>　　摘要</b></p><p>　　大整數(shù)乘法運(yùn)算經(jīng)常會(huì)遇到溢出或精度不夠的問(wèn)題，而在許多領(lǐng)域要求高精度大整數(shù)運(yùn)算。因而，有很多人在這方面作過(guò)努力。大整數(shù)運(yùn)算比較通用的方法有疊加法（小學(xué)生乘法）和分治法。疊加法與我們筆算乘法一樣，用第一個(gè)數(shù)的每一位去乘第二個(gè)數(shù)的每一位，然后把運(yùn)算結(jié)果按權(quán)值疊加；分治法是把大整數(shù)化為可直接運(yùn)算的小整數(shù)，再進(jìn)行乘法運(yùn)算，最后把乘得的結(jié)

2、果組合為所求結(jié)果。</p><p>　　本文在總結(jié)這兩種方法的基礎(chǔ)上，提出一種把疊加與分治相結(jié)合的方法——疊加分治法。疊加分治法吸收了疊加法和分治算法的優(yōu)點(diǎn)。該算法基于分治思想，把大整數(shù)分解成較小整數(shù)（幾十位），再用疊加法運(yùn)算較小整數(shù)，最后把運(yùn)算結(jié)果組合為所求的積。一方面，減少較小整數(shù)多次分解與組合帶來(lái)的在時(shí)間上和空間上的開(kāi)銷；另一方面，避免大整數(shù)疊加運(yùn)算在時(shí)間上與規(guī)模成級(jí)數(shù)增加開(kāi)銷。</p>&l

3、t;p>　　最后，本文還設(shè)計(jì)了一個(gè)算法演示程序，對(duì)分治算法、疊加算法與本文提出的疊加分治法做出定量分析，并就它們的優(yōu)劣和適用環(huán)境做出詳盡闡述。</p><p>　　關(guān)鍵詞　大整數(shù)、乘法、分治法、疊加法、疊加分治法</p><p><b>　　算法設(shè)計(jì)</b></p><p><b>　　疊加法</b></p&g

4、t;<p>　　疊加算法就是通用的筆算算法思想。在兩個(gè)大整數(shù)相乘中，它用第一個(gè)數(shù)的每一位去乘第二個(gè)數(shù)的每一位，再把運(yùn)算結(jié)果按權(quán)值疊加，進(jìn)位處理后，得到所求的結(jié)果。具體描述如下文所示。</p><p><b>　　將因數(shù)和表示如下：</b></p><p><b>　　， </b></p><p>&

5、lt;b>　　則和可以記為：</b></p><p><b>　　， </b></p><p>　　因此，大整數(shù)乘法的計(jì)算公式為：</p><p>　　………………………（2.1）</p><p>　　在本文中，為了方便起見(jiàn)，將的結(jié)果稱為部分積，將、稱為部分因子。</p><p

6、>　　根據(jù)公式（2.1），大整數(shù)疊加算法的計(jì)算過(guò)程如圖2.1所示。從圖2.1可知，這種算法的思想是：按照部分積的權(quán)值從低到高的順序，每次計(jì)算出所有權(quán)值為的部分積，同時(shí)完成它們之間的累加，然后再計(jì)算權(quán)值更高的部分積，依次類推，直到計(jì)算出所有的部分積。</p><p>　　圖2.1中，是權(quán)值為的部分積的累加之和，其計(jì)算方法如公式（2.2）所示：</p><p>　　………………………（2

7、.2）</p><p>　　圖2.1疊加法大整數(shù)乘法算法</p><p>　　根據(jù)圖2.1所描述的算法思想，得到如下偽代碼描述的算法：</p><p>　　Function Mult(X, Y){</p><p>　　//X和Y是記錄兩個(gè)整數(shù)的數(shù)組，返回結(jié)果為X和Y的乘積XY</p><p>　　For (i = 1；

8、 i< len(x)；i++) //乘積疊加運(yùn)算</p><p>　　For (j = 1；j< len(y)；j++) R(i+j-1) += X(i) * Y(j)</p><p>　　For (i = 1 ；i< len(x) + len(y)；i++) R(i) 向R(i+1) 進(jìn)位</p><p><b>　　Return

9、 R</b></p><p><b>　　}// Mult</b></p><p><b>　　算法 2.1</b></p><p>　　由公式（2.1）得，疊加算法共做次乘法。由2.1.1節(jié)和圖2.1知，該算法還需做次加法運(yùn)算和次進(jìn)位處理。在計(jì)算時(shí)間主要由乘法決定的情況下，它的時(shí)間復(fù)雜度為：</p>

10、;<p>　　………………………………………………（2.3）</p><p>　　又根據(jù)圖2.1，存儲(chǔ)和分別花費(fèi)單元，存儲(chǔ)積需要個(gè)單元，因此該算法的空間復(fù)雜度為：</p><p>　　………………………………………………（2.4）</p><p><b>　　分治法</b></p><p><b>

11、;　　分治法思想簡(jiǎn)介</b></p><p>　　分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。</p><p>　　1、分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征[5]：</p><p>　?。?）該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；</p><p>　?。?）該問(wèn)

12、題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；</p><p>　?。?）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；</p><p>　?。?）該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。 </p><p>　　上述的第一條特征是絕大多數(shù)問(wèn)題都可以滿足的，因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而

13、增加；第二條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問(wèn)題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮貪心法或動(dòng)態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。</p><p>　　2、分治法的基本步驟[6]</p>

14、<p>　　如圖2.2所示，分治法在每一層遞歸上都有三個(gè)步驟：</p><p>　　圖2.2 分治技術(shù)（典型實(shí)例）</p><p>　?。?）分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；</p><p>　　（2）解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；</p><p>　?。?/p>

15、3）合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。</p><p>　　它的一般的算法設(shè)計(jì)模式如下：</p><p>　　Divide-and-Conquer（P）{</p><p>　　if |P|≤n0  then return（ADHOC（P））</p><p>　　將P分解為較小的子問(wèn)題P1、P2、…、Pk</p>

16、<p>　　for i←1 to k {</p><p>　　do  yi ← Divide-and-Conquer（Pi） // 遞歸解決Pi</p><p><b>　　}</b></p><p>　　T ← MERGE（y1，y2，…，yk） // 合并子問(wèn)題</p><p><

17、b>　　Return（T）</b></p><p><b>　　}</b></p><p><b>　　算法2.2</b></p><p>　　其中|P|表示問(wèn)題P的規(guī)模；為一閾值，表示當(dāng)問(wèn)題P的規(guī)模不超過(guò)時(shí)，問(wèn)題已容易解出，不必再繼續(xù)分解。ADHOC（P）是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題

18、P。因此，當(dāng)P的規(guī)模不超過(guò)時(shí)，直接用算法ADHOC（P）求解。 </p><p>　　算法MERGE（y1，y2，…，yk）是該分治法中的合并子算法，用于將P的子問(wèn)題P1、P2、…、Pk的相應(yīng)的解y1、y2、…、yk合并為P的解。</p><p>　　根據(jù)分治法的分割原則，原問(wèn)題應(yīng)該分為多少個(gè)子問(wèn)題才較適宜？各個(gè)子問(wèn)題的規(guī)模應(yīng)該怎樣才為適當(dāng)？這些問(wèn)題很難予以肯定的回答。但從大量實(shí)踐中發(fā)現(xiàn)，

19、在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。換句話說(shuō)，將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。許多問(wèn)題可以取k=2。這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。</p><p>　　分治法的合并步驟是算法的關(guān)鍵所在。有些問(wèn)題的合并方法比較明顯，有些問(wèn)題合并方法比較復(fù)雜，或者是有多種合并方案；或者是合并方案不明顯。究竟應(yīng)該怎樣合并，沒(méi)有統(tǒng)一

20、的模式，需要具體問(wèn)題具體分析。</p><p>　　用分治法設(shè)計(jì)大整數(shù)乘法</p><p>　　明顯地，如果用經(jīng)典的小學(xué)生乘法計(jì)算兩個(gè)位數(shù)的大整數(shù)，將需要做次乘法運(yùn)算。似乎不可能有一種算法能使乘法運(yùn)算次數(shù)少于，但事實(shí)證明并非如此。分治法就是一個(gè)明顯的例子。</p><p>　　設(shè)和都是位的進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積。將和分別分為2段，每段的長(zhǎng)為位(為簡(jiǎn)單起見(jiàn)，假

21、設(shè)是2的冪)，如圖2.3所示。</p><p>　　圖2.3 大整數(shù)和的分段　</p><p>　　由此， ，。這樣，和的乘積為：</p><p><b>　　…（2.5）</b></p><p>　　如果按照公式（2.5）計(jì)算，則我們必須進(jìn)行4次位整數(shù)的乘法(，，和)，以及3次不超過(guò)位的整數(shù)加法(分別對(duì)應(yīng)于公式(2.1

22、)中的加號(hào))，此外還要做2次進(jìn)位處理(分別對(duì)應(yīng)于公式（2.5）中乘和乘)。所有這些加法和進(jìn)位共用步運(yùn)算。設(shè)是2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，由公式（2.5），則有：</p><p>　　………………………（2.6）</p><p>　　由此可得。要想改進(jìn)算法的計(jì)算復(fù)雜性，必須減少乘法次數(shù)。為此我們把XY寫成另一種形式:</p><p><b>　　………（

23、2.7）</b></p><p>　　雖然公式(2.7)看起來(lái)比公式（2.5）要復(fù)雜些，但它僅需做3次位整數(shù)的乘法(，和)，6次加、減法和2次進(jìn)位。由此可得： </p><p>　　….………………………（2.8）</p><p>　　用解遞歸方程的套用公式法，可得其解為：</p><p>　　………………………………（2.9）&

24、lt;/p><p>　　由此可見(jiàn)，改用分治法做大整數(shù)乘法，從理論上講，效率有明顯提高。</p><p>　　根據(jù)以上描述的思想，得出大整數(shù)相乘的偽代碼算法MULT，如下所示：</p><p>　　Function MULT(X，Y，n){</p><p>　　//X和Y為2個(gè)小于n位的無(wú)符號(hào)整數(shù)，返回結(jié)果為X和Y的乘積XY</p>

25、<p><b>　　if（n = 1）</b></p><p>　　return(X * Y)</p><p><b>　　else{</b></p><p>　　A = X的左邊n/2位： B = X的右邊n/2位</p><p>　　C = Y的左邊n/2位： D = Y的右邊n/2位

26、</p><p>　　ml = MULT(A, C, n/2)</p><p>　　m2 = MULT(A-B, D-C, n/2)</p><p>　　m3 = MULT(B, D, n/2)</p><p>　　S = S * (m1左移2n位 + (m1 + m2 + m3)左移n位 + m3)</p><p>

27、<b>　　return(S)</b></p><p><b>　　}</b></p><p><b>　　} //MULT</b></p><p><b>　　算法2.3</b></p><p>　　公式（2.9）已經(jīng)給出分治算法的時(shí)間復(fù)雜度，現(xiàn)在只討論

28、該算法的空間復(fù)雜度。</p><p>　　由公式（2.7）可以看出，存儲(chǔ)、需要個(gè)單元格，存儲(chǔ)、A、B、C、D需要個(gè)單元格，存儲(chǔ)和需要個(gè)單元格。由此可得，X乘以Y需要存儲(chǔ)空間：</p><p>　　….……………………（2.10）</p><p>　　用解遞歸方程的套用公式法，可得其解為：</p><p>　　………………………………（2.11

29、）</p><p>　　于是，用分治法實(shí)現(xiàn)大整數(shù)相乘的時(shí)間復(fù)雜度為，空間復(fù)雜度為。</p><p><b>　　疊加分治法</b></p><p>　　由2.1節(jié)和2.2節(jié)對(duì)疊加法和分治法的描述及其效率的分析可知，在理論上講，分治法的時(shí)間效率要高于疊加法。但是，在實(shí)際上并非如此[6]。當(dāng)整數(shù)位數(shù)很?。ㄈ缥粩?shù)小于600）時(shí)，分治法的效率反而不如疊

30、加法。這是因?yàn)榉种畏ㄔ诜指詈秃喜⑦^(guò)程中要消耗掉大量的時(shí)間，規(guī)模越小，分割合并所占的時(shí)間比例越大。</p><p>　　試想，用另一種方法。既可以避免疊加法在運(yùn)算過(guò)程中因規(guī)模增大，時(shí)間復(fù)雜度以增大；又可以避免因分治法分得過(guò)細(xì)而帶來(lái)的分割組合時(shí)間的大量增加。這就是本文要提出的疊加分治法。</p><p>　　疊加分治法是用分治思想，把超大整數(shù)分割成較小整數(shù)（一般在30位左右），再用疊加法計(jì)算較

31、小整數(shù)的積，最后合并為超大整數(shù)的積。</p><p>　　疊加分治法的偽代碼描述如下所示：</p><p>　　Function MULT(X，Y，n){</p><p>　　//X和Y為2個(gè)n位的無(wú)符號(hào)整數(shù)，返回結(jié)果為X和Y的乘積XY</p><p>　　if（n<=LL）{ //LL為分割上限，當(dāng)乘數(shù)的規(guī)模小于LL，不再分割，調(diào)用疊

32、加運(yùn)算</p><p>　　Return Pen-and-Pencil(X ,Y) //用疊加法計(jì)算X，Y的積}</p><p><b>　　else{</b></p><p>　　A = X的左邊n/2位</p><p>　　B = X的右邊n/2位</p><p>　　C = Y的左邊n/2位

33、</p><p>　　D = Y的右邊n/2位</p><p>　　ml = MULT(A, C, n/2)</p><p>　　m2 = MULT(A-B, D-C, n/2)</p><p>　　m3 = MULT(B, D, n/2)</p><p>　　S = (m1左移2n位 + (m1 + m2 + m3)

34、左移n位 + m3)</p><p><b>　　return(S)</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　算法2.4</b></p><p>　　F2

35、分治與大整數(shù)乘法</p><p><b>　　F2.1分治</b></p><p>　　分治可能是最著名的通用算法設(shè)計(jì)技巧。雖然它的名氣與它的名字易于記憶有關(guān)，但這是當(dāng)之無(wú)愧的：相當(dāng)多的高效率算法都是這種算法規(guī)則的特殊實(shí)現(xiàn)。分治法按如下規(guī)則運(yùn)行：</p><p>　　將問(wèn)題實(shí)例分成幾個(gè)性質(zhì)相同的規(guī)模較小的問(wèn)題實(shí)例，最好是它們的規(guī)模相同。<

36、/p><p>　　解答較小的問(wèn)題實(shí)例（典型的方法有遞歸，雖然當(dāng)問(wèn)題變得足夠小時(shí)，有時(shí)引入有其他算法來(lái)解決問(wèn)題）。</p><p>　　如果有必要，就把小問(wèn)題的解合并起來(lái)，組成原問(wèn)題的解。</p><p>　　分治的流程如圖1所示，它描述了把一個(gè)問(wèn)題分成兩個(gè)更小的子問(wèn)題的實(shí)例，這種實(shí)例是目前最廣泛的實(shí)例（至少對(duì)于用分治法設(shè)計(jì)的單CUP機(jī)器上執(zhí)行的算法規(guī)則是這樣的）<

37、/p><p>　　圖1 分治技術(shù)（典型實(shí)例）</p><p>　　例如，先來(lái)考慮這樣一個(gè)問(wèn)題：計(jì)算個(gè)數(shù)的和。如果，可以把這個(gè)問(wèn)題分成兩個(gè)相同性質(zhì)的子問(wèn)題：計(jì)算前個(gè)數(shù)的和以及計(jì)算后個(gè)數(shù)的和。（當(dāng)然，如果就只需要把作為返回值。）當(dāng)這兩個(gè)和都計(jì)算完備（通過(guò)遞歸應(yīng)用上述方法），就可以得到原始問(wèn)題的解：</p><p>　　這是一種計(jì)算個(gè)數(shù)之和的高效的方法么？第一反應(yīng)（這怎么會(huì)比

38、簡(jiǎn)單地順序相加效率高？），假定一個(gè)用這種方法給四個(gè)數(shù)求和的例子，并且對(duì)它進(jìn)行分析（參見(jiàn)下文），認(rèn)為（我們不會(huì)這樣加的，不是么？）所有這些將導(dǎo)致這個(gè)問(wèn)題的否定答案。</p><p>　　因此，分治法并不是在所有場(chǎng)合都比簡(jiǎn)單蠻算效率更高。但通過(guò)分析算法效率時(shí)，得到的答案是沒(méi)有任何一種算法規(guī)則在時(shí)間上的開(kāi)銷比分治法少。實(shí)際上，在計(jì)算機(jī)科學(xué)上，許多最重要的高效的算法都是基于分治法。我們將在這章討論一些經(jīng)典關(guān)于分治法的例子

39、。雖然在這兒考慮的僅僅是順序算法，但值得我們記住分治技術(shù)是解決相同計(jì)算問(wèn)題的理想技術(shù)，因?yàn)楦鱾€(gè)子問(wèn)題都可以有不同的CPU同時(shí)計(jì)算。</p><p>　　這個(gè)求和的例子是分治法應(yīng)用中最典型的特例：一個(gè)規(guī)模為的問(wèn)題分解成規(guī)模為的兩個(gè)小問(wèn)題。更一般地，一個(gè)規(guī)模為的問(wèn)題可以分解成幾個(gè)規(guī)模為的小問(wèn)題，其中有個(gè)小問(wèn)題需要求解。（這兒，和為常數(shù)，并且，。）為簡(jiǎn)化分析，假設(shè)是的冪，我們將得到下面的運(yùn)行時(shí)間的遞歸式：</p&

40、gt;<p>　　……………………………………（1）</p><p>　　其中是記錄分解問(wèn)題和合并小問(wèn)題答案所花時(shí)間的函數(shù)。（如求和例子， 且。）遞歸式（1）就是一般的分治遞歸式。很明顯，的答案的增長(zhǎng)率由常數(shù)、的值和函數(shù)的增長(zhǎng)率共同決定。許多分治算法的效率分析都向如下定理一樣，非常簡(jiǎn)單。</p><p>　　主定理 如果，并且在遞歸方程（1）中，那么，</p>

41、<p>　　……………………（2）</p><p>　　（類似的結(jié)論對(duì)符號(hào)和也成立）</p><p>　　例如，當(dāng)時(shí)，用分治算法計(jì)算數(shù)組的和的遞歸式（如上所示）為：</p><p>　　…….………………………………(3)</p><p>　　也就是說(shuō)，對(duì)于這個(gè)例子，，，；因此，當(dāng)時(shí)，</p><p>　　…

42、…………………(4)</p><p>　　注意，通過(guò)這個(gè)定理，無(wú)需對(duì)遞歸式求解，就可以知道該算法的效率類型。當(dāng)然，這種方法只能在已知初始條件下求解一個(gè)算法的增長(zhǎng)次數(shù)。</p><p><b>　　F2.2大整數(shù)乘法</b></p><p>　　某些應(yīng)用軟件，特別是現(xiàn)代的密碼技術(shù)，需要對(duì)超過(guò)100位十進(jìn)制整數(shù)進(jìn)行乘法運(yùn)算。顯然，這種整數(shù)對(duì)于現(xiàn)代單

43、“字”長(zhǎng)計(jì)算機(jī)直接計(jì)算是太長(zhǎng)了，因此它們需要作特別處理。這是研究高效的大整數(shù)乘法運(yùn)算的現(xiàn)實(shí)需求。在這節(jié)中，我們略述了一個(gè)有趣的大整數(shù)乘法算法。明顯地，如果我們用經(jīng)典的小學(xué)生乘法計(jì)算兩個(gè)位整數(shù)相乘，用第一個(gè)數(shù)的每一位去乘第二個(gè)數(shù)的每一位，將需要做次位乘法。（如果有一個(gè)數(shù)的位數(shù)少一些，我們可以在它的高位加零補(bǔ)足。）似乎不可能有一種算法能使位乘次數(shù)少于，但事實(shí)證明并非如此。分治技術(shù)的魔力幫助我們完成了這一壯舉。</p><

44、p>　　為闡述這種算法的基本思想，讓我們來(lái)看看一個(gè)兩位數(shù)的例子，23和14。它們可以描述如下：</p><p><b>　　和 </b></p><p><b>　　現(xiàn)在把它們相乘：</b></p><p>　　當(dāng)然，上式的正確結(jié)果為322，但它如同小學(xué)生乘法一樣，需要做四次位乘。幸運(yùn)的是，我們可以利用必需計(jì)算的結(jié)果

45、()和來(lái)計(jì)算中間項(xiàng)。</p><p>　　當(dāng)然，我們剛才計(jì)算的數(shù)字沒(méi)有什么特別的。對(duì)于任意一對(duì)兩位數(shù)，和，它們的積可以按如下公式計(jì)算：</p><p><b>　　其中</b></p><p><b>　　是它們高位數(shù)的積</b></p><p><b>　　是它們低位數(shù)的積</b&

46、gt;</p><p>　　是的高半位加低半位之和與的高半位加低半位之和的積，再減去與的和，得到的結(jié)果。</p><p>　　現(xiàn)在我們用這個(gè)訣竅來(lái)計(jì)算兩個(gè)位整數(shù)和的積，其中為正偶數(shù)。讓我們把兩個(gè)數(shù)字一分為二——畢竟，我們承諾利用分治技術(shù)。我們把的高半位記為， 的低半位記為；同樣把的高半位和低半位分別記為和。在這些符號(hào)中，的意思是，的意思是。因此，利用兩位數(shù)計(jì)算技巧，可得：</p>

47、;<p><b>　　其中</b></p><p><b>　　是它們高半位的積</b></p><p><b>　　是它們低半位的積</b></p><p>　　是的兩個(gè)半位數(shù)值之和與的兩個(gè)半位數(shù)值之和的積，再減去與的和，得到的結(jié)果。</p><p>　　如果還

48、是偶數(shù)，我們可以用同樣的方法來(lái)計(jì)算，，的值。因此，如果是2的冪，我們可以得到一個(gè)計(jì)算兩個(gè)位數(shù)的遞歸算法。從形式上看，這個(gè)遞歸式結(jié)束的條件是等于1。也可以在小到可以直接計(jì)算的情況下結(jié)束這個(gè)遞歸式。</p><p>　　這種算法需要做多少乘法運(yùn)算？因?yàn)閮蓚€(gè)位數(shù)相乘，需要做3次兩個(gè)位數(shù)的乘法，因此兩個(gè)數(shù)相乘需要運(yùn)算的次數(shù)如下式所示：</p><p>　　當(dāng)，將得到如下的解：</p>

49、<p><b>　　令，則</b></p><p>　　（在最后一步，我們利用了對(duì)數(shù)的性質(zhì)：）</p><p>　　應(yīng)當(dāng)知道，對(duì)于規(guī)模不是很大的整數(shù)，該算法運(yùn)行的時(shí)間可能比經(jīng)典算法更長(zhǎng)。Brassard和Bratley（[BB96]，70~71頁(yè)）曾經(jīng)申明：他們的實(shí)驗(yàn)顯示，當(dāng)兩個(gè)數(shù)位數(shù)超過(guò)600位時(shí)，分治法的性能超越了疊加算法的性能。如果你是在面向?qū)ο笳Z(yǔ)言

50、如Java、C++、Smalltalk中設(shè)計(jì)程序，會(huì)發(fā)現(xiàn)這些語(yǔ)言有專門處理大整數(shù)運(yùn)算的的類。</p><p>　　誰(shuí)會(huì)把上面的引號(hào)改成不是這樣的對(duì)稱形式的呀？</p><p>　　寫不寫都行。不寫的話就刪除這章好了。</p><p>　　僅“同等學(xué)歷”的同學(xué)需要寫這個(gè)。什么是“同等學(xué)歷”？我也不懂。</p><p>　　千萬(wàn)不要?jiǎng)h除行尾的分節(jié)

51、符，此行不會(huì)被打印。不要在此行和下頁(yè)的注釋之間填寫任何內(nèi)容</p><p>　　下面的內(nèi)容是參考文獻(xiàn)，通過(guò)“插入”“引用”“腳注和尾注”，插入尾注到“文檔結(jié)尾”后，word會(huì)自動(dòng)生成序號(hào)。雙擊序號(hào)能自動(dòng)定位。移動(dòng)引用位置會(huì)自動(dòng)重新編號(hào)。還可以插入“交叉引用”，實(shí)現(xiàn)對(duì)一篇文獻(xiàn)的多次引用。</p><p>　　因?yàn)楸救四芰λ?，不能將其自?dòng)放入前面的“參考文獻(xiàn)”章節(jié)內(nèi)，也不能去掉接下來(lái)的這半條