高精度乘法怎么做

小启洋同学

？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

FishC

要实现高精度乘法，可以利用字符串来表示大数，然后模拟手算的乘法过程。

具体步骤如下：

1. 首先将两个乘数转换为字符串，并获取它们的长度。

2. 创建一个长度为乘数1长度 + 乘数2长度的数组，用于存储乘法结果。

3. 从乘数1的最低位开始，依次与乘数2的各个位相乘，并将结果加到结果数组中相应的位置上。

4. 遍历结果数组，将超过10的部分进位到前一位，并去掉最高位上的0。

5. 最后将结果数组转换为字符串，即为乘法结果。

下面是一个示例代码：

def multiply(num1, num2):    len1 = len(num1)    len2 = len(num2)    result = [0] * (len1 + len2)    for i in range(len1 - 1, -1, -1):        for j in range(len2 - 1, -1, -1):            temp = int(num1[i]) * int(num2[j])            # 将乘法结果加到结果数组的相应位置上            result[i + j + 1] += temp            # 处理进位            result[i + j] += result[i + j + 1] // 10            result[i + j + 1] %= 10    # 去掉结果数组最高位上的0    while len(result) > 1 and result[0] == 0:        result.pop(0)    # 将结果数组转换为字符串    return ''.join(str(num) for num in result)# 测试print(multiply("123", "456"))  # 输出: 56088

这样就实现了高精度乘法的功能。你可以将乘数1和乘数2换成其他大数来测试代码的正确性。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sfqxx

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int MAXN = 2005;
int a[MAXN]={0},b[MAXN]={0},c[MAXN*2]={0};

int main()
{
    string str1,str2;
    cin>>str1>>str2;
    int len1=str1.length();
    int len2=str2.length();
    for(int i=len1-1;i>=0;i--)
        a[len1-i]=str1[i]-'0'; //将str1倒序存储到a中，方便从个位开始逐位相乘
    for(int i=len2-1;i>=0;i--)
        b[len2-i]=str2[i]-'0'; //同上
    for(int i=1;i<=len1;i++)
        for(int j=1;j<=len2;j++)
            c[i+j-1]+=a[i]*b[j]; //根据乘法术算法进行累加
    for(int i=1;i<=len1+len2;i++)
    {
        c[i+1]+=c[i]/10; //进位
        c[i]%=10; //取余数
    }
    int len=len1+len2;
    while(c[len]==0 && len>1) len--; //去掉前导0
    for(int i=len;i>=1;i--)
        cout<<c[i]; //逆序输出
    return 0;
}

sfqxx

[b]

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int MAXN = 2005;
int a[MAXN]={0},b[MAXN]={0},c[MAXN*2]={0};

int main()
{
    string str1,str2;
    cin>>str1>>str2;
    int len1=str1.length();
    int len2=str2.length();
    for(int i=len1-1;i>=0;i--)
        a[len1-i]=str1[i]-'0'; //将str1倒序存储到a中，方便从个位开始逐位相乘
    for(int i=len2-1;i>=0;i--)
        b[len2-i]=str2[i]-'0'; //同上
    for(int i=1;i<=len1;i++)
        for(int j=1;j<=len2;j++)
            c[i+j-1]+=a[i]*b[j]; //根据乘法术算法进行累加
    for(int i=1;i<=len1+len2;i++)
    {
        c[i+1]+=c[i]/10; //进位
        c[i]%=10; //取余数
    }
    int len=len1+len2;
    while(c[len]==0 && len>1) len--; //去掉前导0
    for(int i=len;i>=1;i--)
        cout<<c[i]; //逆序输出
    return 0;
}

这个不行吗
[/b]

zhangjinxuan

可以使用快速傅里叶变换来解决高精度乘法问题，因为高精度乘法本质上也是多项式乘法。

代码（转载自 https://www.luogu.com.cn/blog/_post/158304 ）：

#include<bits/stdc++.h>
using namespace std;
//complex是stl自带的定义复数的容器 
typedef complex<double> cp;
#define N 2097153
//pie表示圆周率π 
const double pie=acos(-1);
int n;
cp a[N],b[N];
int rev[N],ans[N];
char s1[N],s2[N];
//读入优化 
int read(){
        int sum=0,f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
        return sum*f;
}
//初始化每个位置最终到达的位置 
{
    int len=1<<k;
        for(int i=0;i<len;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
}
//a表示要操作的系数，n表示序列长度
//若flag为1，则表示FFT，为-1则为IFFT(需要求倒数） 
void fft(cp *a,int n,int flag){ 
    for(int i=0;i<n;i++)
        {
         //i小于rev[i]时才交换，防止同一个元素交换两次，回到它原来的位置。 
          if(i<rev[i])swap(a[i],a[rev[i]]);
        }
        for(int h=1;h<n;h*=2)//h是准备合并序列的长度的二分之一
        {
        cp wn=exp(cp(0,flag*pie/h));//求单位根w_n^1 
         for(int j=0;j<n;j+=h*2)//j表示合并到了哪一位
         {
          cp w(1,0);
           for(int k=j;k<j+h;k++)//只扫左半部分，得到右半部分的答案
           {
             cp x=a[k];
             cp y=w*a[k+h];
         a[k]=x+y;  //这两步是蝴蝶变换 
         a[k+h]=x-y;
         w*=wn; //求w_n^k 
           }
         }
         }
         //判断是否是FFT还是IFFT 
         if(flag==-1)
         for(int i=0;i<n;i++)
     a[i]/=n;
}
int main(){
        n=read(); 
        scanf("%s%s",s1,s2);
        //读入的数的每一位看成多项式的一项，保存在复数的实部 
    for(int i=0;i<n;i++)a[i]=(double)(s1[n-i-1]-'0');
        for(int i=0;i<n;i++)b[i]=(double)(s2[n-i-1]-'0');
        //k表示转化成二进制的位数 
        int k=1,s=2;
         while((1<<k)<2*n-1)k++,s<<=1;
        init(k);
        //FFT 把a的系数表示转化为点值表示 
    fft(a,s,1);
    //FFT 把b的系数表示转化为点值表示 
    fft(b,s,1);
    //FFT 两个多项式的点值表示相乘 
    for(int i=0;i<s;i++)
    a[i]*=b[i];
    //IFFT 把这个点值表示转化为系数表示 
    fft(a,s,-1);
    //保存答案的每一位(注意进位） 
    for(int i=0;i<s;i++)
    {
    //取实数四舍五入，此时虚数部分应当为0或由于浮点误差接近0
        ans[i]+=(int)(a[i].real()+0.5);
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
        }
        while(!ans[s]&&s>-1)s--;
        if(s==-1)printf("0");
        else
        for(int i=s;i>=0;i--)
        printf("%d",ans[i]);
        return 0;
}

zhangjinxuan

sfqxx 发表于 2023-12-30 20:08
这个不行吗

这个不行，太慢了，看 5#

sfqxx

zhangjinxuan 发表于 2023-12-31 08:34
这个不行，太慢了，看 5#

这个难度大概是提高+/省选-。你确定他看得懂吗？

zhangjinxuan

sfqxx 发表于 2023-12-31 08:41
这个难度大概是提高+/省选-。你确定他看得懂吗？

他能看懂我不确定，但是这个是对的一定是确定的。

sfqxx

zhangjinxuan 发表于 2023-12-31 09:08
他能看懂我不确定，但是这个是对的一定是确定的。

嗯，对是对的，就是太超前了

我当时用haskell做的

zhangchenyvn

这是AI给的代码，不知道好不好用

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void multiply(const char *num1, const char *num2, char *result) {
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    int n = len1 + len2;
    int temp, i, j;

    // 初始化结果数组为0
    for (i = 0; i < n; i++) {
        result[i] = '0';
    }
    result[n] = '\0';

    // 从字符串尾部开始逐位相乘
    for (i = len1 - 1; i >= 0; i--) {
        for (j = len2 - 1; j >= 0; j--) {
            temp = (num1[i] - '0') * (num2[j] - '0') + (result[i + j + 1] - '0');
            result[i + j + 1] = (temp % 10) + '0'; // 当前位
            result[i + j] += temp / 10;             // 进位
        }
    }

    // 找到结果数组中第一个非零数字的索引
    for (i = 0; i < n - 1 && result[i] == '0'; i++);

    // 如果有前导零，则移除它们
    if (i > 0) {
        memmove(result, &result[i], n - i);
        result[n - i] = '\0';
    }
}

int main(void) {
    const char *num1 = "123";
    const char *num2 = "456";
    
    // 结果字符串长度为两个乘数长度之和
    int length = strlen(num1) + strlen(num2);
    
    // 分配内存以存储结果，包括结束符'\0'
    char *result = malloc(length + 1);
    
    multiply(num1, num2, result);

    printf("%s\n", result); // 输出: 56088
    
    free(result); 
   
    return 0;
}

zhangchenyvn

zhangchenyvn 发表于 2024-1-3 20:14
这是AI给的代码，不知道好不好用

模型式ChatGPT4 128K Prevew