高精度乘法怎么做

小启洋同学

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

FishC

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

具体步骤如下：

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

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

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

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

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

下面是一个示例代码：

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

复制代码

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

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

sfqxx

1. #include<iostream>
   
2. #include<string>
   
3. #include<algorithm>
   
4. using namespace std;
   
5. 
   
6. const int MAXN = 2005;
   
7. int a[MAXN]={0},b[MAXN]={0},c[MAXN*2]={0};
   
8. 
   
9. int main()
   
10. {
    
11.     string str1,str2;
    
12.     cin>>str1>>str2;
    
13.     int len1=str1.length();
    
14.     int len2=str2.length();
    
15.     for(int i=len1-1;i>=0;i--)
    
16.         a[len1-i]=str1[i]-'0'; //将str1倒序存储到a中，方便从个位开始逐位相乘
    
17.     for(int i=len2-1;i>=0;i--)
    
18.         b[len2-i]=str2[i]-'0'; //同上
    
19.     for(int i=1;i<=len1;i++)
    
20.         for(int j=1;j<=len2;j++)
    
21.             c[i+j-1]+=a[i]*b[j]; //根据乘法术算法进行累加
    
22.     for(int i=1;i<=len1+len2;i++)
    
23.     {
    
24.         c[i+1]+=c[i]/10; //进位
    
25.         c[i]%=10; //取余数
    
26.     }
    
27.     int len=len1+len2;
    
28.     while(c[len]==0 && len>1) len--; //去掉前导0
    
29.     for(int i=len;i>=1;i--)
    
30.         cout<<c[i]; //逆序输出
    
31.     return 0;
    
32. }

复制代码

sfqxx

[b]

1. #include<iostream>
   
2. #include<string>
   
3. #include<algorithm>
   
4. using namespace std;
   
5. 
   
6. const int MAXN = 2005;
   
7. int a[MAXN]={0},b[MAXN]={0},c[MAXN*2]={0};
   
8. 
   
9. int main()
   
10. {
    
11.     string str1,str2;
    
12.     cin>>str1>>str2;
    
13.     int len1=str1.length();
    
14.     int len2=str2.length();
    
15.     for(int i=len1-1;i>=0;i--)
    
16.         a[len1-i]=str1[i]-'0'; //将str1倒序存储到a中，方便从个位开始逐位相乘
    
17.     for(int i=len2-1;i>=0;i--)
    
18.         b[len2-i]=str2[i]-'0'; //同上
    
19.     for(int i=1;i<=len1;i++)
    
20.         for(int j=1;j<=len2;j++)
    
21.             c[i+j-1]+=a[i]*b[j]; //根据乘法术算法进行累加
    
22.     for(int i=1;i<=len1+len2;i++)
    
23.     {
    
24.         c[i+1]+=c[i]/10; //进位
    
25.         c[i]%=10; //取余数
    
26.     }
    
27.     int len=len1+len2;
    
28.     while(c[len]==0 && len>1) len--; //去掉前导0
    
29.     for(int i=len;i>=1;i--)
    
30.         cout<<c[i]; //逆序输出
    
31.     return 0;
    
32. }

复制代码

这个不行吗
[/b]

zhangjinxuan

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

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

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. //complex是stl自带的定义复数的容器
   
4. typedef complex<double> cp;
   
5. #define N 2097153
   
6. //pie表示圆周率π
   
7. const double pie=acos(-1);
   
8. int n;
   
9. cp a[N],b[N];
   
10. int rev[N],ans[N];
    
11. char s1[N],s2[N];
    
12. //读入优化
    
13. int read(){
    
14.         int sum=0,f=1;
    
15.         char ch=getchar();
    
16.         while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    
17.         while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    
18.         return sum*f;
    
19. }
    
20. //初始化每个位置最终到达的位置
    
21. {
    
22.     int len=1<<k;
    
23.         for(int i=0;i<len;i++)
    
24.         rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    
25. }
    
26. //a表示要操作的系数，n表示序列长度
    
27. //若flag为1，则表示FFT，为-1则为IFFT(需要求倒数）
    
28. void fft(cp *a,int n,int flag){
    
29.     for(int i=0;i<n;i++)
    
30.         {
    
31.          //i小于rev[i]时才交换，防止同一个元素交换两次，回到它原来的位置。
    
32.           if(i<rev[i])swap(a[i],a[rev[i]]);
    
33.         }
    
34.         for(int h=1;h<n;h*=2)//h是准备合并序列的长度的二分之一
    
35.         {
    
36.         cp wn=exp(cp(0,flag*pie/h));//求单位根w_n^1
    
37.          for(int j=0;j<n;j+=h*2)//j表示合并到了哪一位
    
38.          {
    
39.           cp w(1,0);
    
40.            for(int k=j;k<j+h;k++)//只扫左半部分，得到右半部分的答案
    
41.            {
    
42.              cp x=a[k];
    
43.              cp y=w*a[k+h];
    
44.          a[k]=x+y;  //这两步是蝴蝶变换
    
45.          a[k+h]=x-y;
    
46.          w*=wn; //求w_n^k
    
47.            }
    
48.          }
    
49.          }
    
50.          //判断是否是FFT还是IFFT
    
51.          if(flag==-1)
    
52.          for(int i=0;i<n;i++)
    
53.      a[i]/=n;
    
54. }
    
55. int main(){
    
56.         n=read();
    
57.         scanf("%s%s",s1,s2);
    
58.         //读入的数的每一位看成多项式的一项，保存在复数的实部
    
59.     for(int i=0;i<n;i++)a[i]=(double)(s1[n-i-1]-'0');
    
60.         for(int i=0;i<n;i++)b[i]=(double)(s2[n-i-1]-'0');
    
61.         //k表示转化成二进制的位数
    
62.         int k=1,s=2;
    
63.         while((1<<k)<2*n-1)k++,s<<=1;
    
64.         init(k);
    
65.         //FFT 把a的系数表示转化为点值表示
    
66.     fft(a,s,1);
    
67.     //FFT 把b的系数表示转化为点值表示
    
68.     fft(b,s,1);
    
69.     //FFT 两个多项式的点值表示相乘
    
70.     for(int i=0;i<s;i++)
    
71.     a[i]*=b[i];
    
72.     //IFFT 把这个点值表示转化为系数表示
    
73.     fft(a,s,-1);
    
74.     //保存答案的每一位(注意进位）
    
75.     for(int i=0;i<s;i++)
    
76.     {
    
77.     //取实数四舍五入，此时虚数部分应当为0或由于浮点误差接近0
    
78.         ans[i]+=(int)(a[i].real()+0.5);
    
79.         ans[i+1]+=ans[i]/10;
    
80.         ans[i]%=10;
    
81.         }
    
82.         while(!ans[s]&&s>-1)s--;
    
83.         if(s==-1)printf("0");
    
84.         else
    
85.         for(int i=s;i>=0;i--)
    
86.         printf("%d",ans[i]);
    
87.         return 0;
    
88. }

复制代码

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给的代码，不知道好不好用

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. 
   
6. void multiply(const char *num1, const char *num2, char *result) {
   
7.     int len1 = strlen(num1);
   
8.     int len2 = strlen(num2);
   
9.     int n = len1 + len2;
   
10.     int temp, i, j;
    
11. 
    
12.     // 初始化结果数组为0
    
13.     for (i = 0; i < n; i++) {
    
14.         result[i] = '0';
    
15.     }
    
16.     result[n] = '\0';
    
17. 
    
18.     // 从字符串尾部开始逐位相乘
    
19.     for (i = len1 - 1; i >= 0; i--) {
    
20.         for (j = len2 - 1; j >= 0; j--) {
    
21.             temp = (num1[i] - '0') * (num2[j] - '0') + (result[i + j + 1] - '0');
    
22.             result[i + j + 1] = (temp % 10) + '0'; // 当前位
    
23.             result[i + j] += temp / 10;             // 进位
    
24.         }
    
25.     }
    
26. 
    
27.     // 找到结果数组中第一个非零数字的索引
    
28.     for (i = 0; i < n - 1 && result[i] == '0'; i++);
    
29. 
    
30.     // 如果有前导零，则移除它们
    
31.     if (i > 0) {
    
32.         memmove(result, &result[i], n - i);
    
33.         result[n - i] = '\0';
    
34.     }
    
35. }
    
36. 
    
37. int main(void) {
    
38.     const char *num1 = "123";
    
39.     const char *num2 = "456";
    
40.    
    
41.     // 结果字符串长度为两个乘数长度之和
    
42.     int length = strlen(num1) + strlen(num2);
    
43.    
    
44.     // 分配内存以存储结果，包括结束符'\0'
    
45.     char *result = malloc(length + 1);
    
46.    
    
47.     multiply(num1, num2, result);
    
48. 
    
49.     printf("%s\n", result); // 输出: 56088
    
50.    
    
51.     free(result);
    
52.    
    
53.     return 0;
    
54. }
    

复制代码

zhangchenyvn

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

模型式ChatGPT4 128K Prevew