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

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

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

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

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

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

6、>　　根據(jù)公式（2.1），大整數(shù)疊加算法的計算過程如圖2.1所示。從圖2.1可知，這種算法的思想是：按照部分積的權值從低到高的順序，每次計算出所有權值為的部分積，同時完成它們之間的累加，然后再計算權值更高的部分積，依次類推，直到計算出所有的部分積。</p><p>　　圖2.1中，是權值為的部分積的累加之和，其計算方法如公式（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是記錄兩個整數(shù)的數(shù)組，返回結果為X和Y的乘積XY</p><p>　　For (i = 1；

8、 i< len(x)；i++) //乘積疊加運算</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) 進位</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知，該算法還需做次加法運算和次進位處理。在計算時間主要由乘法決定的情況下，它的時間復雜度為：</p>

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

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

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

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

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

15、3）合并：將各個子問題的解合并為原問題的解。</p><p>　　它的一般的算法設計模式如下：</p><p>　　Divide-and-Conquer（P）{</p><p>　　if |P|≤n0  then return（ADHOC（P））</p><p>　　將P分解為較小的子問題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） // 合并子問題</p><p><

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

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

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

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

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

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

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

24、lt;/p><p>　　由此可見，改用分治法做大整數(shù)乘法，從理論上講，效率有明顯提高。</p><p>　　根據(jù)以上描述的思想，得出大整數(shù)相乘的偽代碼算法MULT，如下所示：</p><p>　　Function MULT(X，Y，n){</p><p>　　//X和Y為2個小于n位的無符號整數(shù)，返回結果為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)給出分治算法的時間復雜度，現(xiàn)在只討論

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

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

30、加法。這是因為分治法在分割和合并過程中要消耗掉大量的時間，規(guī)模越小，分割合并所占的時間比例越大。</p><p>　　試想，用另一種方法。既可以避免疊加法在運算過程中因規(guī)模增大，時間復雜度以增大；又可以避免因分治法分得過細而帶來的分割組合時間的大量增加。這就是本文要提出的疊加分治法。</p><p>　　疊加分治法是用分治思想，把超大整數(shù)分割成較小整數(shù)（一般在30位左右），再用疊加法計算較

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

32、加運算</p><p>　　Return Pen-and-Pencil(X ,Y) //用疊加法計算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>　　分治可能是最著名的通用算法設計技巧。雖然它的名氣與它的名字易于記憶有關，但這是當之無愧的：相當多的高效率算法都是這種算法規(guī)則的特殊實現(xiàn)。分治法按如下規(guī)則運行：</p><p>　　將問題實例分成幾個性質相同的規(guī)模較小的問題實例，最好是它們的規(guī)模相同。<

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

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

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

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

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

41、<p>　　……………………（2）</p><p>　?。愃频慕Y論對符號和也成立）</p><p>　　例如，當時，用分治算法計算數(shù)組的和的遞歸式（如上所示）為：</p><p>　　…….………………………………(3)</p><p>　　也就是說，對于這個例子，，，；因此，當時，</p><p>　　…

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

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

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

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

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

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

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

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

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

51、符，此行不會被打印。不要在此行和下頁的注釋之間填寫任何內(nèi)容</p><p>　　下面的內(nèi)容是參考文獻，通過“插入”“引用”“腳注和尾注”，插入尾注到“文檔結尾”后，word會自動生成序號。雙擊序號能自動定位。移動引用位置會自動重新編號。還可以插入“交叉引用”，實現(xiàn)對一篇文獻的多次引用。</p><p>　　因為本人能力所限，不能將其自動放入前面的“參考文獻”章節(jié)內(nèi)，也不能去掉接下來的這半條