进行高精度乘法运算时当数字输入位数超过大概105位时结果是错误的,此后随着输入位数的增加错误的位数也就越多,请问到底是怎么回事呢?
又该如何解决这个问题呢?
我的算法是模仿人类列竖式计算
下面是代码 乘法函数为BIgMultiply函数
#define _CRT_SECURE_NO_DEPRECATE
#pragma warning(disable:4996) //使scanf()函数可用
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 205 //精度(数字位数) +2
//将字符串变为倒序
void reverse(char a[]) {
static char a2[N];
memset(a2, 0, sizeof(a2));
int xa = strlen(a) - 1;
int j = 0;
for (int i = xa; i >= 0; i--) {
a2[j] = a[i];
j++;
}
memset(a, 0, sizeof(a));
strcpy(a, a2);
}
//将字符串换算为真实数字
void str2numArry(char a[]) {
for (int i = 0; a[i] != '\0'; i++) {
a[i] -= '0';
}
}
int strGetLongest(char a[], char b[]) {
int xa = strlen(a);
int xb = strlen(b);
int longest = xb;
if (xa >= xb) {
longest = xa;
}
return longest;
}
//运算得出的out[]是逆序的
void BigPlus(char ia[], char ib[], char ResultGet[]) {
static char out[N], a[N], b[N];
int JW;//进位
//初始化
memset(out, 0, sizeof(out));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(ResultGet, 0, sizeof(ResultGet));
strcpy(a, ia);
strcpy(b, ib);
//先将数字倒序(因为列竖式时需要右对齐且从需要从右往左算)
reverse(a);
reverse(b);
//取a,b之中最长的 长度?
int longest = strGetLongest(a, b);
//换算为真实数字
str2numArry(a);
str2numArry(b);
//因为转换为真实数字之后末尾的‘0’会变成‘\0’,又因为数组经过倒序处理,所以先导零将变成字符串结尾 '\0' 将被忽略。
//运算
JW = 0;
for (int i = 0; i <= longest; i++) {
out[i] = a[i] + b[i] + JW;
JW = 0;
if (out[i] >= 10) {
JW = out[i] / 10;
out[i] %= 10;
}
}
int j = 0;
while (out[longest] == 0 && longest > 0) {
longest--;
}
for (int i = longest; i >= 0; i--) {
ResultGet[j] = out[i] + '0';
j++;
}
ResultGet[j] = '\0';
}
void BigMinus(char ia[], char ib[], char ResultGet[]) {
static char out[N], a[N], b[N];
int JW;//借位
//初始化
memset(out, 0, sizeof(out));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(ResultGet, 0, sizeof(ResultGet));
strcpy(a, ia);
strcpy(b, ib);
//先将数字倒序(因为列竖式时需要右对齐且从需要从右往左算)
reverse(a);
reverse(b);
//取a,b之中最长的 长度?
int longest = strGetLongest(a, b);
//换算为真实数字
str2numArry(a);
str2numArry(b);
//因为转换为真实数字之后末尾的‘0’会变成‘\0’,又因为数组经过倒序处理,所以先导零将变成字符串结尾 '\0' 将被忽略。
//运算
JW = 0;
for (int i = 0; i < longest; i++) {
out[i] = a[i] - b[i] - JW;
JW = 0;
if (out[i] < 0) {
JW = 1;
out[i] += 10;
}
}
//逆序输出ASCII
int j = 0;
while (out[longest] == 0 && longest > 0) {
longest--;
}
for (int i = longest; i >= 0; i--) {
ResultGet[j] = out[i] + '0';
j++;
}
ResultGet[j] = '\0';
}
void BigMultiply(char ia[], char ib[], char ResultGet[]) {
static char out1[N][2 * N], a[N+84], b[N];
static long long int out[2 * N];
long long int JW;//进位
//初始化
memset(out, 0, sizeof(out));
memset(out1, 0, sizeof(out1));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(ResultGet, 0, sizeof(ResultGet));
strcpy(a, ia);
strcpy(b, ib);
//先将数字倒序(因为列竖式时需要右对齐且从需要从右往左算)
reverse(a);
reverse(b);
int la = strlen(a);
int lb = strlen(b);
int longest = strGetLongest(a, b) + 1;//中间过程结果长度可能的最大值
int longest_out = la + lb;//结果可能的最长长度
//换算为真实数字
str2numArry(a);
str2numArry(b);
//因为转换为真实数字之后末尾的‘0’会变成‘\0’,又因为数组经过倒序处理,所以先导零将变成字符串结尾 '\0' 将被忽略。
//运算
JW = 0;
for (int i = 0; i < lb; i++) {
for (int k = 0, m = i; k < longest + i; k++, m++) {//数组序列是从零开始的,用<
out1[i][m] = b[i] * a[k] + JW;
JW = 0;
if (out1[i][m] >= 10) {
JW = out1[i][m] / 10;
out1[i][m] %= 10;
}
printf("%d ", out1[i][k]);
}
putchar('\n');
}
putchar('\n');
putchar('\n');
//char test[50][50] = { {1,2,3},{1,1,1},{1,1,1} };
//lb是实际列数
for (int i = 0; i < longest_out; i++) {
out[i] = out1[0][i];
}
for (int i = 1; i < lb; i++) {
JW = 0;
for (int j = 0; j <= longest_out; j++) {
out[j] += out1[i][j] + JW;
//if(out[j] < 0 || out[j] > 9223372036854775000) exit(0);//test
JW = 0;
if (out[j] >= 10) {
JW = out[j] / 10;
out[j] %= 10;
}
//if (out[j] > 10) exit(0);//test
//if (JW > 10) exit(0);//test
}
}
//working
int j = 0;
while (out[longest_out] == 0 && longest_out > 0) {
longest_out--;
}
for (int i = longest_out; i >= 0; i--) {
ResultGet[j] = out[i] + '0';
//printf("%d",out[i]);
j++;
}
ResultGet[j] = '\0';
}
int main() {
//int T;
static char a[N], b[N], out[2 * N];
/*
scanf("%d", &T);
for (int i = 1; i <= T; i++) {
scanf("%s%s", a, b);
BigPlus(a, b, out);
printf("Case %d:\n%s + %s = %s\n\n", i, a, b, out);
}
*/
while (1) {
scanf("%s%s", a, b);
BigMultiply(a, b, out);
printf("%s", out);
putchar('\n');
}
return 0;
}
你如果要模拟列竖式,那你的所有中间结果也都应该用char[]来存啊,不要依赖long long int类型来保存中间结果,否则输入大到一定程度,中间结果溢出了
分析一个高精度算法
高精度加法
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
高精度减法
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精度乘低精度
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}