高精度乘法怎么做,C\C++交流,技术交流,鱼C论坛

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

高精度乘法怎么做

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

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 = * (len1 + len2)

for i in range(len1 - 1, -1, -1):
   for j in range(len2 - 1, -1, -1):
         temp = int(num1) * int(num2)
         # 将乘法结果加到结果数组的相应位置上
         result += temp
         # 处理进位
         result += result // 10
         result %= 10

# 去掉结果数组最高位上的0
while len(result) > 1 and result == 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={0},b={0},c={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=str1-'0'; //将str1倒序存储到a中，方便从个位开始逐位相乘
for(int i=len2-1;i>=0;i--)
   b=str2-'0'; //同上
for(int i=1;i<=len1;i++)
   for(int j=1;j<=len2;j++)
         c+=a*b; //根据乘法术算法进行累加
for(int i=1;i<=len1+len2;i++)
{
   c+=c/10; //进位
   c%=10; //取余数
}
int len=len1+len2;
while(c==0 && len>1) len--; //去掉前导0
for(int i=len;i>=1;i--)
   cout<<c; //逆序输出
return 0;
}

sfqxx 发表于 2023-12-30 20:08:17

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,b;
int rev,ans;
char s1,s2;
//读入优化
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=(rev>>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时才交换，防止同一个元素交换两次，回到它原来的位置。
   if(i<rev)swap(a,a]);
}
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;
      cp y=w*a;
      a=x+y;//这两步是蝴蝶变换
      a=x-y;
      w*=wn; //求w_n^k
   }
}
}
//判断是否是FFT还是IFFT
if(flag==-1)
for(int i=0;i<n;i++)
a/=n;
}
int main(){
n=read();
scanf("%s%s",s1,s2);
//读入的数的每一位看成多项式的一项，保存在复数的实部
for(int i=0;i<n;i++)a=(double)(s1-'0');
for(int i=0;i<n;i++)b=(double)(s2-'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*=b;
//IFFT 把这个点值表示转化为系数表示
fft(a,s,-1);
//保存答案的每一位(注意进位）
for(int i=0;i<s;i++)
{
//取实数四舍五入，此时虚数部分应当为0或由于浮点误差接近0
ans+=(int)(a.real()+0.5);
ans+=ans/10;
ans%=10;
}
while(!ans&&s>-1)s--;
if(s==-1)printf("0");
else
for(int i=s;i>=0;i--)
printf("%d",ans);
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
他能看懂我不确定，但是这个是对的一定是确定的。

嗯，对是对的，就是太超前了{:10_256:}

我当时用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 = '0';
}
result = '\0';

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

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

// 如果有前导零，则移除它们
if (i > 0) {
   memmove(result, &result, n - i);
   result = '\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

页: [1]

鱼C论坛's Archiver

高精度乘法怎么做