大數(shù)乘法

普通大數(shù)乘法

普通大數(shù)乘法模擬兩個(gè)數(shù)字豎式相乘,為了方便操作,數(shù)字的個(gè)位在數(shù)組的第0位,時(shí)間復(fù)雜度為O ( n2 )
Bull Math

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1200;
struct BigInt
{
    int num[MAXN];
    int len;//數(shù)字長(zhǎng)度
    void init()
    {
        memset(num,0,sizeof(num));
        len=0;
    }
    void setVal(char *str)
    {
        len=strlen(str);
        int index=0;
        while(str[index]=='0'&&len>1)//去除前導(dǎo)零
        {
            len--;
            index++;
        }
        for(int i=strlen(str)-1,j=0;i>=index;i--,j++)
        {
            num[j]=str[i]-'0';
        }
    }
    void out()//數(shù)字打印
    {
        for(int i=len-1;i>=0;i--)
        {
            printf("%d",num[i]);
        }
        printf("\n");
    }
    static BigInt multi(BigInt a,BigInt b)
    {
        BigInt c;
        c.init();
        c.len=a.len+b.len;//a與b相乘的長(zhǎng)度不超過a.len+b.len
        for(int i=0;i<a.len;i++)
        {
            for(int j=0;j<b.len;j++)
            {
                c.num[i+j]+=a.num[i]*b.num[j];
            }
        }
        for(int i=0;i<c.len;i++)
        {
            c.num[i+1]+=c.num[i]/10;
            c.num[i]%=10;
        }
        if(c.num[c.len-1]==0&&c.len>1) c.len--;//去除前導(dǎo)0
        if(c.num[c.len-1]==0&&c.len>1) c.len--;
        return c;
    }
};
int main()
{
    BigInt a,b,c;
    char v1[4500],v2[4500];
    scanf("%s%s",v1,v2);
    a.setVal(v1);
    b.setVal(v2);
    c=BigInt::multi(a,b);
    c.out();
}

Karatsuba algorithm

以下內(nèi)容為轉(zhuǎn)載

  • 概述
    　　Karatsuba乘法是一種快速乘法。此算法主要用于兩個(gè)大數(shù)相乘。普通乘法的復(fù)雜度是n2，而Karatsuba算法的復(fù)雜度僅為3nlog3≈3n1.585（log3是以2為底的）
    取m = (n+1)/2，把x寫成10m*a+b的形式，y寫成10m*c+d的形式，則a, b, c, d都是m位整數(shù)(如果不足m位，前面可以補(bǔ)0)。

    　　遞歸方程為T(n) = 4T(n/2) + O(n)，其中系數(shù)4為四次乘法ac, bd, bc, ad，附加代價(jià)n為最后一個(gè)return語句的兩次高精度加法。方程的解為T(n) = O(n^2)，和暴力乘法沒有區(qū)別。
    　　Anatolii Karatsuba在1962年提出一個(gè)改進(jìn)方法（并由Knuth改進(jìn)）：用ac和bd計(jì)算bc + ad，即：
    bc + ad = (a + b)*(c + d)-ac - bd
    這樣一來，只需要進(jìn)行三次遞歸乘法，即遞歸方程變?yōu)榱薚(n) = 3T(n/2)+O(n)，解為T(n) = O(nlog3) = O(n^1.585)，比暴力乘法快。
  • 偽代碼
procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* calculates the size of the numbers */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* split the digit sequences about the middle */
  x1, x0 = split_at(num1, m2)
  y1, y0 = split_at(num2, m2)
  /* 3 calls made to numbers approximately half the size */
  z0 = karatsuba(x0,y0)
  z1 = karatsuba((x1+x0),(y1+y0))
  z2 = karatsuba(x1,y1)
  return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

代碼參考來源

#include <iostream>
#include <string>
using namespace std;
//增加前導(dǎo)零,加減法法對(duì)齊時(shí)用到
void addPreZero(string &num,int len)
{
    while(len--)
    {
        num.insert(num.begin(),'0');
    }
}
//num=num*10^len
void shiftString(string &num,int len)
{
    if(num=="0") return ;//如果本身是0,不進(jìn)行任何操作,否則最終結(jié)果會(huì)出現(xiàn)前導(dǎo)零
    while(len--)
    {
        num.push_back('0');
    }
}
//對(duì)齊
int makeSameLen(string &num1,string&num2)
{
    int len1=num1.size();
    int len2=num2.size();
    if(len1>len2)
    {
        addPreZero(num2,len1-len2);
        return len1;
    }
    else
    {
        addPreZero(num1,len2-len1);
        return len2;
    }
}
//減法
string minusString(string num1,string num2)
{
    int len=makeSameLen(num1,num2);
    int carray=0,currVal;
    string res;
    for(int i=len-1;i>=0;i--)
    {
        currVal=num1[i]-num2[i]+carray;
        carray=0;
        if(currVal<0)
        {
            currVal+=10;
            carray=-1;
        }
        res.insert(res.begin(),currVal+'0');
    }
    //去掉前導(dǎo)零,只有減法才可能出現(xiàn)前導(dǎo)零,加法不會(huì)出現(xiàn)前導(dǎo)零,所以加法不用去
    string::iterator it=res.begin();
    while(it!=res.end()&&*it=='0') it++;
    if(it==res.end()) return "0";
    res.erase(res.begin(),it);
    return res;
}
//加法
string addString(string num1,string num2)
{
    int len=makeSameLen(num1,num2);
    string res;
    int carray=0,currVal;
    for(int i=len-1;i>=0;i--)
    {
        currVal=num1[i]-'0'+num2[i]-'0'+carray;
        carray=0;
        if(currVal>9)
        {
            currVal-=10;
            carray=1;
        }
        res.insert(res.begin(),currVal+'0');
    }
    if(carray) res.insert(res.begin(),'1');
    return res;
}
string toString(int num)
{
    if(num==0) return "0";
    string res;
    while(num)
    {
        res.insert(res.begin(),num%10+'0');
        num/=10;
    }
    return res;
}
string Karatsuba(string num1,string num2)
{
    int len=makeSameLen(num1,num2);
    if(len==0) return "0";
    if(len==1) return toString((num1[0]-'0')*(num2[0]-'0'));

    int mid=len/2;
    string a=num1.substr(0,mid),b=num1.substr(mid,len-mid);
    string c=num2.substr(0,mid),d=num2.substr(mid,len-mid);

    string z1=Karatsuba(a,c);
    string z2=Karatsuba(b,d);
    string z3=Karatsuba(addString(a,b),addString(c,d));

    z3=minusString(z3,z1);
    z3=minusString(z3,z2);
    shiftString(z1,2*(len-mid));
    shiftString(z3,len-mid);
    return addString(addString(z1,z2),z3);
}
int main(){
    int c;
    string a,b;
    cin>>a>>b;
    cout<<Karatsuba(a,b)<<endl;
    return 0;
}

FFT大數(shù)乘法
大數(shù)乘法（快速傅立葉變換）上
大數(shù)乘法（快速傅立葉變換）下

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN=300010;
const double PI=3.141592653;
char s1[MAXN],s2[MAXN];
int ans[MAXN];
double retmp[MAXN],intmp[MAXN];
double rea[MAXN],ina[MAXN],reb[MAXN],inb[MAXN];
void FFT(double *reA,double *inA,int n,int flag)
{
    if(n==1) return;
    double rewm=cos(2*PI/n),inwm=sin(2*PI/n);
    if(flag) inwm=-inwm;
    double rew=1.0,inw=0.0;
    //把下標(biāo)為偶數(shù)的值按順序放在前面,下標(biāo)為奇數(shù)的值按順序放在后面
    int i,j,k;
    for(i=0,k=1;k<n;k+=2,i++)
    {
        retmp[i]=reA[k];
        intmp[i]=inA[k];
    }
    for(j=2;j<n;j+=2)
    {
        reA[j/2]=reA[j];
        inA[j/2]=inA[j];
    }
    for(j=i,k=0;j<n&&k<i;j++,k++)
    {
        reA[j]=retmp[k];
        inA[j]=intmp[k];
    }
    int length=n/2;
    //遞歸處理
    FFT(reA,inA,length,flag);
    FFT(reA+length,inA+length,length,flag);
    for(k=0;k<length;k++)
    {
        int tag=k+length;
        double reT=rew*reA[tag]-inw*inA[tag];
        double inT=rew*inA[tag]+inw*reA[tag];
        double reU=reA[k],inU=inA[k];
        reA[k]=reU+reT;
        inA[k]=inU+inT;
        reA[tag]=reU-reT;
        inA[tag]=inU-inT;
        double rew_t=rew*rewm-inw*inwm;
        double inw_t=inw*rewm+rew*inwm;
        rew=rew_t;
        inw=inw_t;
    }
}
int main()
{
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        memset(rea,0,sizeof(rea));
        memset(ina,0,sizeof(ina));
        memset(reb,0,sizeof(reb));
        memset(inb,0,sizeof(inb));
        memset(ans,0,sizeof(ans));

        int len1=strlen(s1),len2=strlen(s2);
        //計(jì)算長(zhǎng)度為2的冪次方的len
        int len=len1>len2?len1:len2,base=1;
        while(base<len) base<<=1;
        base<<=1;
        len=base;
        //系數(shù)反轉(zhuǎn)并添加0使長(zhǎng)度湊成2的冪
        for(int i=0;i<len;i++)
        {
            if(len1>i) rea[i]=(double)(s1[len1-i-1]-'0');
            if(len2>i) reb[i]=(double)(s2[len2-i-1]-'0');
            ina[i]=inb[i]=0.0;
        }
        //分別把向量a和向量b的系數(shù)轉(zhuǎn)化為點(diǎn)值表示
        FFT(rea,ina,len,0);
        FFT(reb,inb,len,0);
        //點(diǎn)值相乘得到向量c的點(diǎn)值表示
        for(int i=0;i<len;i++)
        {
            double rec=rea[i]*reb[i]-ina[i]*inb[i];
            double inc=rea[i]*inb[i]+ina[i]*reb[i];
            rea[i]=rec;ina[i]=inc;
        }
        //將c的點(diǎn)值表示轉(zhuǎn)化為系數(shù)表示
        FFT(rea,ina,len,1);
        for(int i=0;i<len;i++)
        {
            rea[i]/=len;
            ina[i]/=len;
        }
        //進(jìn)位
        for(int i=0;i<len;i++)
        {
            ans[i]=(int)(rea[i]+0.5);
        }
        for(int i=0;i<len;i++)
        {
            ans[i+1]+=ans[i]/10;
            ans[i]=ans[i]%10;
        }
        int length=len;
        while(ans[length-1]==0&&length>1) length--;
        for(int i=length-1;i>=0;i--)
        {
            printf("%d",ans[i]);
        }
        printf("\n");
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 大數(shù)乘法的算法 大數(shù)乘法的關(guān)鍵在于如何用字符串來模擬大數(shù)乘法。方法有如下幾種：模擬普通的手算乘法、利用代數(shù)方法優(yōu)化...
    胡哈哈哈閱讀 2,068評(píng)論 0贊 0
  • 近日參加一個(gè)筆試，遇到大數(shù)乘法問題，這是一個(gè)經(jīng)典的算法題。所謂大數(shù)乘法問題其實(shí)就是這樣的：輸入兩個(gè)整數(shù)，要求輸出這...
    拉普拉斯妖kk閱讀 3,177評(píng)論 0贊 2
  • 1、大數(shù)乘法 （1）轉(zhuǎn)換并反轉(zhuǎn)，字符串轉(zhuǎn)換為數(shù)字并將字序反轉(zhuǎn)； （2）自動(dòng)移位，逐位相乘，添加最后的進(jìn)位； （3）...
    saviochen閱讀 587評(píng)論 0贊 2
  • 大數(shù)乘法：
    HangChen閱讀 350評(píng)論 0贊 0
  • 每個(gè)人都是有故事的人 你的故事或許平淡無奇 誰說平凡的人沒有做夢(mèng)的權(quán)利 沒人干涉你去追求幸福 你想要的詩(shī)和遠(yuǎn)方 是...
    北方小確幸閱讀 294評(píng)論 0贊 1

友情鏈接更多精彩內(nèi)容