高精度運(yùn)算c語言

1、高精度運(yùn)算內(nèi)蒙古師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院孟繁軍運(yùn)算的前提條件：類型范圍 確定各類型的取值范圍 int: -2,147,483,6482,147,483,647 unsigned int: 0 to 4,294,967,295 long int:-2,147,483,648 to 2,147,483,647 long long: -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 float:3.4E +/- 38 (7 digits) double:1.7E +/- 308 (15 digits) long double:1.2E

2、 +/- 4932 (19 digits)高精度運(yùn)算的基本方法1、加數(shù)、減數(shù)、運(yùn)算結(jié)果的輸入和存儲(chǔ)運(yùn)算因子超出了整型、實(shí)型能表示的范圍，肯定不能直接用一個(gè)數(shù)的形式來表示。在運(yùn)算過程中，能表示多個(gè)數(shù)的數(shù)據(jù)類型有兩種：數(shù)組和字符串。（1）數(shù)組：每個(gè)數(shù)組元素存儲(chǔ)1位（在優(yōu)化時(shí)，這里是一個(gè)重點(diǎn)！），有多少位就需要多少個(gè)數(shù)組元素；用數(shù)組表示數(shù)的優(yōu)點(diǎn)：每一位都是數(shù)的形式，可以直接加減；運(yùn)算時(shí)非常方便用數(shù)組表示數(shù)的缺點(diǎn)：數(shù)組不能直接輸入；輸入時(shí)每兩位數(shù)之間必須有分隔符，不符合數(shù)值的輸入習(xí)慣；（2）字符串：字符串的最大長度是多少，可以表示多少位數(shù)字？用字符串表示數(shù)的優(yōu)點(diǎn)：能直接輸入輸出，輸入時(shí)，每兩位數(shù)之間不

3、必分隔符，符合數(shù)值的輸入習(xí)慣；用字符串表示數(shù)的缺點(diǎn)：字符串中的每一位是一個(gè)字符，不能直接進(jìn)行運(yùn)算，必須先將它轉(zhuǎn)化為數(shù)值再進(jìn)行運(yùn)算；運(yùn)算時(shí)非常不方便；（3）因此，綜合以上所述，對(duì)上面兩種數(shù)據(jù)結(jié)構(gòu)取長補(bǔ)短：用字符串讀入數(shù)據(jù)，用數(shù)組存儲(chǔ)數(shù)據(jù)：高精度運(yùn)算的運(yùn)算過程 在往下看之前，大家先列豎式計(jì)算35+86。注意的問題：（1）運(yùn)算順序：兩個(gè)數(shù)靠右對(duì)齊；從低位向高位運(yùn)算；先計(jì)算低位再計(jì)算高位；（2）運(yùn)算規(guī)則：同一位的兩個(gè)數(shù)相加再加上從低位來的進(jìn)位，成為該位的和；這個(gè)和去掉向高位的進(jìn)位就成為該位的值；如上例：3+8+1=12，向前一位進(jìn)1，本位的值是2；可借助取余、整除運(yùn)算完成這一步；（3）最后一位的進(jìn)位：

4、如果完成兩個(gè)數(shù)的相加后，進(jìn)位位值不為0，則應(yīng)添加一位；（4）如果兩個(gè)加數(shù)位數(shù)不一樣多，則按位數(shù)多的一個(gè)進(jìn)行計(jì)算；高精度的十進(jìn)制算 一般形式： 輸入時(shí)為數(shù)串 轉(zhuǎn)化為整數(shù)數(shù)組（該數(shù)組的每一個(gè)元素對(duì)應(yīng)一位十進(jìn)制數(shù)，并使用一變量記錄數(shù)組的實(shí)際長度，即數(shù)組元素有效個(gè)數(shù)） 轉(zhuǎn)化方法： memset(a,0,number*sizeof(int); k=length(s); for(i=1;i=k;i+) ak-i+1=si-0;加法運(yùn)算 確定a和b中的最大位數(shù)x(x=maxla,lb) 依照由低位至高位（第1位至第x位）的順序進(jìn)行加法運(yùn)算。 在每一次的運(yùn)算中，a當(dāng)前位加b當(dāng)前位的和除以10，其商即為進(jìn)位，其

5、余數(shù)即為和的當(dāng)前進(jìn)位。 在進(jìn)行了x位的加法后，若最高位有進(jìn)位（ax+10），則a的長度為x+1。加法運(yùn)算算法/*實(shí)現(xiàn)a=a+b*/void add(int a,int b) int i,x; if (la=lb) x=la; else x=lb;for(i=1;i=x ;i+) ai=ai+bi; ai+1=ai+1+ai/10; ai=ai%10;while(ax+10) x=x+1;la=x-1;減法運(yùn)算 依照由低位至高位（第1位至第la位）的順序進(jìn)行減法運(yùn)算。 在每一次的減法運(yùn)算中，若出現(xiàn)不夠減的情況(aibi)，則向高位借位(ai+1=ai+1-1, ai=ai+10)。 在進(jìn)行了la

6、位的減法后，若最高位為零(ala=0),則a的長度減1。減法運(yùn)算算法/*a=a-b*/void sub(int a,int b) int i; for(i=1;i=la;i+) if(aibi) ai+1=ai+1-1; ai=ai+10; ai=ai-bi; while (ala=0) la- -;乘法運(yùn)算 按照乘法規(guī)則，從a的第1位開始逐位與C相乘。 在第i位乘法運(yùn)算中（1ila）,a的i位與C的乘積必加上i-1位的進(jìn)位（i-1位的乘積除以10的整商），然后規(guī)整積的i-1位（取i-1位的乘積對(duì)10的余數(shù)）。乘法運(yùn)算算法void multiply(int a,int c) int i; a1

7、=a1*c; for(i=2;i=10) la=la+1; ala=ala-1 /10; ala-1=ala-1%10; 改善的高精度運(yùn)算的效率 以上的方法的有明顯的缺點(diǎn)：（1）浪費(fèi)空間：一個(gè)整型變量只存放一位（0-9）；（2）浪費(fèi)時(shí)間：一次加減只處理一位； 改進(jìn)辦法： (1)擴(kuò)大進(jìn)制數(shù)：考慮用一個(gè)數(shù)組元素記錄2位數(shù)字、3位數(shù)字或更多位的數(shù)字。（但是要考慮到計(jì)算機(jī)中的一個(gè)數(shù)的取值范圍，必須保證在運(yùn)算過程中不會(huì)越界）如，一個(gè)數(shù)組元素存放四位數(shù)；這樣數(shù)組就相當(dāng)于10000進(jìn)制的數(shù)。 (2)建立因子表：擴(kuò)大進(jìn)制數(shù)1 數(shù)據(jù)類型 int a10000; string st; int la,ln;2 整數(shù)

8、數(shù)組的建立和輸出 當(dāng)輸入數(shù)串st后，我們從左而右掃描數(shù)串st,以四個(gè)數(shù)碼為一組，將之對(duì)應(yīng)的10000進(jìn)制數(shù)據(jù)存入數(shù)組n中。具體方法如下：擴(kuò)大進(jìn)制數(shù)（cont.） 建立： scanf(“%s”,st); K=len(st); For(i=0;ik;i+) j=(k-i+3)/4 -1; nj=nj*10+sti+1-48; ln=(k+3)/4;擴(kuò)大進(jìn)制數(shù)（cont.） 輸出： printf(nln-1); for(i=ln-2;i=0;i-) printf(“%d%d%d%d”,ni/1000,(ni/100)%10,(ni/10)%10,ni%10);基本運(yùn)算 （1）整數(shù)數(shù)組減1（n=n-1

9、,n為整數(shù)數(shù)組） 從n0出發(fā)往左掃描，尋找第一個(gè)非零的元素（nj0, nj-1=nj-2=nj-3=n0=0）。由于該位接受了低位的借位，因此減1，其后綴全為9999。如果最高位為0，則n的長度減1 j=0; While(nj=0) j+; nj=nj-1; for(k=0;k=0lj-) aj=aj+l*1000; l=aj%i; aj=ai/i; While (ala-1=0) la=la-1;基本算法（兩個(gè)整數(shù)數(shù)組相乘） a=a*n; 按照由高位到低位的順序，將a數(shù)組的每一個(gè)元素與n相乘。當(dāng)計(jì)算到aj*n時(shí)，根據(jù)乘法規(guī)則，aj-1,a0不變，aj為原aj與n0的乘積，aj+k加上aj*nk的乘積(k=ln-1,ln-2,1),然后按照由低位到高位的順序處理進(jìn)位。最后，如果ala-1*n有進(jìn)位，則乘積a的有效位數(shù)為la+ln;否則a的有效位數(shù)為la+ln-1.兩個(gè)整數(shù)數(shù)組相乘(cont.)For(j=la-1;j=0