高精度運算c語言

1、高精度運算內(nèi)蒙古師范大學計算機與信息工程學院孟繁軍運算的前提條件：類型范圍 確定各類型的取值范圍 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)高精度運算的基本方法1、加數(shù)、減數(shù)、運算結(jié)果的輸入和存儲運算因子超出了整型、實型能表示的范圍，肯定不能直接用一個數(shù)的形式來表示。在運算過程中，能表示多個數(shù)的數(shù)據(jù)類型有兩種：數(shù)組和字符串。（1）數(shù)組：每個數(shù)組元素存儲1位（在優(yōu)化時，這里是一個重點?。卸嗌傥痪托枰嗌賯€數(shù)組元素；用數(shù)組表示數(shù)的優(yōu)點：每一位都是數(shù)的形式，可以直接加減；運算時非常方便用數(shù)組表示數(shù)的缺點：數(shù)組不能直接輸入；輸入時每兩位數(shù)之間必須有分隔符，不符合數(shù)值的輸入習慣；（2）字符串：字符串的最大長度是多少，可以表示多少位數(shù)字？用字符串表示數(shù)的優(yōu)點：能直接輸入輸出，輸入時，每兩位數(shù)之間不

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

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

5、余數(shù)即為和的當前進位。 在進行了x位的加法后，若最高位有進位（ax+10），則a的長度為x+1。加法運算算法/*實現(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;減法運算 依照由低位至高位（第1位至第la位）的順序進行減法運算。 在每一次的減法運算中，若出現(xiàn)不夠減的情況(aibi)，則向高位借位(ai+1=ai+1-1, ai=ai+10)。 在進行了la

6、位的減法后，若最高位為零(ala=0),則a的長度減1。減法運算算法/*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- -;乘法運算 按照乘法規(guī)則，從a的第1位開始逐位與C相乘。 在第i位乘法運算中（1ila）,a的i位與C的乘積必加上i-1位的進位（i-1位的乘積除以10的整商），然后規(guī)整積的i-1位（取i-1位的乘積對10的余數(shù)）。乘法運算算法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; 改善的高精度運算的效率 以上的方法的有明顯的缺點：（1）浪費空間：一個整型變量只存放一位（0-9）；（2）浪費時間：一次加減只處理一位； 改進辦法： (1)擴大進制數(shù)：考慮用一個數(shù)組元素記錄2位數(shù)字、3位數(shù)字或更多位的數(shù)字。（但是要考慮到計算機中的一個數(shù)的取值范圍，必須保證在運算過程中不會越界）如，一個數(shù)組元素存放四位數(shù)；這樣數(shù)組就相當于10000進制的數(shù)。 (2)建立因子表：擴大進制數(shù)1 數(shù)據(jù)類型 int a10000; string st; int la,ln;2 整數(shù)

8、數(shù)組的建立和輸出 當輸入數(shù)串st后，我們從左而右掃描數(shù)串st,以四個數(shù)碼為一組，將之對應的10000進制數(shù)據(jù)存入數(shù)組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;擴大進制數(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);基本運算 （1）整數(shù)數(shù)組減1（n=n-1

9、,n為整數(shù)數(shù)組） 從n0出發(fā)往左掃描，尋找第一個非零的元素（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;基本算法（兩個整數(shù)數(shù)組相乘） a=a*n; 按照由高位到低位的順序，將a數(shù)組的每一個元素與n相乘。當計算到aj*n時，根據(jù)乘法規(guī)則，aj-1,a0不變，aj為原aj與n0的乘積，aj+k加上aj*nk的乘積(k=ln-1,ln-2,1),然后按照由低位到高位的順序處理進位。最后，如果ala-1*n有進位，則乘積a的有效位數(shù)為la+ln;否則a的有效位數(shù)為la+ln-1.兩個整數(shù)數(shù)組相乘(cont.)For(j=la-1;j=0