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

大數(shù)相乘畢業(yè)論文大數(shù)相乘畢業(yè)論文/大數(shù)相乘畢業(yè)論文摘要大整數(shù)乘法運算經(jīng)常會遇到溢出或精度不夠的問題，而在許多領(lǐng)域要求高精度大整數(shù)運算。因而，有很多人在這方面作過努力。大整數(shù)運算比較通用的方法有疊加法（小學生乘法）和分治法。疊加法與我們筆算乘法一樣，用第一個數(shù)的每一位去乘第二個數(shù)的每一位，然后把運算結(jié)果按權(quán)值疊加；分治法是把大整數(shù)化為可直接運算的小整數(shù)，再進行乘法運算，最后把乘得的結(jié)果組合為所求結(jié)果。本文在總結(jié)這兩種方法的基礎(chǔ)上，提出一種把疊加與分治相結(jié)合的方法——疊加分治法。疊加分治法吸收了疊加法和分治算法的優(yōu)點。該算法基于分治思想，把大整數(shù)分解成較小整數(shù)（幾十位），再用疊加法運算較小整數(shù)，最后把運算結(jié)果組合為所求的積。一方面，減少較小整數(shù)多次分解與組合帶來的在時間上和空間上的開銷；另一方面，避免大整數(shù)疊加運算在時間上與規(guī)模成級數(shù)增加開銷。最后，本文還設(shè)計了一個算法演示程序，對分治算法、疊加算法與本文提出的疊加分治法做出定量分析，并就它們的優(yōu)劣和適用環(huán)境做出詳盡闡述。關(guān)鍵詞大整數(shù)、乘法、分治法、疊加法、疊加分治法AbstractMultiplicationoflargeintegersusuallymeetstheproblemofoverflowingornotenoughaccurate.But,inmanyappliedrealms,highlyaccuratecalculationoflargeintegersisrequested.Asaresult,manypeoplehavemadegreateffortsinthisaspect.Now,thegeneralmethodsarethepen-and-pencilmethodandthedivide-and-conquermethod.Thepen-and-pencilmethod,whichissimilartomultiplywithapen,ismultiplyinglargeintegerswitheverydigitofonenumberbyeverydigitoftheotherone.Differently,thedivide-and-conquermethodistodividelargeintegersintoseveralsmallerintegers(generally,theyaretow),andthen,tocarryonthemultiplicationofthesmallerintegers.Thistextspecifiesanotheralgorithm,whichbasesonthosetwomethods.Thisalgorithm,thatcombinesthepen-and-pencilmethodandthedivide-and-conquermethodtogether,iscalledthecombinativealgorithmofpen-and-pencilanddivide-and-conquer.Itisthecombinationofvirtuesofthepen-and-pencilmethodandthedivide-and-conquermethod.Itsthought,basedonthedivide-and-conquer,isfirstlyusingthedivide-and-conquermethodtodividethelargeintegersintosmallerintegers(severaldozendigits),nextusingthepen-and-pencilmethodtocalculatethesmallerintegers,andthencombiningthecalculatinglyresultsintothedesiredproduct.Ontheonehand,itreducesthetimeexpenseondecomposingsmallerintegersandcombiningtheirproduct.Ontheotherhand,itavoidsthefleetlyincrementalexpenseontimethatcomesfromtheincrementaldigitsoflargeintegers.Lastly,thistextanalyzesthepen-and-pencilmethod,thedivide-and-conquermethod,andthecombinationofpen-and-pencilanddivide-and-conquerquantificationally,andthen,elaboratestheirgoodandbad,andtheirappliedenvironments.Keywordslargeintegers,multiplication,pen-and-pencil,divide-and-conquer,combinativealgorithmofpen-and-pencilanddivide-and-conquer目錄摘要 IAbstract II第1章緒論 11.1課題背景 11.2發(fā)展狀況 11.3各章安排 2第2章算法設(shè)計 32.1疊加法 32.2分治法 52.2.1分治法思想簡介 52.2.2用分治法設(shè)計大整數(shù)乘法 72.3疊加分治法 9第3章算法演示設(shè)計 113.1概要設(shè)計 113.2詳細設(shè)計 123.2.1主調(diào)用模塊設(shè)計 123.2.2疊加法模塊設(shè)計 133.2.3疊加分治法模塊設(shè)計 153.3結(jié)果與分析 17結(jié)論 19參考文獻 20附錄英譯漢 21F1Divide-and-ConquerandMultiplicationofLargeIntegers 21F1.1Divide-and-Conquer 21F1.2MultiplicationofLargeIntegers 23F2分治與大整數(shù)乘法 26F2.1分治 26F2.2大整數(shù)乘法 28致謝 31緒論課題背景密碼學是用來保證信息安全的一種必要的手段，是信息安全的一個核心。密碼學要解決的問題也是信息安全的主要任務(wù)，就是解決網(wǎng)上信息的機密性、完整性、不可否認性和可用性。機密性就是要傳送一個信息，這個信息只有接收者才能讀到，其他的人，其他的用戶是無法獲取這個信息，即使得到加密以后的形式，也無法打開信息內(nèi)容。機密性就是要對傳送的信息加密，保證信息不泄漏給未經(jīng)授權(quán)的人。完整性就是防止信息被未經(jīng)授權(quán)的人篡改，保證信息不被篡改，而且信息的完整性跟不可否認性是緊密相連的東西。不可否認性和完整性這兩條實際上都是一種對信息的一些認證，就是對每一條消息，它是可以通過密碼算法加密，用像數(shù)字簽名一類的認證算法進行識別和認證?？捎眯援斎灰馑急容^明確，就是保證信息與信息系統(tǒng)確實為授權(quán)使用者所用[10]。密碼學必然包括一些直接的數(shù)學理論，很多數(shù)學理論對密碼學都有直接的應(yīng)用，如橢圓曲線群中的離散對數(shù)問題、整數(shù)分解問題、丟番圖算法。而這些數(shù)學理論在計算機中的實現(xiàn)，大都涉與到大整數(shù)的運算。這里所謂的大整數(shù)指的是至少上百位之間的數(shù)字組成的大整數(shù)。比如RSA、Rabin、以與EIGamal等加密機制都需要這種大整數(shù)的運算。而現(xiàn)有的計算機一般只能處理32位的二進制整數(shù)，少數(shù)的可以處理64位整數(shù)。因此，大整數(shù)的運算就必須借助軟件才能實現(xiàn)。發(fā)展狀況任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模n有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題也就不那么容易處理。為了加快大整數(shù)乘法運算，人們對大整數(shù)乘法的運算與實現(xiàn)進行了很多研究。目前，大整數(shù)的運算方法主要有將大整數(shù)運算分解成規(guī)模較小整數(shù)運算的分治算法和整體運算的疊加算法。參考文獻[1,2,3]給出了基于小學生乘法的疊加算法。該思想是把大整數(shù)按位分解成整數(shù)，然后分別相乘，再按權(quán)值疊加得到所乘的積。參考文獻[4,5,6]給出了基于大整數(shù)化為小整數(shù)的分治法。它把大整數(shù)分解成兩個規(guī)模較小的、計算機可直接處理的整數(shù)，讓小整數(shù)相乘，然后在把它們的乘積組合起來，得到所需的大整數(shù)之積。前者思路簡單，易于實現(xiàn)；但時間復(fù)雜度高，隨著規(guī)模增大，時間花費增加很快。后者隨著規(guī)模增大，時間花消增大比例不如疊加法大；但是當整數(shù)規(guī)模較小時，用于分解與合并花費的時間占總運算時間的比例很大。所以本文提出一種把疊加與分治相結(jié)合的方法。它首先把大整數(shù)分解成規(guī)模較小的整數(shù)，再用疊加法計算較小整數(shù)的值，最后把計算結(jié)果組合為所求的原整數(shù)的解。各章安排第一章：緒論。主要介紹大整數(shù)乘法的應(yīng)用領(lǐng)域和當前發(fā)展狀況。第二章：詳細描述疊加法、分治法和疊加分治算法的設(shè)計思想。第三章：基于VB，設(shè)計演示程序，演示以上三種算法。算法設(shè)計疊加法疊加算法就是通用的筆算算法思想。在兩個大整數(shù)相乘中，它用第一個數(shù)的每一位去乘第二個數(shù)的每一位，再把運算結(jié)果按權(quán)值疊加，進位處理后，得到所求的結(jié)果。具體描述如下文所示。將因數(shù)和表示如下：，則和可以記為：，因此，大整數(shù)乘法的計算公式為：………（2.1）在本文中，為了方便起見，將的結(jié)果稱為部分積，將、稱為部分因子。根據(jù)公式（2.1），大整數(shù)疊加算法的計算過程如圖2.1所示。從圖2.1可知，這種算法的思想是：按照部分積的權(quán)值從低到高的順序，每次計算出所有權(quán)值為的部分積，同時完成它們之間的累加，然后再計算權(quán)值更高的部分積，依次類推，直到計算出所有的部分積。圖2.1中，是權(quán)值為的部分積的累加之和，其計算方法如公式（2.2）所示：………（2.2）圖2.1疊加法大整數(shù)乘法算法根據(jù)圖2.1所描述的算法思想，得到如下偽代碼描述的算法：FunctionMult(X,Y){//X和Y是記錄兩個整數(shù)的數(shù)組，返回結(jié)果為X和Y的乘積XYFor(i=1；i<len(x)；i++)//乘積疊加運算For(j=1；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)進位ReturnR}//Mult算法2.1由公式（2.1）得，疊加算法共做次乘法。由2.1.1節(jié)和圖2.1知，該算法還需做次加法運算和次進位處理。在計算時間主要由乘法決定的情況下，它的時間復(fù)雜度為：………………（2.3） 又根據(jù)圖2.1，存儲和分別花費單元，存儲積需要個單元，因此該算法的空間復(fù)雜度為：………………（2.4）分治法分治法思想簡介分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。1、分治法所能解決的問題一般具有以下幾個特征[5]：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

上述的第一條特征是絕大多數(shù)問題都可以滿足的，因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加；第二條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮貪心法或動態(tài)規(guī)劃法。第四條特征涉與到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。2、分治法的基本步驟[6]如圖2.2所示，分治法在每一層遞歸上都有三個步驟：解答子問題解答子問題1解答子問題2規(guī)模為的問題規(guī)模為的子問題1規(guī)模為的子問題2合并為原問題的解圖2.2分治技術(shù)（典型實例）（1）分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；（2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題；（3）合并：將各個子問題的解合并為原問題的解。它的一般的算法設(shè)計模式如下：Divide-and-Conquer（P）{if|P|≤n0

thenreturn（ADHOC（P））將P分解為較小的子問題P1、P2、…、Pkfori←1tok

{do

yi←Divide-and-Conquer（Pi）//遞歸解決Pi}T←MERGE（y1，y2，…，yk）//合并子問題Return（T）}算法2.2其中|P|表示問題P的規(guī)模；為一閾值，表示當問題P的規(guī)模不超過時，問題已容易解出，不必再繼續(xù)分解。ADHOC（P）是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。因此，當P的規(guī)模不超過時，直接用算法ADHOC（P）求解。算法MERGE（y1，y2，…，yk）是該分治法中的合并子算法，用于將P的子問題P1、P2、…、Pk的相應(yīng)的解y1、y2、…、yk合并為P的解。根據(jù)分治法的分割原則，原問題應(yīng)該分為多少個子問題才較適宜？各個子問題的規(guī)模應(yīng)該怎樣才為適當？這些問題很難予以肯定的回答。但從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子問題規(guī)模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。分治法的合并步驟是算法的關(guān)鍵所在。有些問題的合并方法比較明顯，有些問題合并方法比較復(fù)雜，或者是有多種合并方案；或者是合并方案不明顯。究竟應(yīng)該怎樣合并，沒有統(tǒng)一的模式，需要具體問題具體分析。用分治法設(shè)計大整數(shù)乘法明顯地，如果用經(jīng)典的小學生乘法計算兩個位數(shù)的大整數(shù)，將需要做次乘法運算。似乎不可能有一種算法能使乘法運算次數(shù)少于，但事實證明并非如此。分治法就是一個明顯的例子。設(shè)和都是位的進制整數(shù)，現(xiàn)在要計算它們的乘積。將和分別分為2段，每段的長為位(為簡單起見，假設(shè)是2的冪)，如圖2.3所示。圖2.3大整數(shù)和的分段由此，，。這樣，和的乘積為：…（2.5）如果按照公式（2.5）計算，則我們必須進行4次位整數(shù)的乘法(，，和)，以與3次不超過位的整數(shù)加法(分別對應(yīng)于公式(2.1)中的加號)，此外還要做2次進位處理(分別對應(yīng)于公式（2.5）中乘和乘)。所有這些加法和進位共用步運算。設(shè)是2個n位整數(shù)相乘所需的運算總數(shù)，由公式（2.5），則有：………（2.6）由此可得。要想改進算法的計算復(fù)雜性，必須減少乘法次數(shù)。為此我們把XY寫成另一種形式:………（2.7）雖然公式(2.7)看起來比公式（2.5）要復(fù)雜些，但它僅需做3次位整數(shù)的乘法(，和)，6次加、減法和2次進位。由此可得：….………（2.8）用解遞歸方程的套用公式法，可得其解為：………………（2.9）由此可見，改用分治法做大整數(shù)乘法，從理論上講，效率有明顯提高。根據(jù)以上描述的思想，得出大整數(shù)相乘的偽代碼算法MULT，如下所示：FunctionMULT(X，Y，n){//X和Y為2個小于n位的無符號整數(shù)，返回結(jié)果為X和Y的乘積XYif（n=1）return(X*Y)else{A=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)給出分治算法的時間復(fù)雜度，現(xiàn)在只討論該算法的空間復(fù)雜度。由公式（2.7）可以看出，存儲、需要個單元格，存儲、A、B、C、D需要個單元格，存儲和需要個單元格。由此可得，X乘以Y需要存儲空間：….……（2.10）用解遞歸方程的套用公式法，可得其解為：………………（2.11） 于是，用分治法實現(xiàn)大整數(shù)相乘的時間復(fù)雜度為，空間復(fù)雜度為。疊加分治法由2.1節(jié)和2.2節(jié)對疊加法和分治法的描述與其效率的分析可知，在理論上講，分治法的時間效率要高于疊加法。但是，在實際上并非如此[6]。當整數(shù)位數(shù)很?。ㄈ缥粩?shù)小于600）時，分治法的效率反而不如疊加法。這是因為分治法在分割和合并過程中要消耗掉大量的時間，規(guī)模越小，分割合并所占的時間比例越大。試想，用另一種方法。既可以避免疊加法在運算過程中因規(guī)模增大，時間復(fù)雜度以增大；又可以避免因分治法分得過細而帶來的分割組合時間的大量增加。這就是本文要提出的疊加分治法。疊加分治法是用分治思想，把超大整數(shù)分割成較小整數(shù)（一般在30位左右），再用疊加法計算較小整數(shù)的積，最后合并為超大整數(shù)的積。疊加分治法的偽代碼描述如下所示：FunctionMULT(X，Y，n){//X和Y為2個n位的無符號整數(shù)，返回結(jié)果為X和Y的乘積XYif（n<=LL）{//LL為分割上限，當乘數(shù)的規(guī)模小于LL，不再分割，調(diào)用疊加運算ReturnPen-and-Pencil(X,Y)//用疊加法計算X，Y的積}else{A=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=(m1左移2n位+(m1+m2+m3)左移n位+m3)return(S)}}算法2.4算法演示設(shè)計為證明第二章所提出的疊加分治算法性能的高效性，本章在VB平臺下設(shè)計了一個演示程序。概要設(shè)計為證明本文提出的疊加分治算法性能的高效性，需要用不同的方法對同一對大整數(shù)做乘法運算。因此本演示程序需要完成四個方面的功能：分治實現(xiàn)大整數(shù)乘法運算、疊加實現(xiàn)大整數(shù)乘法運算、疊加分治實現(xiàn)大整數(shù)乘法運算以與它們的效率與結(jié)果的比較。當用疊加分治法實現(xiàn)且分治上限變?yōu)?時，疊加分治法就退化為分治法。因此，該演示程序大致可以分為三個模塊：主調(diào)用模塊、疊加算法模塊、疊加分治與分治共用模塊，如圖3.1所示。演示程序疊加算法模塊疊加算法模塊主調(diào)用模塊疊加分治及分治共用模塊息圖3.1模塊關(guān)系圖現(xiàn)在對這三個的功能模塊做概括說明：主調(diào)用模塊：實現(xiàn)調(diào)用疊加算法模塊、疊加分治與分治共用模塊和比較運算結(jié)果的正確性。疊加算法模塊：完成對大整數(shù)的疊加運算。疊加分治與分治共用模塊：完成對大整數(shù)的分治運算和疊加分治運算。詳細設(shè)計主調(diào)用模塊設(shè)計1、設(shè)計界面，如圖3.2所示：圖3.2主調(diào)用模塊界面2、主界面窗體與其控件屬性設(shè)置表3.1主界面窗體與其控件的屬性對象功能屬性設(shè)計時屬性值說明Form3程序運行主界面Caption大整數(shù)乘法器Command1引導疊加法界面Caption疊加法運算器Command2引導疊加分治法界面Caption疊加分治法運算器Command3判斷兩種算法計算結(jié)果是否相等Caption兩種算法計算結(jié)果相等否3、窗體中主要過程與其代碼的文字簡述PrivateSubCommand1_Click()Callform.pen-and-pencil‘調(diào)用疊加法模塊EndSubPrivateSubCommand2_Click()Callform.cent‘調(diào)用疊加分治法模塊EndSubPrivateSubCommand3_Click()判斷兩種方法運算的結(jié)果是否相等EndSub疊加法模塊設(shè)計1、疊加算法界面設(shè)計，如圖3.2所示：圖3.2疊加算法模塊界面2、疊加運算窗體與其控件屬性設(shè)置表3.2疊加運算窗體與其控件的屬性對象功能屬性設(shè)計時屬性值說明Form4用戶界面窗體Caption疊加法用戶界面標題Command1調(diào)用運算乘積函數(shù)Caption做乘積運算命令按鈕標題Command2清空輸入輸出口Caption清空命令按鈕標題Text1輸入乘數(shù)Text空白MultiLineTrue允許多行輸入ScrollBars2垂直滾動條Text2輸入乘數(shù)Text空白MultiLineTrue允許多行輸入ScrollBars2垂直滾動條Text3輸出積Text空白MultiLineTrue允許多行輸入ScrollBars2垂直滾動條LockedTrue不允許輸入Label1指示輸入位置Caption因數(shù)1Label2指示輸入位置AutoWrapTrue控件可以自動調(diào)整Caption因數(shù)2Label3指示輸出位置AutoWrapTrue控件可以自動調(diào)整Caption積Label4統(tǒng)計因數(shù)1的字符長度AutoWrapTrue控件可以自動調(diào)整Caption空Label5統(tǒng)計因數(shù)2的字符長度AutoWrapTrue控件可以自動調(diào)整Caption空Label6統(tǒng)計積的字符長度AutoWrapTrue控件可以自動調(diào)整Caption空3、窗體中主要過程與其代碼的文字簡述PrivateSubCommand1_Click()T=hefa(text1.text,text2.text)‘對輸入因數(shù)字符串合法性檢查，‘如果合法則返回True；否則，返回Falseif(T)thenxCint(text1.text)；yCint(text2.text)‘因數(shù)字符串轉(zhuǎn)化為‘整數(shù)賦值給數(shù)組x、yr疊加運算（x，y）‘疊加運算x、y賦給rtext3.textCchar(r)‘結(jié)果數(shù)組轉(zhuǎn)化因數(shù)字符串賦值文本3輸出為Else報錯處理EndIfEndSubPrivateSubText1_KeyPress(KeyAsciiAsInteger)控制因數(shù)1的輸入，只有輸入合法才讓輸入文本接受EndSubPrivateSubText2_KeyPress(KeyAsciiAsInteger)控制因數(shù)2的輸入，只有輸入合法才讓輸入文本接受EndSub疊加分治法模塊設(shè)計1、疊加分治法模塊界面設(shè)計，如圖3.3所示：圖3.3疊加分治法模塊界面2、疊加分治運算窗體與其控件屬性設(shè)置表3.3疊加分治運算窗體與其控件的屬性對象功能屬性設(shè)計時屬性值說明Form1用戶界面窗體Caption疊加分治法用戶界面標題Command1調(diào)用運算乘積函數(shù)Caption做乘積運算命令按鈕標題Command2清空輸入輸出口Caption清空命令按鈕標題Text1輸入乘數(shù)Text空白MultiLineTrue允許多行輸入ScrollBars2垂直滾動條Text2輸入乘數(shù)Text空白MultiLineTrue允許多行輸入ScrollBars2垂直滾動條Text3輸出積Text空白MultiLineTrue允許多行輸入ScrollBars2垂直滾動條LockedTrue不允許輸入Text4輸入分治下限Text25默認下限Label1指示輸入位置Caption因數(shù)1AutoWrapTrue控件可以自動調(diào)整Label2指示輸入位置Caption因數(shù)2AutoWrapTrue控件可以自動調(diào)整Label3指示輸出位置Caption積AutoWrapTrue控件可以自動調(diào)整Label4統(tǒng)計因數(shù)1的字符長度Caption空AutoWrapTrue控件可以自動調(diào)整Label5統(tǒng)計因數(shù)2的字符長度Caption空AutoWrapTrue控件可以自動調(diào)整Label6統(tǒng)計積的字符長度Caption空AutoWrapTrue控件可以自動調(diào)整Label7記錄程序開始時間Caption空AutoWrapTrue控件可以自動調(diào)整Label8記錄程序結(jié)束時間Caption空AutoWrapTrue控件可以自動調(diào)整Label9提示分治下限Caption分治下限3、窗體中主要過程與其代碼的文字簡述DimTtimeAsInteger‘記錄分治下限SubMul(x()AsInteger,y()AsInteger,r()AsInteger)Ifx(0)<TtimeThen‘如果位數(shù)小于下限，則調(diào)用疊加法CallPensM(x,y,r)ElseA=left(x,len(x)/2):B=right(x,(len(x)+1)/2)C=left(x,len(y)/2):D=right(x,(len(y)+1)/2)E=A-B:F=C-DCallMul(A,C,r1)CallMul(B,D,r3)CallMul(E,F,r2)EndIfEndSubPrivateSubPensM(x()AsInteger,y()AsInteger,r()AsInteger)DimiAsInteger,jAsIntegerFori=x(0)To1Step-1Forj=y(0)To1Step-1r(i+j)=r(i+j)+x(i)*y(j)NextjNextiEndSubPrivateSubCommand1_Click()T=hefa(text1.text,text2.text,Text4.Text)‘輸入字符串合法性檢查，‘如果合法則返回True；否則，返回Falseif(T)thenTtime=CInt(Text4.Text)xCint(text1.text)；yCint(text2.text)‘因數(shù)字符串轉(zhuǎn)化為‘整數(shù)賦值給數(shù)組x、yr疊加分治運算（x，y）‘疊加運算x、y賦給rtext3.textCchar(r)‘結(jié)果數(shù)組轉(zhuǎn)化因數(shù)字符串從文本3輸出為Else報錯處理EndIfEndSub結(jié)果與分析圖3.4~3.6展示了在VB平臺上實現(xiàn)上述三種方法對兩個大整數(shù)（都是8192位9）相乘，在時間效率上的差異?？梢钥闯?，用疊加法耗時2秒（圖3.4），用分治法耗時8秒（圖3.5），疊加分治法耗時不到1秒（圖3.6）。通過它們的差異，得出如下結(jié)論：用疊加分治法耗時最少。因而，疊加分治法是一種效率很高的大整數(shù)乘法運算方法。同時，也必須注意：當兩乘數(shù)位數(shù)相差很大時，疊加分治法的效率反而不如疊加法的效率。所以當兩整數(shù)位數(shù)相差很大時，疊加法的效率可能比疊加分治法的效率更高。圖3.4疊加法運算結(jié)果圖3.5分治法運算結(jié)果圖3.6疊加分治法運算結(jié)果結(jié)論本文以大整數(shù)相乘在計算機中的表示為題目，主要討論了三個方面的問題：疊加法實現(xiàn)大整數(shù)乘法、分治法實現(xiàn)大整數(shù)乘法、疊加分治法實現(xiàn)大整數(shù)乘法。大整數(shù)疊加運算是傳統(tǒng)的經(jīng)典算法。在這一部分討論了大整數(shù)的表示方法，大整數(shù)的表示采用數(shù)組的形式，每個數(shù)組元素存放一位十進制整數(shù)，以與在這種大整數(shù)的存儲形式下，探討了在密碼學中經(jīng)常用到的大整數(shù)疊加運算方法是如何實現(xiàn)的。分治法是比較著名的算法思想，分治法實現(xiàn)大整數(shù)乘法從理論上提高了大整數(shù)乘法運算的效率。本部分主要討論了分治法是如何實現(xiàn)大整數(shù)乘法運算的，并對實現(xiàn)效率做出定性分析。在用疊加分治法實現(xiàn)大整數(shù)乘這一部分中，通過分析疊加法、分治法的優(yōu)劣和它們的應(yīng)用環(huán)境，結(jié)合它們的特點，提出了把疊加法和分治法相結(jié)合的方法——疊加分治法。在最后一章，做了一個演示程序，演示了本文提出算法的正確性和高效性，對三種算法進行了定性分析。下一步工作與有待改進之處：優(yōu)化算法，進一步提高運算效率。在現(xiàn)有基礎(chǔ)之上，實現(xiàn)大整數(shù)的除法運算。在大整數(shù)四則混合運算基礎(chǔ)上，繼續(xù)進行其他有關(guān)模的運算算法的研究。參考文獻[1] 原巍，許琪，沈緒榜.大整數(shù)乘法器設(shè)計.微電子學與計算機，2003，2003增刊：1-3[2] 羅洋.大整數(shù)乘法的計算機處理.遼林師專學報，2005，第1期：39-40[3] 吳曉麗，吳鋒.計算機中的大整數(shù)運算技術(shù).武警工程學院學報，1999，第15卷第2期：35-37[4] M.H.Alsuwaiyel著，吳偉昶等譯.算法設(shè)計技巧與分析.北京：電子工業(yè)出版社，2004.[5] 王曉東.算法設(shè)計與分析.北京：清華大學出版社，2003.[6] [美]AnanyLevitin.IntroductiontoTheDesignandAnalysisofAlgorithms.北京：清華工業(yè)出版社，2003.[7] 石研，姚晟.大整數(shù)算術(shù)運算的實現(xiàn).安慶師范學院學報（自然科學版）.2004，第10卷第2期：75-77[8] 楊劍等.字符化大整數(shù)運算系統(tǒng)的構(gòu)造與實現(xiàn).揚州大學學報（自然科學版）.2000，第3卷第4期：52-56[9] 凌晨，買磊.基于兩種不同存儲方式的大整數(shù)運算與性能比較.安慶師范學院學報（自然學報）.2003，第9期第2版：86-88[10] 李愛武.密碼學中的大整數(shù)運算與其應(yīng)用.[學位論文].廣州：中山大學，2002[11]余祥宣等.計算機算法基礎(chǔ)（第二版）.武漢：華中科技大學出版社，2004[12]周彬.大整數(shù)模運算算法研究與實現(xiàn).[學位論文].成都：電子科技大學，2001/ruanjiansp/guide/1388.htm附錄英譯漢F1Divide-and-ConquerandMultiplicationofLargeIntegersF1.1Divide-and-ConquerDivide-and-conquerisprobablythebest-knowgeneralalgorithmdesigntechnique.Thoughitsfamemayhavesomethingtodowithitscatchyname,itiswelldeserved:quiteafewefficientalgorithmsarespecificimplementationsofthisgeneralstrategy.Divide-and-conqueralgorithmsworkaccordingtothefollowinggeneralplan:1.Aproblem’sinstanceisdividedintoseveralsmallerinstanceofthesameproblem,ideallyofaboutthesamesize.2.Thesmallerinstancesaresolved(typicallyrecursively,thoughsometimesadifferentalgorithmisemployedwheninstancesbecomesmallenough).3.Ifnecessary,thesolutionsobtainedforthesmallerinstancesarecombinedtogetasolutiontotheoriginalproblem.Thedivide-and-conquertechniqueisdiagrammedinFigure1,whichdepictsthecaseofdividingaproblemintotowsmallersubproblems,byfarthemostwidelyoccurringcase(atlestfordivide-and-conqueralgorithmsdesignedtobeexecutedonasingle-processorcomputer).SSolutiontotheoriginalproblemProblemofsizenSubproblem1ofsizeSubproblem1ofsizeSolutiontosubproblem2Solutiontosubproblem1Figure1Divide-and-conquertechnique(typicalcase)Asanexample,letusconsidertheproblemofcomputingthesimofnumbers.If,wecandividetheproblemintotowinstancesofthesameproblem:tocomputethesumofthefirstnumbersandtocomputethesumoftheremainingnumbers.(Ofcourse,ifwesimplyreturnastheanswer.)Onceeachofthesetowsumsiscomputed(byapplyingthesamemethod,i.e.,recursively),wecanaddtheirvaluestogetthesuminquestion:Isthisanefficientwaytocomputethesumofnumbers?Amomentofreflection(whycoulditbemoreefficientthanthebrute-forcesummation?),asmallexampleofsumming,say,fournumbersbythisalgorithm,aformalanalysis(whichfollows),andcommonsense(wedonotcomputesumsthisway,dowe?)allleadtoanegativeanswertothisquestion.Thus,noteverydivide-and-conqueralgorithmisnecessarilymoreefficientthanevenabrute-forcesolution.ButoftenourprayerstotheGoddessofAlgorithmicsareanswer,andthetimespentonexecutingthedivide-and-conquerplanturnsouttobesmallerthansolvingaproblembyadifferentmethod.Infact,thedivide-and-conquerapproachyieldssomeofthemostimportantandefficientalgorithmsincomputerscience.Wediscussafewclassicexamplesofsuchalgorithmsinthischapter.Thoughweconsideronlysequentialalgorithmshere,itisworthkeepinginmindthatthedivide-and-conquertechniqueisideallysuitedforparallelcomputations,inwhicheachsubprolemcanbesolvedsimultaneouslybyitsownprocessor.Thesumexampleillustratesthemosttypicalcaseofdivide-and-conquer:aproblem’sinstanceofsize.Moregenerally,aninstanceofsizecanbedividedintoseveralinstancesofsize,withofthemneedingtobesolved.(Here,andareconstants;and.)Assumingthatsizeisapowerof,simplifyouranalysis,wegetthefollowingrecurrencefortherunningtime:………..(1)whereisafunctionthataccountsforthetimespentondividingtheproblemintosmalleronesandoncombiningtheirsolutions.(Forthesummationexample,and.)Recurrence(1)iscalledthegeneraldivide-and-conquerrecurrence.Obviously,theorderofgrowthofitssolutiondependsonthevaluesoftheconstantsandandtheorderofgrowthofthefunction.Theefficiencyanalysisofmanydivide-and-conqueralgorithmsisgreatlysimplifiedbythefollowingtheorem.MASTERTHEOREMIfwhereinrecurrenceequation(1),then….……….(2)(Analogousresultsholdfortheandnotations,too)Forexample,therecurrenceequationforthenumberofadditionsmadebythedivide-and-conquersummationalgorithm(seeabove)oninputsofsizeis……………..………..……..(3)Thus,forthisexample,,,and;hence,since,….………….…….………(4)Notethatwewereabletofindthesolution’sefficiencyclasswithoutgoingthroughthedrudgeryofsolvingtherecurrence.But,ofcourse,thisapproachcanonlyestablishasolution’sorderofgrowthtowithinanunknownmultiplicativeconstantwhilesolvingarecurrenceequationwithaspecificinitialconditionyieldsanexactanswer(atlestfor’sthatarepowerof).F1.2MultiplicationofLargeIntegersSomeapplications,notablymoderncryptology,requiremanipulationofintegersthatareover100decimaldigitslong.Obviously,suchintegersaretoolongtofitinasinglewordofamoderncomputer,andhencetheyrequirespecialtreatment.Thispracticalneedsupportsinvestigationsofalgorithmsforefficientmanipulationoflargeintegers.Inthissection,weoutlineaninterestingalgorithmformultiplyingsuchnumbers.Obviously,ifweusetheclassicpen-and-pencilalgorithmformultiplyingtow-digitintegers,eachofthedigitsofthefirstnumbersismultipliedbyeachofthedigitsofthesecondnumberforthetotalofdigitmultiplications.(Ifoneofthenumbershasfewerdigitsthantheother,wecanpadashorternumberwithleadingzerostoequaltheirlengths.)Thoughitmightappearthatitwouldbeimpossibletodesignanalgorithmwithfewerthandigitmultiplications,itprovesnottobethecase.Themiracleofdivide-and-conquercomestotherescuetoaccomplishthisfeat.Todemonstratethebasicideaofthealgorithm,letusstartwithacaseoftow-digitintegers,23and14.Thesenumberscanberepresentedasfollows:andNowletusmultiplythem:Thelastformulayieldsthecorrectanswerof322,ofcourse,butitusesthesamefourdigitmultiplicationsasthepen-and-pencilalgorithm.Fortunately,wecancomputethemiddletermwithjustonedigitmultiplicationbytakingadvantageoftheproducts()andthatneedtobecomputedanyway:Ofcourse,thereisnothingspecialaboutthenumberswejustmultiplied.Foranypairoftow-digitnumbersand,theirproductcanbecomputedbytheformulawhereistheproductoftheirfirstdigitsistheproductoftheirseconddigitsistheproductofthesumofthe’sdigitsandthesumofthe’sdigitsminusthesumofand.Nowweapplythistricktomultiplyingtow-digitintegersandwhereisapositiveevennumber.Letusdividebothnumbersinthemiddle—afterall,wepromisedtotakeadvantageofthedivide-and-conquertechnique.Wedenotethefirsthalfofthe’sdigitsbyandthesecondhalfby;for,thenotionsareand,respectively.Inthesenotions,impliesthatandimpliesthat.Therefore,takingadvantageofthesametrickweusedfortow-digitnumbers,wegetwhereistheproductoftheirfirsthalvesistheproductoftheirsecondhalvesistheproductofthesumofthe’shalvesandthesumofthe’shalvesminusthesumofand.Ifiseven,wecanapplythesamemethodforcomputingtheproducts,and.Thus,ifisapowerof2,wehavearecursivealgorithmforcomputingtheproductoftow-digitintegers.Initspureform,therecursionisstoppedwhenbecomesone.Itcanalsobestoppedwhenwedeemsmallenoughtomultiplythenumbersone.Itcanalsobestoppedwhenwedeemsmallenoughtomultiplythenumbersofthatsizedirectly.Howmanydigitmultiplicationsdoesthisalgorithmmake?Sincemultiplicationof-digitnumbersrequiresthreemultiplicationsof-digitnumbers,therecurrenceforthenumberofmultiplicationswillbeSolvingitbybackwardsubstitutionsforyieldsSince(Onthelaststep,wetakeadvantageofthefollowingpropertyoflogarithms:)Youshouldkeepinmindthatformoderatelylargeintegersthisalgorithmwillprobablyrunlongertheclassicone.BrassardandBratley([BB96],pp.70-71)reportthatintheirexperimentsthedivide-and-conqueralgorithmstartedtooutperformthepen-and-pencilmethodonintegersover600digitslong.Ifyouprograminanobject-orientedlanguagesuchasJava,C++,orSma