高精度乘法怎么做

小启洋同学 · 发表于 2023-12-30 15:02:19

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

FishC · 发表于 2023-12-30 15:02:32

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

具体步骤如下：

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 · 发表于 2023-12-30 15:18:23

#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 · 发表于 2023-12-30 20:08:17

#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;

}
复制代码

这个不行吗

zhangjinxuan · 发表于 2023-12-31 08:24:05

本帖最后由 zhangjinxuan 于 2023-12-31 08:34 编辑

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

代码（转载自 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 · 发表于 2023-12-31 08:34:54

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

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

sfqxx · 发表于 2023-12-31 08:41:21

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

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

zhangjinxuan · 发表于 2023-12-31 09:08:35

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

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

sfqxx · 发表于 2023-12-31 09:24:51

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

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

我当时用haskell做的

zhangchenyvn · 发表于 2024-1-3 20:14:57

这是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 · 发表于 2024-1-3 20:15:55

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

模型式ChatGPT4 128K Prevew

账号		自动登录	找回密码
密码			立即注册