對於計算機無法用普通數據類型（如：longint）表示的大整數進行乘法運算，稱為高精度乘法。
基本介紹
- 中文名：高精度乘法
- 例題：對輸入的兩個大整數求乘積
- 代碼：C/c++/pascal語言
- 作用：求大整數乘積
問題提出,例題,代碼,
問題提出
例題
輸入
輸入一個整數n，下面的程式中，n不宜太大了。n<=1000。當然，也可以通過改變MAX來實現求更大數的階乘。
輸出
輸出 n! 。
代碼
Python(最短)
print(int(input())*int(input()))#真的是高精度乘法
C語言
複雜度分析：對於m * n， m 的長度為lm， n 長度為ln， 則樸素算法的複雜度為O(lm * ln)。
/*高精度乘法輸入：兩行，每行表示一個非負整數（不超過10000位）輸出：兩數的乘積。*/#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX 10001int bigchengfa(int *sum,int *a,int *b,int la,int lb){ int i,j,lsum = 0 ; memset(sum,0,sizeof(sum)); for(i=1 ; i<= la ; i++) /*用數組模擬運算*/ for(j=1,lsum=i-1; j<= lb ; j++) sum[++lsum] += b[j] * a[i] ; for(i=1 ; i<= lsum ; i++)/*進位處理*/ if (sum[i] >= 10) { if ( sum[lsum] >= 10) lsum ++ ; sum[i+1] += sum[i] / 10 ; sum[i] %= 10 ; } return lsum ;}int main(void){ int a[MAX]={0},b[MAX]={0},sum[MAX*2]={0} ; int la=0,lb=0,lsum=0; int i,j ; char sa[MAX],sb[MAX] ; scanf("%s %s",sa,sb); la = strlen(sa); lb = strlen(sb); for(i=1,j=la-1; i<= la ; i++,j--) a[i] = sa[j] - '0' ; for(i=1,j=lb-1; i<= lb ; i++,j--) b[i] = sb[j] - '0' ; lsum = bigchengfa(sum,a,b,la,lb) ; for(i=lsum ; i> 0 ; i--) printf("%d",sum[i]); printf("\n"); return 0 ;}另：
#include<stdio.h>int main(){ char n[255]={},m[255]={}; int n1[255]={},m1[255]={},s[510]={}; int i,j,k=0,t,x=0,dig; int lenn,lenm; scanf("%s%s",&n,&m); lenn = strlen(n); lenm = strlen(m); for(i=0; i<lenn; i++) n1[i] = n[i] - 48; for(j=0; j<lenm; j++) m1[j] = m[j] - 48; for(j=lenm-1; j>=0; j--){ t=k; for(i=lenn-1; i>=0; i--) { s[t] += n1[i]*m1[j]; t++; } ++k; dig = t; } for(i=0; i<dig; i++) while(s[i] >= 10){ s[i] -= 10; ++s[i+1]; } if(s[dig] != 0) for(i=dig; i>=0; i--) printf("%d", s[i]); else for(i=dig-1;i>=0;i--) printf("%d",s[i]); return 0;}Pascal
vari,j,la,lb,len:integer;s1,s2:string;m:longint;a,b,c:array[1..250] of integer;beginreadln(s1);la:=length(s1);readln(s2);lb:=length(s2);for i:=1 to la doa[i]:=ord(s1[la-i+1])-48;for i:=1 to lb dob[i]:=ord(s2[lb-i+1])-48;for i:=1 to la dofor j:=1 to lb doc[i+j-1]:=c[i+j-1]+a[i]*b[j];len:=la+lb;for i:=1 to len dobeginc[i+1]:=c[i+1]+c[i] div 10;c[i]:=c[i] mod 10;end;while c[len]=0 do dec(len);m:=c[len];while m>0 dobeginc[len]:=m mod 10;m:=m div 10;inc(len);end;for i:=len-1 downto 1 dowrite(c[i]);end .
C++
簡單的字元串模擬：
#include<bits/stdc++.h>//萬能頭檔案char x[205],y[205];int a[205],b[205],c[1000],lenc=0,t;int main(){ gets(x); gets(y); int lenx=strlen(x); int leny=strlen(y); for(int i=0;i<lenx;i++)//-48==-'0' a[lenx-i]=x[i]-48; for(int i=0;i<leny;i++) b[leny-i]=y[i]-48; for(int i=1;i<=lenx;i++) { t=0; for(int j=1;j<=leny;j++) { c[i+j-1]+=a[i]*b[j]+t; t=c[i+j-1]/10;c[i+j-1]%=10; } c[i+leny]=t; } lenc=lenx+leny; while(c[lenc]==0&&lenc>1) lenc--; for(int i=lenc;i>=1;i--) printf("%d",c[i]);}#include<bits/stdc++.h>using namespace std;string add(string x,string y){ string result=""; int a[1000],b[1000],c[1000],l,i,t,p; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for (i=x.size()-1;i>=0;i--) a[x.size()-i-1]=int(x[i])-48; for (i=y.size()-1;i>=0;i--) b[y.size()-i-1]=int(y[i])-48; if (x.size()>y.size()) l=x.size(); else l=y.size(); for (i=0;i<l;i++) { t=a[i]+b[i]+c[i]; p=0; if (t>=10) {p=1; t%=10;} c[i]+=t-c[i]; c[i+1]+=p; } if (p==1) l++; for (i=l-1;i>=0;i--) result+=char(c[i]+48); return result;}string mul(string x,char y){ string result=""; int a[1000],b,c[1000],l,i,t,p; memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); l=x.size(); for (i=l-1;i>=0;i--) a[l-i-1]=int(x[i])-48; b=int(y)-48; for (i=0;i<l;i++) { t=a[i]*b+c[i]; p=0; if (t>=10) {p=t/10; t%=10;} c[i]+=t-c[i]; c[i+1]+=p; } if (p) l++; for (i=l-1;i>=0;i--) result+=char(c[i]+48); return result;}int main(){ string a,b,c="",r; int i,j,l,t=0; cin>>a; cin>>b; l=b.size(); for (i=l-1;i>=0;i--) { c=mul(a,b[i]); for (j=1;j<=t;j++) c+="0"; if (!t) r=c; else r=add(r,c); t++; } cout<<r; return 0;}#include <iostream>using namespace std;int main(){ int a[100],b[100],c[100],len,la,lb,i,j; long long n,m; cin>>n>>m; la=0; while(n>0) { la++; a[la]=n%10; n=n/10; } lb=0; while(m>0) { lb++; b[lb]=m%10; m=m/10; } memset(c,0,sizeof(c)); for(i=1;i<=la;i++) for(j=1;j<=lb;j++) c[i+j-1]=c[i+j-1]+a[i]*b[j]; len=la+lb; for(i=1;i<=len;i++) { c[i+1]=c[i+1]+c[i]/10; c[i]=c[i]%10; } while(c[len]==0){len--;} m=c[len]; while(m>0) { c[len]=m%10; m=m/10; len++; } for(i=len-1;i>=1;i--) {cout<<c[i];} cout<<endl; return 0;}#include<cstdio>#include<cstdlib>#include<iostream>#include<cstring>using namespace std;struct node{int d[100000],l;};char s[1000000];node a,b,c;void read(node &x){ scanf("%s",s); x.l=strlen(s); memset(x.d,0,sizeof(x.d)); for (int i=0;i<x.l;i++) x.d[x.l-i-1]=s[i]-'0';}int main(){ read(a);read(b); // if (la>lb) lc=la;else lc=lb; memset(c.d,0,sizeof(c.d)); for (int i=0;i<a.l;i++) { for (int j=0;j<b.l;j++) c.d[i+j]+=a.d[i]*b.d[j]; } c.l=a.l+b.l-1; for (int i=0;i<c.l;i++) { c.d[i+1]+=c.d[i]/10; c.d[i]%=10; } while (c.d[c.l]>0) { c.d[c.l+1]=c.d[c.l]/10; c.d[c.l]%=10; c.l++; } while (c.l>1 && c.d[c.l-1]==0) c.l--; for (int i=c.l-1;i>=0;i--) printf("%d",c.d[i]); return 0;} 分治（僅函式） list<char> Mul(list<char> num1,list<char> num2) // 分治法求兩大數的積 { list<char> ans; int sign = 0; int len1,len2,len; list<char>::iterator iter1,iter2,iter; list<char> high,low; list<char> anshigh,anslow; int th,tl; int i,j,k; //print(num1);cout << endl; //print(num2);cout << endl; if(num1.size() == 1 && num2.size() == 1) //如果兩數都已是一位數，則進行運算 { th = *(num1.begin()) - '0'; tl = *(num2.begin()) - '0'; th *= tl; ans.push_front( th % 10 + '0'); ans.push_front( th / 10 + '0'); return ans; } else if(num1.size() == 1 && num2.size() > 1) //如果num1位數大於1，則對Num1分治求積 { if(*(num2.begin()) == '-') { sign = 1; num2.pop_front(); } len2 = num2.size(); if(len2 == 1) { ans = Mul(num1,num2); if(sign) ans.push_front('-'); } else { for(iter= num2.begin(),i = 0; i < len2 / 2; i++,iter++) { high.push_back(*iter); } for(;iter!=num2.end();iter++) { low.push_back(*iter); } len = low.size(); anshigh = Mul(num1,high); //num1分為兩部分，high,low anslow = Mul(num1,low); for(i = 0; i < len; i++) anshigh.push_back('0'); ans = Add(anshigh,anslow); //合併結果 if(sign) ans.push_front('-'); } return ans; } else if(num2.size() == 1 && num1.size() > 1) //如果num2位數大於1，則對Num2分治求積 { if(*(num1.begin()) == '-') { sign = 1; num1.pop_front(); } len1 = num1.size(); if(len2 == 1) { ans = Mul(num1,num2); if(sign) ans.push_front('-'); } else { for(iter= num1.begin(),i = 0; i < len1 / 2; i++,iter++) { high.push_back(*iter); } for(;iter!=num1.end();iter++) { low.push_back(*iter); } len = low.size(); anshigh = Mul(num2,high); //num2分為兩部分，high,low anslow = Mul(num2,low); for(i = 0; i < len; i++) anshigh.push_back('0'); ans = Add(anshigh,anslow); //合併結果 if(sign) ans.push_front('-'); } return ans; } //如果兩數位數都大於1，則都運用分治 else { list<char> num1high,num1low,num2high,num2low; int flag1 = 0,flag2 = 0; if(*(num1.begin()) == '-') { flag1 = 1; num1.pop_front(); } if(*(num2.begin()) == '-') { flag2 = 1; num2.pop_front(); } if((flag1 == 1 && flag2 == 0)||(flag1 == 0 && flag2 == 1)) //如果有一正一負，則標記結果為負 { sign = 1; } len1 = num1.size(); len2 = num2.size(); if(len1 == 1 || len2 == 1) //如果有一個數是一位數，則直接遞歸調用 { ans = Mul(num1,num2); if(sign) ans.push_front('-'); } else { //否則分治法求 for(iter = num1.begin(),i = 0; i < len1 / 2; iter++,i++) num1high.push_back(*iter); //被乘數高位部分 for( ; iter != num1.end(); iter++) num1low.push_back(*iter); //被乘數低位部分 for(iter = num2.begin(),i = 0; i < len2 / 2; iter++,i++) num2high.push_back(*iter); //乘數高位部分 for( ; iter != num2.end(); iter++) num2low.push_back(*iter); //乘數低位部分 int a = (len1 + 1) / 2; int b = (len2 + 1) / 2; list<char> AC,AD,BC,BD; //print(num2high);cout << endl; //print(num2low);cout << endl; AC = Mul(num1high,num2high); //運用X=A*10^a + B; Y= C*10^b + D; AD = Mul(num1high,num2low); // X*Y = AC * 10 ^(a+b) + AD *10^a + BC * 10 ^b + BD公式求 BC = Mul(num1low,num2high); BD = Mul(num1low,num2low); for(i = 0; i < a + b; i++) AC.push_back('0'); for(i = 0; i < a; i++) AD.push_back('0'); for(i = 0; i < b; i++) BC.push_back('0'); ans = Add(AC,AD); ans = Add(ans,BC); ans = Add(ans,BD); //累加結果 if(sign) ans.push_front('-'); } return ans; } } 還有一種：#include<iostream>#include<string>using namespace std;int x[50000], y[50000], z[250000000]={0}, p=0;//數組開到50000，支持50000位乘50000位的算式，代價就是占記憶體。 int main(){ string a,b; cin>>a>>b;//輸入因數 for(int i=0; i<a.size(); i++){ x[i] = a[a.size()-i-1]-48; } for(int i=0; i<b.size(); i++){ y[i] = b[b.size()-i-1]-48; }//這兩步是把字元串轉換成 數字，存在一個數組裡。 //這樣方便計算，但是如果不轉換也可以，只是麻煩一些。 for(int i=0; i<a.size(); i++){ for(int j=0; j<b.size(); j++){ z[i+j] += x[i]*y[j];//將積存在另一個數組裡。 while(z[i+j] > 9) z[i+j]-=10,z[i+j+1]++;//進位 } } for(int i=a.size()+b.size()-1; i>=0; i--){ //輸出 if(z[i]==0 && p==0 && i!=0) continue;//判斷最高位是否是0，如果是則不輸出。 else p=1; cout<<z[i]; } return 0;//最好還是返回一下，養成好習慣。 }//代碼提供者： 喲iudyoudavb6.0
Dim i, j, L(2), a(1000) As Integer, b(1000) As Integer, c(2000, 2000) As Integer, d(2000, 2000) As Integer, x(10000) As Integer, jieguo As String, y(10000) As IntegerPrivate Sub Command1_Click()L(1) = Len(Text2.Text)L(2) = Len(Text3.Text)For i = 1 To L(1)a(i) = Val(Mid(Text2.Text, L(1) - i + 1, 1))Next iFor i = 1 To L(2)b(i) = Val(Mid(Text3.Text, L(2) - i + 1, 1))Next iFor i = 1 To L(2)For j = 1 To L(1)c(i, j) = b(i) * a(j) + c(i, j)d(i, j) = Int(c(i, j) / 10)If d(i, j) > 0 Thenc(i, j) = c(i, j) - 10 * d(i, j)c(i, j + 1) = c(i, j + 1) + d(i, j)End Ifd(i, j) = 0Next jNext iFor i = 1 To L(2)b(i) = 0Next iFor i = 1 To L(1)a(i) = 0Next iFor i = 1 To L(2)For j = 1 To L(1) + 1x(i + j - 1) = x(i + j - 1) + c(i, j)c(i, j) = 0Next jNext iFor i = 1 To L(1) + L(2) + 1y(i) = Int(x(i) / 10)If y(i) > 0 Thenx(i) = x(i) - 10 * y(i)x(i + 1) = x(i + 1) + y(i)End Ify(i) = 0Next iText1.Text = ""If x(L(1) + L(2) + 1) <> 0 Then Text1.Text = Text1.Text & x(L(1) + L(2) + 1)If x(L(1) + L(2)) <> 0 Then Text1.Text = Text1.Text & x(L(1) + L(2))For i = L(1) + L(2) - 1 To 1 Step -1Text1.Text = Text1.Text & x(i)Next iFor i = 1 To L(1) + L(2) + 1x(i) = 0Next iL(1) = 0L(2) = 0jieguo = Text1.TextEnd SubPrivate Sub Form_Load()Text2.Text = "a"Text3.Text = "b"Text1.Text = "結果"Command1.Caption = "計算"Timer1.Interval = 1"interval，是間隔，值只能為數字而不能是truejieguo = "結果"End SubPrivate Sub Timer1_Timer()Text1.Text = jieguoEnd Sub
