C語(yǔ)言中超大整數(shù)乘法運(yùn)算

1、C 語(yǔ)言中超大整數(shù)乘法運(yùn)算在計(jì)算機(jī)中，長(zhǎng)整型 (long int) 變量的范圍是 -2147483648 至 2147483647 ，因此若用長(zhǎng)整型 變量做乘法運(yùn)算，乘積最多不能超過(guò) 10 位數(shù)。即便用雙精度型 (double) 變量，也僅能保證 16 位有效數(shù)字的精度。在某些需要更高精度的乘法運(yùn)算的場(chǎng)合，需要用別的辦法來(lái)實(shí)現(xiàn)乘法運(yùn)算。 比較容易想到的是做多位數(shù)乘法時(shí)列豎式進(jìn)行計(jì)算的方法，只要寫出模擬這一過(guò)程的程序，就能 實(shí)現(xiàn)任意大整數(shù)的乘法運(yùn)算。經(jīng)過(guò)查閱資料，找到一種更易于編程的方法，即“列表法”。下面先介紹“列表法”：例如當(dāng)計(jì)算 8765 x 234 時(shí)，把乘數(shù)與被乘數(shù)照如下列出，見(jiàn)表 1

2、 ：把表 1 中的數(shù)按圖示斜線分組(橫縱坐標(biāo)和相等的數(shù)分為一組)，把每組數(shù)的累加起來(lái)所得的 和記在表格下方，見(jiàn)表 2 ：從最低位的 20 開始，保留個(gè)位數(shù)字“ 0 ”，把個(gè)位以外的數(shù)“2 ”進(jìn)到前一位； 把39次 低位的加上低位進(jìn)上來(lái)的 2 得 41 ，保留個(gè)位數(shù)字“1”，把“ 4”進(jìn)到前一位；以此類推，直至最高位的 16，16 加上低位進(jìn)上來(lái)的 4 得 20 ，保留“ 0”，把2 進(jìn)到最高位，得乘積答數(shù) 2051010 。根據(jù)以上思路就可以編寫 C 程序了，再經(jīng)分析可得：1、一個(gè) m 位的整數(shù)與一個(gè) n 位的整數(shù)相乘，乘積為 m+n-1 位或 m+n 位。2、程序中，用三個(gè)字符數(shù)組分別存儲(chǔ)乘

3、數(shù)、被乘數(shù)與乘積。由第1 點(diǎn)分析知，存放乘積的字符數(shù)組的長(zhǎng)度應(yīng)不小于存放乘數(shù)與被乘數(shù)的兩個(gè)數(shù)組的長(zhǎng)度之和。3、可以把第二步“計(jì)算填表”與第三四步“累加進(jìn)位”放在一起完成，可以節(jié)省存儲(chǔ)表格2 所需的空間。4、程序關(guān)鍵部分是兩層循環(huán)，內(nèi)層循環(huán)累計(jì)一組數(shù)的和，外層循環(huán)處理保留的數(shù)字與進(jìn)位。編寫的程序如下：#define MAXLENGTH 1000#include #include void compute(char *a, char *b, char *c);void main(void)char aMAXLENGTH, bMAXLENGTH, cMAXLENGTH * 2;puts(Input

4、multiplier :);gets(a);puts(Input multiplicand :);gets(b);compute(a, b, c);puts(Answer :);puts(c);getchar();void compute(char *a, char *b, char *c) int i, j, m, n;long sum, carry;m = strlen(a) - 1;n = strlen(b) - 1;for (i =m; i = 0; i-)ai -= 0;for (i =n; i = 0; i-)bi -= 0;cm +n + 2 = 0;carry =0;for (

5、i =m + n; i = 0; i-) /* i為坐標(biāo)和 */sum =carry;if (j = i- m) 0)j = 0;for ( ; j=i & j=n; j+) /* j為縱坐標(biāo) */sum += ai-j * bj; /*累計(jì)一組數(shù)的和 */ci + 1= sum % 10 + 0; /*算出保留的數(shù)字 */carry =sum / 10; /* 算出進(jìn)位 */if (c0 = carry+0) = 0) /* if no carry, */ c0 = 040; /* c0 equals to space */ 效率分析：用以上算法計(jì)算 m 位整數(shù)乘以 n 位整數(shù)，需要先進(jìn)行

6、m x n 次乘法運(yùn)算，再進(jìn)行約 m + n 次加法運(yùn)算和 m + n 次取模運(yùn)算 ( 實(shí)為整數(shù)除法 )。把這個(gè)程序稍加修改，讓它自己產(chǎn)生 乘數(shù)與被乘數(shù)，然后計(jì)算隨機(jī)的 7200 位整數(shù)互乘，在 Cyrix 6x86 pr166 機(jī)器的純 DOS 方式 下耗時(shí) 7 秒(用 Borland C3.1 編譯 )。經(jīng)過(guò)改進(jìn)，此算法效率可以提高約 9 倍。注意到以下事實(shí)： 8216547 x 96785 將兩數(shù)從個(gè)位起，每 3 位分為節(jié)，列出乘法表，將斜線間 的數(shù)字相加；8 216 54796 785將表中最后一行進(jìn)行如下處理：從個(gè)位數(shù)開始，每一個(gè)方格里只保留三位數(shù)字，超出 1000 的部 分進(jìn)位到前

7、一個(gè)方格里；所以 8216547 x 96785 = 795238501395也就是說(shuō)我們?cè)谟?jì)算生成這個(gè)二維表時(shí)，不必一位一位地乘，而可以三位三位地乘；在累加時(shí)也 是滿 1000 進(jìn)位。這樣，我們?cè)谟?jì)算 m 位整數(shù)乘以 n 位整數(shù)，只需要進(jìn)行 m x n / 9 次乘法運(yùn) 算，再進(jìn)行約 (m + n) / 3 次加法運(yùn)算和 (m + n) /3 次取模運(yùn)算。總體看來(lái)，效率約是前一種算 法的 9 倍。有人可能會(huì)想：既然能夠三位三位地乘，為什么不 4 位 4 位甚至 5 位 5 位地乘呢？那不是可以 提高 16 乃至 25 倍效率嗎？聽(tīng)我解來(lái)：本算法在累加表中斜線間的數(shù)字時(shí)，如果用無(wú)符號(hào)長(zhǎng)整 數(shù)(

8、范圍 0 至4294967295) 作為累加變量，在最不利的情況下 (兩個(gè)乘數(shù)的所有數(shù)字均是 9) ，能 夠累加約 4294967295/(999*999)=4300 次，也就是能夠準(zhǔn)確計(jì)算任意兩個(gè)均不超過(guò) 12900( 每次累加的結(jié)果 值 三位，故 4300*3=12900) 位的整數(shù)相乘。如果 4 位 4 位地乘，在 最不利的情況下，能夠累加約 4294967295/(9999*9999)=43 次，僅能夠確保任意兩個(gè)不超過(guò) 172 位的整數(shù)相乘，沒(méi)有什么實(shí)用價(jià)值，更不要說(shuō) 5 位了。請(qǐng)看改進(jìn)后的算法的實(shí)例程序：該程序隨機(jī)產(chǎn)生兩個(gè) 72xx 位的整數(shù)，把乘數(shù)與積保存在 result.txt

9、 中。在 Borland C+ 3.1 中 用BCC -3 -O2 -G -mh -Z -f287 -pr -T- dashu.cpp編譯生成的 exe 文件在 Cyrix 6x86 pr166 的機(jī)器上運(yùn)行耗時(shí) 0.82 秒。程序 2 清單：#include#include#include #include #include #define N 7200 / 作 72xx 位的整數(shù)乘法 int max(int,int,int);int initarray(int a);void write(int a,int l);FILE *fp;void main()int a5000=0,b5000=

10、0,k10001=0; / 聲明存放乘數(shù)、被乘數(shù)與積的數(shù)組clock_t start, end; / 聲明用于計(jì)時(shí)的變量unsigned long c,d,e; / 聲明作累加用的無(wú)符號(hào)長(zhǎng)整數(shù)變量int i,j,la,lb,ma,mi,p,q,t; / 聲明其它變量randomize(); / 初始化隨機(jī)數(shù)la=initarray(a); / 產(chǎn)生被乘數(shù)，并返回其長(zhǎng)度lb=initarray(b); / 產(chǎn)生乘數(shù)，并返回其長(zhǎng)度if(lala)?lb:la;for (q=0;q=0;i-) /累加斜線間的數(shù)， i 為橫縱坐標(biāo)之和c=d; / 將前一位的進(jìn)位標(biāo)志存入累加變量 c ma=max(0,

11、i-la+1,i-lb+1); /求累加的下限mi=(ila-1)?(la-1):i; / 求累加的上限 for(j=ma;j999)c%=1000; / 取 c 的末三位ki=c; / 保存至表示乘積的數(shù)組 ke=k0+1000*d; / 求出乘積的最高位end = clock();/ 停止計(jì)時(shí)fp = fopen(result.txt, w+); /保存結(jié)果到 result.txtprintf(nThe elapsed time was: %3.4fn, (end - start) / CLK_TCK); / 打印消耗的時(shí)間fprintf(fp,%d,a0); / 打印被乘數(shù)最高位 wri

12、te(a,la); / 打印被乘數(shù)其他位 fprintf(fp,%d,b0); / 打印乘數(shù)最高位 write(b,lb); / 打印乘數(shù)其他位 fprintf(fp,%ld,e); / 打印乘積最高位 write(k,la+lb-1); / 打印乘積其他位 fclose(fp);max(int a,int b,int c)int d;d=(ab)?a:b;return (dc)?d:c;int initarray(int a)int q,p,i;q=N+random(100); if(q%3=0) p=q/3;elsep=q/3+1;for(i=0;ip;i+) ai=random(1000);if(q%3=0) a0=100+random(900);if(q%3=2)a0=10+random(90);if(q%3=1) a0=1+random(9);return p;void write(int a,int l)int i;char s