大整數(shù)乘法運(yùn)算論文24561

1、摘要大整數(shù)乘法運(yùn)算經(jīng)常會(huì)遇到溢出或精度不夠的問題，而在許多領(lǐng)域要求高精度大整數(shù)運(yùn)算。因而，有很多人在這方面作過努力。大整數(shù)運(yùn)算比較通用的方法有疊加法（小學(xué)生乘法）和分治法。疊加法與我們筆算乘法一樣，用第一個(gè)數(shù)的每一位去乘第二個(gè)數(shù)的每一位，然后把運(yùn)算結(jié)果按權(quán)值疊加；分治法是把大整數(shù)化為可直接運(yùn)算的小整數(shù)，再進(jìn)行乘法運(yùn)算，最后把乘得的結(jié)果組合為所求結(jié)果。本文在總結(jié)這兩種方法的基礎(chǔ)上，提出一種把疊加與分治相結(jié)合的方法疊加分治法。疊加分治法吸收了疊加法和分治算法的優(yōu)點(diǎn)。該算法基于分治思想，把大整數(shù)分解成較小整數(shù)（幾十位），再用疊加法運(yùn)算較小整數(shù)，最后把運(yùn)算結(jié)果組合為所求的積。一方面，減少較小整數(shù)多次分

2、解與組合帶來的在時(shí)間上和空間上的開銷；另一方面，避免大整數(shù)疊加運(yùn)算在時(shí)間上與規(guī)模成級(jí)數(shù)增加開銷。最后，本文還設(shè)計(jì)了一個(gè)算法演示程序，對(duì)分治算法、疊加算法與本文提出的疊加分治法做出定量分析，并就它們的優(yōu)劣和適用環(huán)境做出詳盡闡述。關(guān)鍵詞大整數(shù)、乘法、分治法、疊加法、疊加分治法第1章 算法設(shè)計(jì)1.1 疊加法疊加算法就是通用的筆算算法思想。在兩個(gè)大整數(shù)相乘中，它用第一個(gè)數(shù)的每一位去乘第二個(gè)數(shù)的每一位，再把運(yùn)算結(jié)果按權(quán)值疊加，進(jìn)位處理后，得到所求的結(jié)果。具體描述如下文所示。將因數(shù)和表示如下：， 則和可以記為：， 因此，大整數(shù)乘法的計(jì)算公式為： （2.1）在本文中，為了方便起見，將的結(jié)果稱為部分積，將、稱

3、為部分因子。根據(jù)公式（2.1），大整數(shù)疊加算法的計(jì)算過程如圖2.1所示。從圖2.1可知，這種算法的思想是：按照部分積的權(quán)值從低到高的順序，每次計(jì)算出所有權(quán)值為的部分積，同時(shí)完成它們之間的累加，然后再計(jì)算權(quán)值更高的部分積，依次類推，直到計(jì)算出所有的部分積。圖2.1中，是權(quán)值為的部分積的累加之和，其計(jì)算方法如公式（2.2）所示： （2.2）圖2.1疊加法大整數(shù)乘法算法根據(jù)圖2.1所描述的算法思想，得到如下偽代碼描述的算法：function mult(x, y)/x和y是記錄兩個(gè)整數(shù)的數(shù)組，返回結(jié)果為x和y的乘積xyfor (i = 1； i len(x)；i+) /乘積疊加運(yùn)算for (j = 1

4、；j len(y)；j+) r(i+j-1) += x(i) * y(j)for (i = 1 ；i len(x) + len(y)；i+) r(i) 向r(i+1) 進(jìn)位return r/ mult算法 2.1由公式（2.1）得，疊加算法共做次乘法。由2.1.1節(jié)和圖2.1知，該算法還需做次加法運(yùn)算和次進(jìn)位處理。在計(jì)算時(shí)間主要由乘法決定的情況下，它的時(shí)間復(fù)雜度為： （2.3）又根據(jù)圖2.1，存儲(chǔ)和分別花費(fèi)單元，存儲(chǔ)積需要個(gè)單元，因此該算法的空間復(fù)雜度為： （2.4）1.2 分治法1.2.1 分治法思想簡(jiǎn)介分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊

5、破，分而治之。1、分治法所能解決的問題一般具有以下幾個(gè)特征5：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。上述的第一條特征是絕大多數(shù)問題都可以滿足的，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加；第二條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征

6、，而不具備第三條特征，則可以考慮貪心法或動(dòng)態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。2、分治法的基本步驟6如圖2.2所示，分治法在每一層遞歸上都有三個(gè)步驟：解答子問題1解答子問題2規(guī)模為的問題規(guī)模為的子問題1規(guī)模為的子問題2合并為原問題的解圖2.2 分治技術(shù)（典型實(shí)例）（1）分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；（2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題；（3）合并：將各個(gè)子問題的解合并為原問題的解。它的一般的算法設(shè)計(jì)模式如下：divide-and-conq

7、uer（p）if |p|n0 then return（adhoc（p）將p分解為較小的子問題p1、p2、pkfor i1 to kdo yi divide-and-conquer（pi） / 遞歸解決pit merge（y1，y2，yk） / 合并子問題return（t）算法2.2其中|p|表示問題p的規(guī)模；為一閾值，表示當(dāng)問題p的規(guī)模不超過時(shí)，問題已容易解出，不必再繼續(xù)分解。adhoc（p）是該分治法中的基本子算法，用于直接解小規(guī)模的問題p。因此，當(dāng)p的規(guī)模不超過時(shí)，直接用算法adhoc（p）求解。 算法merge（y1，y2，yk）是該分治法中的合并子算法，用于將p的子問題p1、p2、pk

8、的相應(yīng)的解y1、y2、yk合并為p的解。根據(jù)分治法的分割原則，原問題應(yīng)該分為多少個(gè)子問題才較適宜？各個(gè)子問題的規(guī)模應(yīng)該怎樣才為適當(dāng)？這些問題很難予以肯定的回答。但從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同。換句話說，將一個(gè)問題分成大小相等的k個(gè)子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子問題規(guī)模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。分治法的合并步驟是算法的關(guān)鍵所在。有些問題的合并方法比較明顯，有些問題合并方法比較復(fù)雜，或者是有多種合并方案；或者是合并方案不明顯。究竟應(yīng)該怎樣合并，沒有統(tǒng)一的模式，需要具體問題具體分

9、析。1.2.2 用分治法設(shè)計(jì)大整數(shù)乘法明顯地，如果用經(jīng)典的小學(xué)生乘法計(jì)算兩個(gè)位數(shù)的大整數(shù)，將需要做次乘法運(yùn)算。似乎不可能有一種算法能使乘法運(yùn)算次數(shù)少于，但事實(shí)證明并非如此。分治法就是一個(gè)明顯的例子。設(shè)和都是位的進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積。將和分別分為2段，每段的長為位(為簡(jiǎn)單起見，假設(shè)是2的冪)，如圖2.3所示。圖2.3 大整數(shù)和的分段由此， ，。這樣，和的乘積為： （2.5）如果按照公式（2.5）計(jì)算，則我們必須進(jìn)行4次位整數(shù)的乘法(，和)，以及3次不超過位的整數(shù)加法(分別對(duì)應(yīng)于公式(2.1)中的加號(hào))，此外還要做2次進(jìn)位處理(分別對(duì)應(yīng)于公式（2.5）中乘和乘)。所有這些加法和進(jìn)位共用步

10、運(yùn)算。設(shè)是2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，由公式（2.5），則有： （2.6）由此可得。要想改進(jìn)算法的計(jì)算復(fù)雜性，必須減少乘法次數(shù)。為此我們把xy寫成另一種形式: （2.7）雖然公式(2.7)看起來比公式（2.5）要復(fù)雜些，但它僅需做3次位整數(shù)的乘法(，和)，6次加、減法和2次進(jìn)位。由此可得： .（2.8）用解遞歸方程的套用公式法，可得其解為： （2.9）由此可見，改用分治法做大整數(shù)乘法，從理論上講，效率有明顯提高。根據(jù)以上描述的思想，得出大整數(shù)相乘的偽代碼算法mult，如下所示：function mult(x，y，n)/x和y為2個(gè)小于n位的無符號(hào)整數(shù)，返回結(jié)果為x和y的乘積xyif（n =

11、 1）return(x * y)elsea = x的左邊n/2位： b = x的右邊n/2位c = y的左邊n/2位： d = y的右邊n/2位ml = mult(a, c, n/2)m2 = mult(a-b, d-c, n/2)m3 = mult(b, d, n/2)s = s * (m1左移2n位 + (m1 + m2 + m3)左移n位 + m3)return(s) /mult算法2.3公式（2.9）已經(jīng)給出分治算法的時(shí)間復(fù)雜度，現(xiàn)在只討論該算法的空間復(fù)雜度。由公式（2.7）可以看出，存儲(chǔ)、需要個(gè)單元格，存儲(chǔ)、a、b、c、d需要個(gè)單元格，存儲(chǔ)和需要個(gè)單元格。由此可得，x乘以y需要存儲(chǔ)空

12、間： .（2.10）用解遞歸方程的套用公式法，可得其解為： （2.11）于是，用分治法實(shí)現(xiàn)大整數(shù)相乘的時(shí)間復(fù)雜度為，空間復(fù)雜度為。1.3 疊加分治法由2.1節(jié)和2.2節(jié)對(duì)疊加法和分治法的描述及其效率的分析可知，在理論上講，分治法的時(shí)間效率要高于疊加法。但是，在實(shí)際上并非如此6。當(dāng)整數(shù)位數(shù)很?。ㄈ缥粩?shù)小于600）時(shí)，分治法的效率反而不如疊加法。這是因?yàn)榉种畏ㄔ诜指詈秃喜⑦^程中要消耗掉大量的時(shí)間，規(guī)模越小，分割合并所占的時(shí)間比例越大。試想，用另一種方法。既可以避免疊加法在運(yùn)算過程中因規(guī)模增大，時(shí)間復(fù)雜度以增大；又可以避免因分治法分得過細(xì)而帶來的分割組合時(shí)間的大量增加。這就是本文要提出的疊加分治法。

13、疊加分治法是用分治思想，把超大整數(shù)分割成較小整數(shù)（一般在30位左右），再用疊加法計(jì)算較小整數(shù)的積，最后合并為超大整數(shù)的積。疊加分治法的偽代碼描述如下所示：function mult(x，y，n)/x和y為2個(gè)n位的無符號(hào)整數(shù)，返回結(jié)果為x和y的乘積xyif（n=ll） /ll為分割上限，當(dāng)乘數(shù)的規(guī)模小于ll，不再分割，調(diào)用疊加運(yùn)算return pen-and-pencil(x ,y) /用疊加法計(jì)算x，y的積elsea = x的左邊n/2位b = x的右邊n/2位c = y的左邊n/2位d = y的右邊n/2位ml = mult(a, c, n/2)m2 = mult(a-b, d-c, n/

14、2)m3 = mult(b, d, n/2)s = (m1左移2n位 + (m1 + m2 + m3)左移n位 + m3)return(s)算法2.4f2 分治與大整數(shù)乘法f2.1分治分治可能是最著名的通用算法設(shè)計(jì)技巧。雖然它的名氣與它的名字易于記憶有關(guān)，但這是當(dāng)之無愧的：相當(dāng)多的高效率算法都是這種算法規(guī)則的特殊實(shí)現(xiàn)。分治法按如下規(guī)則運(yùn)行：1. 將問題實(shí)例分成幾個(gè)性質(zhì)相同的規(guī)模較小的問題實(shí)例，最好是它們的規(guī)模相同。2. 解答較小的問題實(shí)例（典型的方法有遞歸，雖然當(dāng)問題變得足夠小時(shí)，有時(shí)引入有其他算法來解決問題）。3. 如果有必要，就把小問題的解合并起來，組成原問題的解。分治的流程如圖1所示，它

15、描述了把一個(gè)問題分成兩個(gè)更小的子問題的實(shí)例，這種實(shí)例是目前最廣泛的實(shí)例（至少對(duì)于用分治法設(shè)計(jì)的單cup機(jī)器上執(zhí)行的算法規(guī)則是這樣的）解答子問題1解答子問題2規(guī)模為的問題規(guī)模為的子問題1規(guī)模為的子問題2合并為原問題的解圖1 分治技術(shù)（典型實(shí)例）待添加的隱藏文字內(nèi)容2例如，先來考慮這樣一個(gè)問題：計(jì)算個(gè)數(shù)的和。如果，可以把這個(gè)問題分成兩個(gè)相同性質(zhì)的子問題：計(jì)算前個(gè)數(shù)的和以及計(jì)算后個(gè)數(shù)的和。（當(dāng)然，如果就只需要把作為返回值。）當(dāng)這兩個(gè)和都計(jì)算完備（通過遞歸應(yīng)用上述方法），就可以得到原始問題的解：這是一種計(jì)算個(gè)數(shù)之和的高效的方法么？第一反應(yīng)（這怎么會(huì)比簡(jiǎn)單地順序相加效率高？），假定一個(gè)用這種方法給四個(gè)數(shù)

16、求和的例子，并且對(duì)它進(jìn)行分析（參見下文），認(rèn)為（我們不會(huì)這樣加的，不是么？）所有這些將導(dǎo)致這個(gè)問題的否定答案。因此，分治法并不是在所有場(chǎng)合都比簡(jiǎn)單蠻算效率更高。但通過分析算法效率時(shí)，得到的答案是沒有任何一種算法規(guī)則在時(shí)間上的開銷比分治法少。實(shí)際上，在計(jì)算機(jī)科學(xué)上，許多最重要的高效的算法都是基于分治法。我們將在這章討論一些經(jīng)典關(guān)于分治法的例子。雖然在這兒考慮的僅僅是順序算法，但值得我們記住分治技術(shù)是解決相同計(jì)算問題的理想技術(shù)，因?yàn)楦鱾€(gè)子問題都可以有不同的cpu同時(shí)計(jì)算。這個(gè)求和的例子是分治法應(yīng)用中最典型的特例：一個(gè)規(guī)模為的問題分解成規(guī)模為的兩個(gè)小問題。更一般地，一個(gè)規(guī)模為的問題可以分解成幾個(gè)規(guī)模

17、為的小問題，其中有個(gè)小問題需要求解。（這兒，和為常數(shù)，并且，。）為簡(jiǎn)化分析，假設(shè)是的冪，我們將得到下面的運(yùn)行時(shí)間的遞歸式： （1）其中是記錄分解問題和合并小問題答案所花時(shí)間的函數(shù)。（如求和例子， 且。）遞歸式（1）就是一般的分治遞歸式。很明顯，的答案的增長率由常數(shù)、的值和函數(shù)的增長率共同決定。許多分治算法的效率分析都向如下定理一樣，非常簡(jiǎn)單。主定理 如果，并且在遞歸方程（1）中，那么， （2）（類似的結(jié)論對(duì)符號(hào)和也成立）例如，當(dāng)時(shí)，用分治算法計(jì)算數(shù)組的和的遞歸式（如上所示）為： .(3)也就是說，對(duì)于這個(gè)例子，；因此，當(dāng)時(shí)， (4)注意，通過這個(gè)定理，無需對(duì)遞歸式求解，就可以知道該算法的效率類

18、型。當(dāng)然，這種方法只能在已知初始條件下求解一個(gè)算法的增長次數(shù)。f2.2大整數(shù)乘法某些應(yīng)用軟件，特別是現(xiàn)代的密碼技術(shù)，需要對(duì)超過100位十進(jìn)制整數(shù)進(jìn)行乘法運(yùn)算。顯然，這種整數(shù)對(duì)于現(xiàn)代單“字”長計(jì)算機(jī)直接計(jì)算是太長了，因此它們需要作特別處理。這是研究高效的大整數(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ù)的魔力幫助我們完成了這一壯舉。為闡述這種

19、算法的基本思想，讓我們來看看一個(gè)兩位數(shù)的例子，23和14。它們可以描述如下： 和 現(xiàn)在把它們相乘：當(dāng)然，上式的正確結(jié)果為322，但它如同小學(xué)生乘法一樣，需要做四次位乘。幸運(yùn)的是，我們可以利用必需計(jì)算的結(jié)果()和來計(jì)算中間項(xiàng)。當(dāng)然，我們剛才計(jì)算的數(shù)字沒有什么特別的。對(duì)于任意一對(duì)兩位數(shù)，和，它們的積可以按如下公式計(jì)算：其中是它們高位數(shù)的積是它們低位數(shù)的積是的高半位加低半位之和與的高半位加低半位之和的積，再減去與的和，得到的結(jié)果?，F(xiàn)在我們用這個(gè)訣竅來計(jì)算兩個(gè)位整數(shù)和的積，其中為正偶數(shù)。讓我們把兩個(gè)數(shù)字一分為二畢竟，我們承諾利用分治技術(shù)。我們把的高半位記為， 的低半位記為；同樣把的高半位和低半位分別記為和。在這些符號(hào)中，的意思是，的意思是。因此，利用兩位數(shù)計(jì)算技巧，可得：其中是它們高半位的積是它們低半位的積是的兩個(gè)半位數(shù)值之和與的兩個(gè)半位數(shù)值之和的積，再減去與的和，得到的結(jié)果。如果還是偶數(shù)，我們可以用同樣的方法來計(jì)算，的值。因此，如果是2的