高精度運算，是指參與運算的數(加數，減數，因子……）范圍大大超出了標準數據類型（整型，實型）能表示的范圍的運算。例如，求兩個20000位的數的和。這時，就要用到高精度算法了。
定義
高精度加法
高精度運算主要解決以下三個問題：
一、加數、減數、運算結果的輸入和存儲
運算因子超出了整型、實型能表示的范圍，肯定不能直接用一個數的形式來表示。在Pascal中，能表示多個數的數據類型有兩種：數組和字符串。
數組：每個數組元素存儲1位（在優化時，這里是一個重點！），有多少位就需要多少個數組元素；用數組表示數的優點：每一位都是數的形式，可以直接加減；運算時非常方便。用數組表示數的缺點：數組不能直接輸入；輸入時每兩位數之間必須有分隔符，不符合數值的輸入習慣；
字符串：String型字符串的最大長度是255，可以表示255位。Ansistring型字符串長度不受限制。用字符串表示數的優點：能直接輸入輸出，輸入時，每兩位數之間不必分隔符，符合數值的輸入習慣；用字符串表示數的缺點：字符串中的每一位是一個字符，不能直接進行運算，必須先將它轉化為數值再進行運算；運算時非常不方便；
綜合以上所述，對上面兩種數據結構取長補短：用字符串讀入數據，用數組存儲數據：
var st:string;
x,y:array[0..255]of integer;{定義兩個數組,X和Y,用來儲存數}
i,j,l1,l2:integer;
begin
readln(st);
l1:=length(st);{------length(x),該函數是獲取字符串X的長度，返回為整型}
for i:=0 to 255 do x[i]:=0;{數組初始化，該句等價于‘fillchar（x,sizeof(x),o）；’，即給一數組整體賦值，但運行速度快于用‘for’語句對數組中的每一個數賦值}
for i:=l1 downto 1 do
x[l1-i+1]:=ord(st[i])-ord('0');{------這里是重點，把字符串轉換為數值，儲存在數組中}
readln(st);
l2:=length(st);{------length(x),該函數是獲取字符串X的長度，返回為整型}
for i:=0 to 255 do y[i]:=0;{數組初始化，該句等價于‘fillchar（y,sizeof(y),o）；’}
for i:=l2 downto 1 do
y[l2-i+1]:=ord(st[i])-ord('0');{------這里是重點，把字符串轉換為數值，儲存在數組中}
對字符串轉為數值原理補充:ord(x)-48,如果X='1',因為'1'的ASCLL碼是49,所以減去48就等于1,間接地把字符轉換為數值了，各位初手要好好體會.
二、運算過程
在往下看之前，大家先列豎式計算35+86。
注意的問題：
（1）運算順序：兩個數靠右對齊；從低位向高位運算；先計算低位再計算高位；
（2）運算規則：同一位的兩個數相加再加上從低位來的進位，成為該位的和；這個和去掉向高位的進位就成為該位的值；如上例：3+8+1=12，向前一位進1，本位的值是2；可借助MOD、DIV運算完成這一步；
（3）最后一位的進位：如果完成兩個數的相加后，進位位值不為0，則應添加一位；
（4）如果兩個加數位數不一樣多，則按位數多的一個進行計算；
if l1 for i:=1 to l1 do begin x[i]:=x[i]+y[i]; x[i+1]:=x[i+1]+x[i] div 10; x[i]:=x[i] mod 10; end; 三、結果的輸出（這也是優化的一個重點） 按運算結果的實際位數輸出 var st:string; x,y:array[0..255]of integer; i,j,l1,l2:integer; begin readln(st); l1:=length(st); for i:=0 to 255 do x[i]:=0; for i:=l1 downto 1 do x[l1-i+1]:=ord(st[i])-ord('0'); readln(st); l2:=length(st); for i:=0 to 255 do y[i]:=0; for i:=l2 downto 1 do y[l2-i+1]:=ord(st[i])-ord('0'); if l1 for i:=1 to l1 do begin x[i]:=x[i]+y[i]; x[i+1]:=x[i+1]+x[i] div 10; x[i]:=x[i] mod 10; end; write('x+y='); j:=255; while x[j]=0 do j:=j-1; for i:=j downto 1 do write(x[i]); readln; end. 四、優化： 以上的方法的有明顯的缺點： （1）浪費空間：一個整型變量（-32768~32767）只存放一位（0~9）； （2）浪費時間：一次加減只處理一位； 針對以上問題，我們做如下優化：一個數組元素存放四位數；（integer的最大范圍是32767，5位的話可能導致出界）將標準數組改為緊縮數組。第一步的具體方法： l:=length(s1); k1:=260; repeat {————有關字符串的知識} s:=copy(s1,l-3,4); VAL(s,a[k1],code); k1:=k1-1; s1:=copy(s1,1,l-4); l:=l-4; until l<=0; k1:=k1+1; 而因為這個改進，算法要相應改變： （1）運算時：不再逢十進位，而是逢萬進位（mod 10000; div 10000); （2）輸出時：最高位直接輸出，其余各位，要判斷是否足夠4位，不足部分要補0；例如：1，23，2345這樣三段的數，輸出時，應該是100232345而不是1232345。 改進后的算法： var a,b:string; k,i,c,d:longint; e,z,y:array[0..255]of integer; begin readln(a); readln(b); if length(b)>length(a) then for i:=1 to length(b)-length(a) do a:='0'+a else for i:=1 to length(a)-length(b) do b:='0'+b; for i:=length(a) downto 1 do begin c:=ord(a[i])-48; d:=ord(b[i])-48; if c+d<10 then e[i]:=e[i]+c+d else begin e[i]:=e[i]+c+d-10;e[i-1]:=1; end; end; if e=1 then k:=0 else k:=1; for i:=k to length(a) do write(e[i]); end. C++參考程序： #include #include #include using namespace std; int main() { char a1,b1; int a,b,c,lena,lenb,lenc,i,x; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); gets(a1); gets(b1); //輸入加數與被加數 lena=strlen(a1); lenb=strlen(b1); for (i=0;i<=lena-1;i++) a[len阿倫·艾弗森]=a1[i]-48; //加數放入a數組 for (i=0;i<=lenb-1;i++) b[lenB.I]=b1[i]-48; //加數放入b數組 lenc =1; x=0; while (lenc <=lena||lenc <=lenb) { c[lenc]=a[lenc]+b[lenc]+x; //兩數相加 x=c[lenc]/10; c[lenc]%=10; lenc++; } c[lenc]=x; if (c[lenc]==0) lenc--; //處理最高進位 for (i=lenc;i>=1;i--) cout< return 0; } 和高精度加法相比，減法在差為負數時處理的細節更多一點：當被減數小于減數時，差為負數，差的絕對值是減數減去被減數；在程序實現上用一個變量來存儲符號位，用另一個數組存差的絕對值。 算法流程:(1).讀入被減數S1，S2（字符串）； (2).置符號位：判斷被減數是否大于減數：大則將符號位置為空；小則將符號位置為“- ”，交換減數與被減數； (3).被減數與減數處理成數值，放在數組中； (4).運算：A、取數； B、判斷是否需要借位； C、減，將運算結果放到差數組相應位中； D、判斷是否運算完成：是，轉5；不是，轉A； (5).打印結果：符號位，第1位，循環處理第2到最后一位； 細節：▲如何判斷被減數與減數的大小？ 如果位數一樣，直接比較字符串大小；否則，位數多的大。 k1:=length(s1); k2:=length(s2); if k1=k2 then if s1 else if k1 ▲將字符串處理成數值： l:=length(s1);{求出s1的長度，也即s1的位數；有關字符串的知識。} k1:=260; for i:=l downto 1 do begin a[k1]:=ord(s1[i])-48;{將字符轉成數值} k1:=k1-1; end; k1:=k1+1; ▲運算（減法跟加法比較，減法退位處理跟加法進位處理不一樣）： 處理退位：跟加法一樣，在for語句外面先將退位清零，用被減數再減去退位，{注意：由于每一個數位不一定都得向前一位借位，所以這里退位得清零。例如，234-25，個位需借位，而十位不用} 接著，再判斷，當被減數某一位不夠減時，則需加上前一位退位過來的數。注意：由于這里采用優化方法，所以退一位，就等于后一位加上10000。）最后，再拿一個數組來存儲兩個減數的差。 jw:=0; for i:=260 downto k1 do begin a[i]:=a[i]-jw;{此處jw為從剛處理的那一位上從本一位上的借位} jw:=0; {此處jw為I 位準備向高一位的借位} if a[i] begin jw:=1; a[i]:=a[i]+10000; end; c[i]:=a[i]-b[i] end; ▲打印結果：先找到差的第一個非零數，如果差的所有位數都為零，就直接輸出零；如果不是，就輸出符號位和差的第一位。剩下部分，打印補足零；因為優化后的高精度減法,是把每四個數位分成一段，而每一段則必須有四個數，當有一段不足四個數時，就得用"0"補足.(如：第一位是'1',第二位是'34',第三位是'345',第四位是'8', 則應寫為'').注意：第一位不用補零,(如：第一位為'3',則寫成'3'). while (c[k]=0) and (k<=260) do k:=k+1; if k>260 then write('0') else Begin write(fh,c[k]);{k是差的第1位；} for i:=k+1 to 260 do begin if c[i]<100 then write('0'); if c[i]<10 then write('0'); write(c[i]); end; end; 參考程序： program ZDloveQC; var s1,s2,s3,s4,s:string; a,b,c:array[1..260]of integer; i,k1,k2,l,code,jw:longint; fh:string; begin readln(s1); readln(s2); k1:=length(s1); k2:=length(s2); fh:=''; if k1=k2 then if s1 if k1 k1:=260; l:=length(s1); repeat s3:=copy(s1,l-3,4); VAL(s3,a[k1],code); dec(k1); s1:=copy(s1,1,l-4); l:=l-4; until l<=0; inc(k1); l:=length(s2); k2:=260; repeat s4:=copy(s2,l-3,4); val(s4,b[k2],code); 迪吉多(k2); s2:=copy(s2,1,l-4); l:=l-4; until l<=0; inc(k2); jw:=0; for i:=260 downto k1 do begin a[i]:=a[i]-jw; jw:=0; if a[i] begin jw:=1; a[i]:=a[i]+10000; end; c[i]:=a[i]-b[i]; end; while (c[k1]=0)and(k1<260) do inc(k1); if k1>260 then writeln('0') else Begin write(fh,c[k1]); for i:=k1+1 to 260 do begin if c[i]<1000 then write('0'); if c[i]<100 then write('0'); if c[i]<10 then write('0'); write(c[i]); end; end; end. C++參考程序： #include #include #include #include #include int const n=1000; typedef int arr[n]; int c[2*n+1]={}, i,j,k; arr a,b;void dushu(arr &s){int i=0,j,k,m; 單精度乘法是計算范圍次于高精度乘法的一種運算，只是運算效率比高精度計算略高。 單精度乘法過程樣例： const maxcount=進制位 maxlen=記錄高精度數組大小 procedure mulnum(a:bignum;x:longint;,var c:bignum); var i:longint; begin fillchar(c,sizeof(c),0);c:=a; for i:=1 to c do c[i]:=a[i]*x; for i:=1 to c do {進位} begin inc(c[i+1],c[i] div maxcount); c[i]:=c[i] MOD 10; end; while c[c+1]>0 do begin inc(c); inc(c[c+1],c[c] div maxcount); c[c]:=c[c] mod maxcount; end; end; 高精度乘法基本思想和加法一樣。其基本流程如下： ①讀入被乘數s1，乘數s2 ②把s1、s2分成4位一段，轉成數值存在數組a,b中；記下a,b的長度k1,k2； ③i賦為b中的最低位； ④從b中取出第i位與a相乘，累加到另一數組c中；（注意：累加時錯開的位數應是多少位？） ⑤i:=i-1；檢測i值：小于k2則轉⑥,否則轉④ ⑥打印結果 參考程序： program chengfa; const n=100; type ar=array [1..n] of integer; var a,b:ar; k1,k2,k:integer; c:array [1..200] of integer; s1,s2:string; procedure fenge(s:string;var d:ar; var kk:integer); {將s分割成四位一組存放在d中，返回的kk值指向d的最高位} var ss:string; i,code:integer; begin i:=length(s); kk:=n; repeat ss:=copy(s,i-3,4); VAL(ss,d[kk],code); kk:=kk-1; s:=copy(s,1,i-4); i:=i-4; until i<0; kk:=kk+1; end; procedure init; var i:integer; begin for i:=1 to n do begin a:=0; b:=0; end; for i:=1 to 2*n do c:=0; write('input 2 numbers:'); readln(s1); readln(s2); fenge(s1,a,k1); fenge(s2,b,k2); end; procedure jisuan; var i,j,m:integer; x,y,z,jw:longint; begin i:=n; k:=2*n; repeat x:=b; z:=0; m:=k; jw:=0; for j:=n downto k1 do begin y:=a[j]; z:=c[m]; x:=x*y+z+jw; jw:=x div 10000; c[m]:=x mod 10000; m:=m-1; x:=b; end; if jw<>0 then c[m]:=jw else m:=m+1; i:=i-1; k:=k-1; until i k:=m; end; procedure daying; var i:integer; begin write(c[k]); for i:=k+1 to 2*n do begin if c<1000 then write('0'); if c<100 then write('0'); if c<10 then write('0'); write(c); end; writeln; end; begin init; jisuan; daying; end. 教材“基礎編”P87高精乘法參考程序： program ex3_1; var a,b,c:array[0..1000] of word; procedure init; var s:string; ok,i,j:integer; begin readln(s); a:=length(s); for i:=1 to a do VAL(s[a-i+1],a,ok); readln(s); b:=length(s); b:=length(s); for i:=1 to b do val(s[b-i+1],b,ok); end; procedure highmul; var i,j,k:integer; begin c:=a+b; for i:=1 to b do for j:=1 to a+1 do begin inc(c[i+j-1],a[j]*b mod 10); c[i+j]:=c[i+j]+(a[j]*b div 10)+(c[i+j-1] div 10); c[i+j-1]:=c[i+j-1] mod 10; end; end; procedure print; var i:integer; begin while c[c]=0 do dec(c); for i:=c downto 1 do write(c); writeln; end; begin init; highmul; print; end. C++參考程序： #include 高精度除法： 1）.高精度除以整型數據(integer); 程序如下: program HighPrecision3_Multiply1; const fn_inp='hp5.inp'; fn_out='hp5.out'; maxlen=100; { max length of the number } type hp=record len:integer; { length of the number } s:array[1..maxlen] of integer { s is the lowest position s[len] is the highest position } end; var x,y:hp; z,w:integer; procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.s[i]); end; procedure init; var st:string; i:integer; begin assign(input,fn_inp); reset(input); readln(st); x.len:=length(st); for i:=1 to x.len do { change string to HP } XS:=ord(st[x.len+1-i])-ord('0'); readln(z); close(input); end; procedure Divide(a:hp;b:integer;var c:hp;var d:integer); { c:=a div b ; d:=a mod b } var i,len:integer; begin fillchar(c,sizeof(c),0); len:=a.len; d:=0; for i:=len downto 1 do { from high to low } begin d:=d*10+AS[i]; 計算機科學:=d div b; d:=d mod b; end; while(len>1) and (c.s[len]=0) do dec(len); c.len:=len; end; procedure main; begin Divide(x,z,y,w); end; procedure out_; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; writeln(w); close(output); end; begin init; main; out_; end. 2）.高精度除以高精度 程序如下: 版本一： 版本二： 作為一種高精度乘法的擴展算法，實質為高精度乘低精度，算法如下： var a:array[1..10000] of longint; i,j,k,l,p,o,q,x,y,w:integer; begin read(i); a:=1; w:=1; for j:=1 to i do begin y:=0; //到“For”前可省，但改為for k:=1 to 10000 do x:=j; while x>0 do begin y:=y+1; x:=x div 10; end; o:=0; for k:=w to l+y+1 do begin q:=a[k]*j+o; o:=q div 10; a[k]:=q mod 10; end; l:=10000; while (a[l]=0) and (l>1) do l:=l-1; w:=1; while (a[w]=0) and (w<9999) do w:=w+1; end; for p:=l downto 1 do write(a[p]); writeln; end. 我們知道，C++是一個面向對象的語言。上述所有代碼的實現都是面向過程的，都是以高精度運算為主體進行編程。然而，在實際應用中，高精度通常只作為程序的一部分而出現，在這樣的情況下，上述代碼難以直接移植、使用的特性暴露無遺。我們用C++的面向對象編程特性來做一次非常好用的高精度。 我們使用標準庫vector做基類，完美解決位數問題，同時更易于實現。 高精度類型Wint包含一個低精度轉高精度的初始化函數，可以自動被編譯器調用，因此無需單獨寫高精度數和低精度數的運算函數，十分方便；還包含了一個在各類運算中經常用到的進位小函數。 平淡無奇，有很多讀入的方法。這里偷個懶，直接讀入一個字符串再轉入Wint中。 比較，只需要寫兩個，其他的直接代入即可。值得注意的是，這里用常量引用當參數，避免拷貝更高效。 加法，先實現+=，這樣更簡潔高效。注意各個參數有別。 減法，返回差的絕對值，由于后面有交換，故參數不用引用。 乘法不能先實現*=，原因自己想。 除法和取模先實現一個帶余除法函數。當然，高精度除法也可以用二分中華人民共和國檔案法實現，不過效率過低且代碼冗長，這里使用常規豎式除法。 通過重載運算符，還可以實現++、--、^、!、邏輯運算符等很多運算，十分簡單，此處都不寫了。 此時你幾乎可以像int一般便捷地使用Wint，甚至可以把Wint和int混合使用。 順手實現一個快速冪，可以看到和普通快速冪幾乎無異。 上述高精度代碼已經能滿足正常使用需求了，不過仍然有優化和改進的空間： 一、萬進制優化 用int保存個位數顯然太過浪費，short型運算效率又沒有int型高（絕大部分機器對int有特別優化），在這樣的情況下，我們將改進后的Wint每位保存十進制下的四位（首位可能有前導0）即萬進制。在這樣的優化下，空間占用四分之一，加法快4倍，乘法16倍，而除法可達64倍之多。當然，這仍屬于常數級優化，不過底層運算十分頻繁的情況下還是值得考慮的。上述代碼無需作出太大調整，只需輸入輸出、進位、減法除法等函數略加改進即可，代碼略。 二、低精度優化 前面說過，目前高精度和低精度的運算會先將低精度提升到高精度再進行運算，這就有了優化空間。注意，這里的優化低精度是基于Wint是由int組成這一特點進行的，大于int型的別的類型（如long long）仍需提升到Wint再運算。考慮到低精度數位數在十位以內，優化后效率提升其實不到十倍。不過，在高精度和低精度混合運算十分頻繁的情況下，專門寫優化的高精度和低精度的運算也聊勝于無。這里先給出加法的優化示例。 三、初始化函數改進： 注意到初始化函數Wint(int n)會將大于int表示范圍的類型數如（unsigned long long）先轉為低精度再初始化，我們再增加（或者直接替換原先的）初始化函數，改為： 此外，在代碼中如果想定義到一個高精度常量（20位向上），就必須增加一個字符串初始化函數而不能直接賦一個整型常數（想想為什么？）。但是，這個字符串初始化函數我們希望它不會像int型一樣在運算中自動提升至Wint。否則，像s+7這樣的表達式就會有意義（先將s隱形轉換至Wint再進行加法運算，返回一個Wint型結果），但通常不符合我們的預期而僅僅只是代碼錯誤，而編譯時無法找出，會給我們調試代碼帶來很大麻煩。所以，這個字符串初始化函數前需加關鍵字explicit，來指出我們不希望隱式轉換的發生。 參考資料 >高精度減法
char b,ch;
scanf("%c",&ch);
while ((ch>=48)&& (ch <=57) )
{ i=i+1;
b[i]=ch;
scanf("%c",&ch);
} k=0; for(j=i; j>=1; j=j-1) { k=k+1; s[k]=b[j]-48; } }void shuchu(int c[n]) { int i=n; j=0; while ((c[i]==0) && (i>1)) i--; for (j=i; j>0; j--) printf("%d",c[j]); printf("\n"); } bool compare(arr &a,arr &b){ int i,j,k; for (i=n; i>0; i--) { if (a[i]>b[i]) {return true;} else if (a[i]
{
s=a[i]+b[i]+t;
c[i]=s % 10;
t=s / 10;
} shuchu(c); } void jianfa(arr &a, arr &b) { int i,j,k,s; memset(c,0,2*n+1); for (i=1; i<=n; i++) { if (a[i]>=b[i]) c[i]=a[i]-b[i]; else { c[i]=a[i]-b[i]+10; a[i+1]--; } } shuchu(c); }void chengfa(arr a, arr b) { int i,j,k,m; memset(c,0,2*n+1); for (i=1; i<=n; i++) for (j=1; j<=n; j++) { m=i+j-1; c[m]=a[j]*b[i]+c[m]; c[m+1]=c[m] / 10; c[m]=c[m]% 10; } shuchu(c); } main(){ dushu(a); dushu(b); jiafa(a,b); if (!compare(a,b)) { printf("%c",'-'); change(a,b); } jianfa(a,b); chengfa(a,b); system("pause"); return 0;}單精度乘法
高精度乘法
高精度除法
高精度階乘
C++的優雅實現
實現
輸入輸出
大小比較
加法
減法
乘法
除法和取模
使用
優化與改進