❶ 如何實現兩個超大整數的相乘
*函數名稱： 大數乘法
*函數過程：1 輸入兩個大數作為字元串
* 2 作一個雙向鏈表
* 3 兩個指針分別指向數字字元串的最低位
* 4 以第一個數的最低的一個位乘以第二個數的所有項存於鏈表中
* 5 鏈表首指針移
* 6 重復4，5依次從最低位乘到最高位
* 7 乘完後因為最低位是鏈表首，最後一位是鏈表尾。所以在逆順輸出鏈表。
* 4 直到循環結束
*入口參數：numa，numb，result字元串
*出口參數：無
*--------------------------------------------------------------------------*/
void multiply(char *numa, char *numb ,char *result)//用來儲結果的)//計算乘積
{
char *pna = findend(numa);//指向numa的一個指針。point numa pna 指向乘數的最低位，
char *pnb = findend(numb);//指向numb的一個指針 //pnb 指向被乘數的最低位，
int along=(int)strlen(numa);//標記數字a的長度；
int blong=(int)strlen(numb);//標記數字b的長度；
int carry=0,temp_result;//存貯進位 和臨時結果的
Node *head, // 用於存貯頭指針
*pstart, // 用於存貯計算時的首指針
*pnew, //作於申請新結點
*pgo; //作為每計算完一行時，回到下一行起始節點用,移位標致來用
head = pstart =new Node;//初始化首結點和頭結點。
pstart -> data = 0;
pstart -> next = NULL;
pstart -> ahead = NULL;
while (along--)
{
pgo = pstart;//保存進位點
blong = (int)strlen(numb);//初始化長度
pnb = findend(numb); //初始化指針
while ((blong-- && (blong>=0))|| carry != 0)
{
if(!pstart->next)//如果當前為空結點，則申請新結點
{
pnew = new Node;
pnew -> data = 0;
pnew -> next = NULL;
pnew -> ahead = pstart;
pstart -> next = pnew;
}
if(blong<0)temp_result = carry ;//處理只有進位的情況
else temp_result =(pstart->data+(*pna-48)*(*pnb-48)+carry);//自身值+新值+進位作為新值
pstart -> data = temp_result%10; //存貯個位
carry = temp_result/10; //存貯進位
pstart = pstart -> next; //結點移動
pnb--; //指針移向被乘數高位
}
pstart = pgo->next; //前進一個位置；
pna--; //指針移向乘數高位
}
pstart =head;//尋找鏈表的結尾點
while(pstart->next != 0)
{
pstart->data += 48;//!!<<<因為我們的輸出是字元。所以再此加上48>>>> 逆順輸出
pstart = pstart->next ;
}
int tip = 0;//轉為字元串用
pstart = pstart->ahead ;//找有效字
while(pstart != 0)//輸出正序的結果；
{
result[tip++] = pstart->data;
pstart = pstart->ahead ;
}
result[tip] = '\0';
pstart =head; //釋放空間
while(pstart->next != 0)
{
pnew = pstart->next ;delete pstart;
pstart =pnew;
}
return ;
}
❷ 求高手幫忙——大整數乘法的演算法
就是高精度乘
模擬小學時學乘法豎式的方法
比如123*456
首先用一個數組a保存123
a[0]=1;a[1]=2;a[2]=3;
再用另外一個數組b保存456
b[0]=4;b[1]=5;b[2]=6;
做三次高精乘單精，如下：
a乘以b[0]，得到c0數組為
c0[0]=a[0]*b[0]=4
c0[1]=a[1]*b[0]=8
c0[2]=a[2]*b[0]=12
a乘以b[1]，得到c1數組為
c1[0]=a[0]*b[1]=5
c1[1]=a[1]*b[1]=10
c1[2]=a[2]*b[1]=15
同理，a乘以b[2]，得到c2數組為
c2[0]=6
c2[1]=12
c2[2]=18
下一步，是c0c1c2三個數組，依次移位相加，得到數組d，如下：
c0[0]c0[1]c0[2]
______c1[0]c1[1]c1[2]
____________c2[0]c2[1]c2[2]
--------------------------------
_d[0]d[1]d[2]d[3]d[4]
_413282718
最後一步，是對d數組的整理啦
從個位開始，每一位，如果大於9，則求模，前一位進位
for(i=4;i>0;i--)
__if(d[i]>9)
__{
____d[i-1]+=d[i]/10;
____d[i]=d[i]%10;
__}
經過整理，數組d各元素如下：
d[0]d[1]d[2]d[3]d[4]
56088
因此，依次輸出，得到56088
123*456=56088
大數相乘亦此道理也~
❸ 大數乘法的幾種演算法分析及比較
1、分治乘法（最簡單的是Karatsuba乘法，一般化以後有Toom-Cook乘法）；
2、快速傅里葉變換FFT(為了避免精度問題，可以改用快速數論變換FNTT)，時間復雜度O(NlgNlglgN)；
3、中國剩餘定理（把每個數分解到一些互素的模上，然後每個同餘方程對應乘起來就行）；
4、剛看到一個比FFT還快的演算法Furer's algorithm，不過好像不太實用。下面的reference[3]給出了
❹ c語言大整數乘法
dc這個函數裡面連b這個參數都沒有使用，這也能出結果...，
if(z[0]='0')continue 也寫錯了
不是打擊你，你的代碼太濫了，實在不想去找錯誤，給你我以前寫的代碼吧，你自己整理一下
#include <stdio.h>
int mulx(char * a,int b,char * r,int d);
void init(char * s);
char buf1[4*1024];
char buf2[4*1024];
char buf3[4*1024];
int main()
{
char * a;
char * b;
char * r;
char * t;
int d;
int i;
a = buf1;
b = buf2;
r = buf3;
init(NULL);
while(scanf("%s %d",a,&d)!=EOF)
{
mulx(a,d,r,10);
printf("%s\n",r);
}
return 0;
}
char c2d[256]; //字元轉換成數字
char * charset; //代表數字的字元
/*功能：設置使用那些字元表示數字，默認的為"0123456789ABCDEF"*/
/*參數：*/
/*返回值：*/
void init(char * s)
{
int i;
if(s==NULL)
charset = "0123456789ABCDEF";
else
charset = s;
for(i=0;i<256;i++)
c2d[i] = 0;
for(i=0;charset[i];i++)
c2d[charset[i]] = i;
}
/*功能：清除前導零*/
/*參數：需要清楚的數字*/
/*返回值：清零後數字的位數*/
int clearZeros(char * a)
{
int i,j;
for(i=0;a[i]==charset[0];i++);
for(j=0;a[i];i++,j++)
a[j] = a[i];
a[j] = 0;
if(j==0)
{
a[j++] = charset[0];
a[j] = 0;
}
return j;
}
/*功能：乘,用於進制轉換之類*/
/*參數：a 和 b 分別為乘數，結果保存到 r , d 為使用的進制*/
/*注意：r 可以等於 a , b一定要小於d, 如果被乘數有前導0 則結果也會有前導0*/
/*返回值：結果的位數*/
int mulx(char * a,int b,char * r,int d)
{
int i,j,k,len;
int c,t;
if(r==NULL)
r = a;
for(i=0;a[i];i++);
len = k = i;
for(c=0,i--,r[k--]=0;i>=0 ;i--,k--)
{
t = c2d[a[i]] * b + c ;
c = t/d;
r[k] = charset[t%d];
}
if(c)
{
for(i=len,j=++len;i>=0;i--,j--)
r[j] = r[i];
r[0]=charset[c];
}
return len;
}
❺ 大數相乘 快速演算法
給你一個吧
速度還可以
自己讀下代碼
/**************************************
演算法復雜度為：O(longhta*longthb）
longtha為乘數的位數
longhtb為被乘數的位數
***************************************/
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define LEN 1000
void mult(char [],char [],char []);
main()
{
char op1[LEN],op2[LEN],op3[LEN*2-1];
scanf("%s%s",op1,op2);
mult(op1,op2,op3);
printf("%s\n",op3);
getch();
return 0;
}
void reverse(char a[])
{
int longth=strlen(a);
int i;
for(i=0;i<longth/2;i++){
char t;
t=a[i];
a[i]=a[longth-i-1];
a[longth-i-1]=t;
}
}
void mult(char op1[LEN],char op2[LEN],char ans[LEN*2-1])
{
char top1[LEN];
char top2[LEN];
strcpy(top1,op1);
strcpy(top2,op2);
reverse(top1);
reverse(top2);
int k;
int top1s=strlen(top1);
int top2s=strlen(top2);
for(k=0;k<top1s+top2s;k++){
ans[k]='0';
}
int i,j;
int jw,ys;
int longth;
for(j=0;j<top2s;j++){
jw=0;
for(i=0;i<top1s;i++){
ys=((top1[i]-'0')*(top2[j]-'0')+jw+ans[i+j]-'0')%10;
jw=((top1[i]-'0')*(top2[j]-'0')+jw+ans[i+j]-'0')/10;
ans[i+j]=ys+'0';
}
if(jw>0){
ans[i+j]=jw+'0';
}
}
longth=i+j-1;
if(jw>0)
ans[longth++]=jw+'0';
ans[longth]='\0';
reverse(ans);
}