大數(shù)運算法則

1、中國科學技術大學繼續(xù)教育學院課程設計論文報告論文題目：大數(shù)四則運算的C+實現(xiàn)學員姓名：王歡 學 號：TB04039103專 業(yè)：計算機科學與技術 指導教師：日 期：2007年1月10日大數(shù)四則運算的C+實現(xiàn)摘要大數(shù)運算不僅僅運用在密碼學中，還運用在一些物理學研究、生物學，化學等科目中。 大數(shù)運算，意味著參加的值和計算結果通常是以上百位數(shù)，上千位數(shù)以及更大長度之間的整數(shù)運 算。例如大家所熟知圓周率n的值，在一般的數(shù)值計算中用到圓周率的不須要多大的精度，但在 計算一些星球或是星系上的體積面積時便顯的誤差很大了，這就要求n值計算的精度達到幾百萬 位甚至更高，才能縮小誤差。人工計算是遠遠不行了，而且本

2、身誤差也無法估計。只有在計算機 中用大數(shù)運算求兀值了。又如，考古學家計算石頭內(nèi)的碳元素衰變來考證地球形成的時間，更是 將計算的結果精確到了百年以內(nèi)。所以說大數(shù)的運算是涉及領域多，應用范廣，與我們生活息息 關。在此，我采用一個在C語言下實現(xiàn)計算大數(shù)運算的一個程序為例，講解包括了大數(shù)的加法， 減法，乘法和除法及求冪運算的算法及代碼。關鍵詞大數(shù)計算網(wǎng)絡安全密碼學隨著計算機網(wǎng)絡技術的發(fā)展和因特網(wǎng)的廣泛普及，網(wǎng)絡安全事故逐年增加，黑客的攻擊已經(jīng) 和病毒并列成為對信息安全影響最嚴重的兩大危害。其很大程度上是被黑客破解了用戶的計算機 名及登陸密碼及資料的加密較差，而使得黑客來對網(wǎng)民的資料如同自己般的隨意更改

3、和破壞。而 安全的密碼和賬號成為了網(wǎng)民的安全之本，怎么才能提高安全問題成為的人們和社會關注的問 題。而加密大部又是以大素數(shù)的計算為基礎的，如非對稱密碼體制RSA的安全性依賴于對大數(shù)進 行因數(shù)分解的耗時性。一個二進制數(shù)n的因數(shù)分解所需的機器周期大約是 expln(n)ln(ln(n)1/2。若機器周期為1s，b為二進制數(shù)的位數(shù)，分解n=2b所需時間如 下表所示：位數(shù)1002003005007501000時間30秒3天9年1兆年2*109 年6*1015 年實際應用中，p、q的選擇都在10200數(shù)字以上，這樣每個明文塊的二進制位數(shù)可達664比 特，即83個字節(jié)。而DES只有8個字符。一般認為，對于

4、當前的計算機水平，選擇1024位長的 密鑰就可認為是無法攻破的了。數(shù)字存儲的實現(xiàn)大數(shù)計算的因數(shù)和結果精度一般是少則數(shù)十位，多則幾萬位。在C語言中定義的類型中精度 最多只有二十多位，因而我們采取用鏈表存貯的方式來存放大數(shù)。在計算中會用到從高位開始計 算，和從低位開始計算數(shù)值的兩種情況。所以我們將鏈表定義為雙向鏈表，其中為一個單元來存 貯數(shù)據(jù)，一個指針指向前方的數(shù)據(jù)，另一個指向后的數(shù)據(jù)。其結構為：struct Node /定義一個雙向鏈表用來存貯結果 char data;/數(shù)據(jù)*定義為字符的原因：要顯示負號Node *next;/尾指針Node *ahead;/首指針；各種算法2.1加法運算的實現(xiàn)

5、加法計算還是比較容易的，我們也是先從低位算起，因為只須要對應的位相加，再加上前一 位的進位，再去判斷是否本位是否有進位，有則把本位數(shù)字改為減去它的權，也就是10，再置 進位為1。如果沒有進位，則給進位賦值0。在程序時應注意：1、兩個加數(shù)中那一個數(shù)的位數(shù)長，以位數(shù)長的作為循環(huán)變量；2、結束循環(huán)時，不僅僅是最后一位加完就停止，還應加入如果有進位，也要再循環(huán)一次。如最后一位是9,進位是1，則相加時進位，要加上進位這一位值。具體看代碼，輸入輸出時和 乘法的一樣。/*函數(shù)名稱：大數(shù)加法*函數(shù)過程：1比較兩個數(shù)那一個長2以長的作為循環(huán)次數(shù)3對應項相加進位存貯直到下高位相加用4直到循環(huán)結束5 !沒設計負數(shù)相

6、加*入口參數(shù)：numa，numb，result 字符串*出口參數(shù)：無*編輯環(huán)境：winSP2 + VC2003 + C+*/void addition(char *numa, char *numb,char *result) / 計算兩大數(shù)之和char *pna = findend(numa); / 指向 numa 的一個指針。point numa pna 指向乘數(shù)的最低位，char *pnb = findend(numb); 指向numb的一個指針/pnb指向被乘數(shù)的最低位，int along=(int)strlen(numa); 標記數(shù)字 a 的長度；int blong=(int)strl

7、en(numb); 標記數(shù)字 b 的長度；int times = 0; /標致要計算多少次。int carry=0,temp_result; 存貯進位和臨時結果的Node *head, /用于存貯頭指針*pstart, /用于存貯計算時的首指針*pnew; /作于申請新結點head = pstart =new Node; 初始化首結點和頭結點。pstart - data = 0;pstart - next = NULL;pstart - ahead = NULL;if (abigerb(numa ,numb)=1)times = (int)strlen(numa); /比較兩個字符串長度，以大

8、的作為循環(huán)次數(shù)elsetimes = (int)strlen(numb);pna = findend(numb); 交換指針pnb = findend(numa);along=(int)strlen(numb); 標記數(shù)字 a 的長度；blong=(int)strlen(numa); 標記數(shù)字 b 的長度；while (times & (times=0)| carry != 0)if(!pstart-next) 如果當前為空結點，則申請新結點pnew = new Node;pnew - data = 0;pnew - next = NULL;pnew - ahead = pstart;psta

9、rt - next = pnew;else temp_result =(pstart-data +(*pna-48) + (*pnb-48)+carry) ; / 自身的值+新值+ 進位作為當前的新值pstart - data = temp_result%10; /存貯個位carry = temp_result/10; 存貯進位pstart = pstart - next; 結點移動blong一;if(blong0)pnb-; /指針移向被加數(shù)高位else *pnb=48; 之后相減就變?yōu)榱?0不作任何運算；pna-; /加數(shù)指針移動，pstart =head; 尋找鏈表的結尾點while(p

10、start-next != 0)pstart-data += 48; /!逆順輸出 pstart = pstart-next ;int tip = 0; /轉為字符串用pstart = pstart-ahead ; 找有效字/coutdata;/coutahead ;resulttip = 0;pstart =head; 釋放空間while(pstart-next != 0)pnew = pstart-next ;delete pstart;pstart =pnew;return ; 2.2減法運算的實現(xiàn)減法稍微有一點復雜，因為會處理負數(shù)，而我們所用的是字符串的形式來保存數(shù)字也是為 這一點。否

11、則用整型或其它類型時，則表示處理、保存時會相當復雜。算法也是從低位開始減。 先要判斷減數(shù)和被減數(shù)那一個位數(shù)長，減數(shù)位數(shù)長是正常減；被減數(shù)位數(shù)長，則被減數(shù)減減數(shù)， 最后還要加上負號；兩數(shù)位數(shù)長度相等時，最好比那一個數(shù)字大，否則負號處理會很繁瑣；處理 每一項時要，如果前一位相減有借位，就先減去上一位的借位，無則不減，再去判斷是否能夠減 開被減數(shù)，如果減不開，就要借位后再去減，同時置借位為1，否則置借位為0。這有一我寫的比較兩個數(shù)字符串大小的函數(shù)：返回值說明：0 是 alongblong ; 2 是 along=blongint abigerb(char *numa, char *numb) /比較

12、兩個數(shù)最高位那一個大 int along=(int)strlen(numa); 標記數(shù)字 a 的長度；int blong=(int)strlen(numb); 標記數(shù)字 b 的長度；char *pna = numa; /指向數(shù)A的最高位，char *pnb = numb; /指向數(shù)B的最高位，if (alongblong) return 1;if (along=blong)while(*pna) /比較兩個數(shù)那一個大if(*pna*pnb)return 1;else if(*pna data = 0;pstart - next = NULL;pstart - ahead = NULL;if (

13、abigerb(numa ,numb)times = strlen(numa);/比較兩個字符串長度，以大的作為循環(huán)次數(shù)else /交換位置以降低難度(times = strlen(numb);/讓數(shù)(字符串)長的減去數(shù)(字符串)短的pna = findend(numb);/交換指針pnb = findend(numa);along=(int)strlen(numb);/標記數(shù)字 a 的長度；blong=(int)strlen(numa);/標記數(shù)字 b 的長度；isnegative=1;/標記最后要加上負號while (times- & (times=0)| carry != 0)/carr

14、y != 0 說沒有借位 時(if(!pstart-next)/如果當前為空結點，則申請新結點(pnew = new Node;pnew - data = 0;pnew - next = NULL;pnew - ahead = pstart;pstart - next = pnew;if(times data = -3 ;/讓它等于負號-/-3來源于負號與0相差3。break;else(if ( *pna = *pnb )/減數(shù)等于被減數(shù)時。結果等于直截相減的結果；并 置借位為0(if(carry=0)pstart - data = (*pna-48)-(*pnb-48); /111-11 的

15、情況else(pstart-data = (*pna-48)-(*pnb-48)+10 -carry;/1121T112carry=1;if( *pna *pnb )/減數(shù)大于被減數(shù)時。結果等于直截相減的結果；并置 借位為0(pstart - data = (*pna-48)-(*pnb-48)-carry; 存貯個位carry=0;else if( *pna 0) pstart-data = (*pna-48)-(*pnb-48)+10 -carry;/13-5 的情況作為新值else pstart-data = (*pnb-48)-(*pna-48) -carry; /3-5 作為當前 的

16、新值carry=1;pstart = pstart - next;/結點移動blong;if(blong0)pnb-;/指針移向被減數(shù)高位else*pnb=48;/之后相減就變?yōu)榱?0不作任何運算，其實可以優(yōu)化的。但代 碼會長！而且還需要重新開結點。所以放棄；pna-;/被數(shù)指針移動，if(isnegative=1)/加上負號處理。增加一長度并置為負號(pnew = new Node;pnew - data = 0;pnew - next = NULL;pnew - ahead = pstart;pstart - next = pnew;pstart-data=-3;/因為尋找鏈表的結尾點要統(tǒng)

17、一加48。又因為-是45。所以等于-3pstart =head;/尋找鏈表的結尾點while(pstart-next != 0)(pstart-data += 48;/! 逆順輸出pstart = pstart-next ;int tip = 0;/轉為字符串用clear0=0;/消除結果最前面無用的0 13-5 = 08的效果.修改 字符串的首指針pstart = pstart-ahead ;/找有效字while(pstart != 0)/輸出正序的結果；(if (clear0=0 & (int)pstart-data)=48&pstart-ahead!=0)/ 消除結果最前面無用的0;/不

18、輸出任何東西elseresulttip+ = pstart-data;if(int)pstart-data)!=48&(int)pstart-data)!=45)clear0=1;/ 號pstart = pstart-ahead ;resulttip = 0;pstart =head; 釋放空間while(pstart-next != 0)(pnew = pstart-next ;delete pstart;pstart =pnew;return ;2.3乘法運算的實現(xiàn)首先說一下乘法計算的算法，從低位向高位乘，在豎式計算中，我們是將乘數(shù)第一位與被乘 數(shù)的每一位相乘，記錄結果，之后，用第二位相乘

19、，記錄結果并且左移一位，以此類推，直到計 算完最后一位，再將各項結果相加。得出最后結果。當然我們可以直接用這種方法，但要用多個 鏈表來保存計算出的分結果，之后結果再相加得到最后結果，但是這樣會浪費很多空間，我們 可以再優(yōu)化一下，就是只用一人鏈表來表示結果，先把第一位乘數(shù)與被乘數(shù)的結果保存在鏈表中， 之后把存儲結果的頭部后移一位、也就是從鏈表的第二加起，當?shù)诙怀藬?shù)與被乘數(shù)結果加到第 二之后的各個項內(nèi)。以此類推，直到結束。這樣就可以用一個鏈表來存儲相乘后的結果。在程序時應注意：1、傳入的乘數(shù)和被乘數(shù)是以字符串形式放入的話，要讓指針指向最后一位，我自己寫了個 函數(shù)來完成這件事。鏈表傳入也要找到最后

20、一向來計算；2、因為傳入和保存的都是字符，所以計算時要將字符轉化為數(shù)字，算完再轉化為字符存儲;3、另外進位時要處理，當前的值加上進位的值再看本位數(shù)字是否又有進位；4、輸出時要逆序輸出，因為鏈表首指針是存的結果的最低位。我的函數(shù)為了對應輸入輸出 結果的一致性，都有采用了字符串輸出，所以在輸出時又將鏈表轉為了字符串。具體代碼如下：/*函數(shù)名稱：大數(shù)乘法*函數(shù)過程：1輸入兩個大數(shù)作為字符串2作一個雙向鏈表3兩個指針分別指向數(shù)字字符串的最低位4以第一個數(shù)的最低的一個位乘以第二個數(shù)的所有項存于鏈表中5鏈表首指針移6重復4, 5依次從最低位乘到最高位7乘完后因為最低位是鏈表首，最后一位是鏈表尾。所以在逆順

21、輸出鏈表。4直到循環(huán)結束*入口參數(shù)：numa，numb，result 字符串*出口參數(shù)：無*/void multiply(char *numa, char *numb ,char *result)/用來儲結果的)/ 計算乘積(char *pna = findend(numa);/指向 numa 的一個指針。point numa pna 指 向乘數(shù)的最低位，char *pnb = findend(numb);/指向 numb 的一個指針/pnb指向被乘數(shù)的最低位，一int along=(int)strlen(numa);/標記數(shù)字 a 的長度；int blong=(int)strlen(numb

22、);/標記數(shù)字 b 的長度；int carry=0,temp_result;/存貯進位 和臨時結果的Node *head, /用于存貯頭指針*pstart, /用于存貯計算時的首指針*pnew,作于申請新結點*pgo;/作為每計算完一行時，回到下一行起始節(jié)點用，移位標致來用head = pstart =new Node;/初始化首結點和頭結點。pstart - data = 0;pstart - next = NULL;pstart - ahead = NULL;while (along-)(pgo = pstart;/保存進位點blong = (int)strlen(numb);/初始化長度

23、pnb = findend(numb); /初始化指針while (blong- & (blong=0)| carry != 0)(if(!pstart-next)/如果當前為空結點，則申請新結點(pnew = new Node;pnew - data = 0;pnew - next = NULL;pnew - ahead = pstart;pstart - next = pnew;if(blongdata+(*pna-48)*(*pnb-48)+carry);/ 自 身值 +新值+進位作為新值pstart - data = temp_result%10; /存貯個位carry = temp_

24、result/10;/存貯進位pstart = pstart - next;/結點移動pnb-; /指針移向被乘數(shù)高位pstart = pgo-next; 前進一個位置；pna-;/指針移向乘數(shù)高位pstart =head;/尋找鏈表的結尾點while(pstart-next != 0)(pstart-data += 48;/!逆順輸出pstart = pstart-next ;int tip = 0;/轉為字符串用pstart = pstart-ahead ;/找有效字while(pstart != 0)/輸出正序的結果；(resulttip+ = pstart-data;pstart =

25、pstart-ahead ;resulttip = 0;pstart =head; 釋放空間while(pstart-next != 0)(pnew = pstart-next ;delete pstart;pstart =pnew;return ;2.4除法運算的實現(xiàn)首先說一下我們所要的結果，當除數(shù)除不開被子除數(shù)時，不用除到小數(shù)，當除數(shù)小于被除數(shù) 時，除數(shù)作為余數(shù)既可，不用再向下除了。除法算法是最容易想到的啦！我們學數(shù)字電路，或模擬電路時里面有用門實現(xiàn)的除法器，做 法是用除數(shù)減被除數(shù)，再用一個加法器去計算存儲結果，算法簡單明了，結果我實現(xiàn)之后，計算 速度大大出乎我的遇料，比算乘方時還慢，經(jīng)仔

26、細想想電路中計算的長度不過8位，16位，32 位，而且都是硬件實現(xiàn)，我們要算的是幾千位，幾萬位。特別是兩數(shù)位長度差很大時計算速度相 當慢，如10000-3時要進行多少次鏈表運算啊。否定了這條算法，經(jīng)不斷思考，發(fā)現(xiàn)另一種方法可行，且效率僅次于減法。就是從高位向低 位減，減時以被除數(shù)長度為單位，從高位取出大于被除數(shù)的字符串，和被除數(shù)相減，減的次數(shù)為 結果，余數(shù)從剩下的除數(shù)高位再取出幾位做補位，直到大于被除數(shù)。再減，循環(huán)減到被減數(shù)大于 余數(shù)加上補位，那么這個新的余數(shù)作為結果返回。在程序時應注意：1、除法算法計算時是用的最高位開始向低位減，所以要注意指針的位置。2、余數(shù)和被減數(shù)相減時，一定要注意：一旦

27、能夠減開被除數(shù)時，一定要每從除數(shù)那里取一個字符時，結果也要對應補一個0。如111222/111。/*函數(shù)名稱：大數(shù)除法2-*函數(shù)想法：1用指針指向除數(shù)的最高位，保存臨時字符串；tempstra+ = pna2如果臨時字符串大于被除數(shù)，則相減。結果等于余數(shù)if(tempstrnumb)tempstr = tempstr - numb3如果小于被除數(shù)且指針到頭，余數(shù)等于臨時字符串if(tempstr *入口參數(shù)：numa，numb，result,remainder 字符串*出口參數(shù)：無*/void divide2( char *numa, char *numb,char *result,char

28、*remainder)/計算除法2(char one二1；/ 臨時字符串.char one2=1;/char zero=0;/char numb26048;/char tempstr6018=；/臨時字符串int ia=0,ia2=0;/tempstr 的指示器bool moveon=false;/翻轉牌pna指向減/pnbchar *pna = numa;/f指 向 numa 的一個指針。point numa 數(shù)的最低位，char *pnb = findend(numb);/指向 numb 的一個指針指向被減數(shù)的最低位，Node *head, /用于存貯頭指針*pstart, /用于存貯計算

29、時的首指針*pnew;作于申請新結點head = pstart =new Node;/初始化首結點和頭結點。pstart - data = 0;pstart - next = NULL;pstart - ahead = NULL;moveon = false;while(*pna)(if(!pstart-next)/如果當前為空結點，則申請新結點(pnew = new Node;pnew - data = 0;pnew - next = NULL;pnew - ahead = pstart;pstart - next = pnew;ia=(int)strlen(tempstr);/取的長度te

30、mpstria+ = *(pna+);tempstria =0; /轉換為字符串if(tempstr0=0)/處理高位也是0的那種 如00(ia2=0;while(tempstria2=0)+ia2;while(ia2=1)/清除無用的 0(ia=ia2-1;tempstria=tempstria2;-ia2;tempstr+ia2=0;while(abigerb(tempstr,numb)0)/如果 tempstr 大于等于 numb(if(tempstr0=0)/處理高位也是0的那種 如00-此乃冗余代碼，留 做記念用(ia2=0;while(tempstria2=0)+ia2;if(ia

31、=ia2 )(moveon = true;break;strcpy(numb2,numb);subtract(tempstr, numb,tempstr);/A-Bstrcpy(numb,numb2);if(tempstr0=-)/若判斷的不準，變?yōu)榱素摂?shù)就再加上B。(strcpy(numb2,numb);addition(tempstr, numb,tempstr);/A-Bstrcpy(numb,numb2);ia2=0; 修正之后的長度。因為加法中未做負數(shù)運算ia=0; /為了消除最后的那一個負號，整體向前移動。while(tempstria2!=0)+ia2;while(ia2=1)/

32、清除無用的 0(tempstria=tempstria+1;+ia;-ia2;tempstria=0;moveon = true;break;pstart-data+ ; 結果自加 moveon = true;if(moveon) pstart = pstart - next;/結點移動strcpy(remainder,tempstr);/存貯余數(shù)int tip = 0;/轉為字符串用pstart =head;/尋找鏈表的結尾點while(pstart-next != 0)(pstart-data += 48;/! 逆順輸出resulttip+ = pstart-data;pstart = p

33、start-next ;resulttip = 0;/存貯結果pstart =head; 釋放空間while(pstart-next != 0)(pnew = pstart-next ;delete pstart;pstart =pnew;return ;2.5冪運算的實現(xiàn)冪的實現(xiàn)是最為簡單的了，國為有了前面的算法做鋪墊，就是調(diào)用乘法函數(shù)，來循環(huán)去自乘， 冪指數(shù)相應減1，直到冪指數(shù)變?yōu)?時結束。其詳細代碼如下：/*函數(shù)名稱：大數(shù)冪*函數(shù)想法：1 B自減1直到，作為循環(huán)控制變量.保存結果；2結果初值1每次乘以A3重復1、2步驟到結束.*入口參數(shù)：numa，numb，result 字符串*出口參數(shù)：無*/void power (char *numa, char *numb,char *result) /計算冪( char one=1; /臨時字符串.char one2=1;char zero=0;char numb26048;char remainder6048;strcpy(result,one); /給結果初值為 1strcpy(numb2,numb);subtract(numb,one ,rema