高精度乘法_高精度乘法核心算法

1.高精度乘法原理

高精度乘法问题主要利用了乘法原理，利用字符数组存放超过数字类型长度的数，然后将字符数组的值转入数字数组内进行计算。

该算法的核心就是利用两个循环依次循环处理各位数，然后判断是否需要进位。

# include <stdio.h>
# include <string.h>  // 调用strlen函数的头文件
#pragma warning(disable:4996)
int main(void) {
	char a1[250], b1[250];  // 先定义两个字符数组，用于存储两个较多位数的乘数
	int a[250], b[250], c[500] = { 0 };  // 再定义三个数组，前两个用于存放字符数组里的数字各个位的数值，最后一个用于存储最终结果的各个位的数值
	int len1, len2, len;  // 前两个分别表示字符数组a1,b1的实际长度，最后一个表示两个字符数组实际长度之和
	scanf("%s%s", a1, b1);  // 对两个字符数组进行赋值
	len1 = strlen(a1);  // 将字符串a1的长度赋给len1，用于数组的赋值
	len2 = strlen(b1);  // 将字符串b1的长度赋给len2, 用于数组的赋值
	len = len1 + len2;  // 将两字符串实际长度之和赋给len
	for (int i = 0; i < len1; i++)   // 用for循环，实现字符数组a1内数字向数组转移
		a[i] = a1[len1 - 1 - i] - '0';//由于乘法是从个位数依次处理至高位，所以讲数字倒序
	/* 不过，字符数组内的数字与数组内数字顺序相反，这与乘法原理有关，根据ASCII，字符数组内的数字要转化成实际的数字，就要减去48，因为‘0’的ASCII码恰好是48，所以将字符数组元素－‘0’以实现转化 */
	for (int j = 0; j < len2; j++) // 用for循环，实现字符数组b1内数字向数组转移
		b[j] = b1[len1 - 1 - j] - '0';
	for (int i = 0; i < len1; i++)  // 接下来这两个嵌套的for循环便是高精度乘法的核心
		for (int j = 0; j < len2; j++) { // 此处这短短三步需要结合乘法原理理解，用文字很难表达
			c[i + j] += a[i] * b[j];  // 数字的其中一位与另一数字其中一位相乘，先不考虑进位情况
			c[i + j + 1] += (c[i + j]) / 10;  // 除以10的作用便是判断进多少（注意是c[i+j]）
			c[i + j] = c[i + j] % 10;  // 进位结束以后该数位便只去各位，故将其取余取余数（注意是c[i+j]）
		}  // 此处第一、第二个式子用+=，原因可根据乘法原理解释，第三个式子无需+=，原因是取该位数总值的个位即可
	if (c[len - 1] == 0)  //  此处是判断输出的第一个数位是否为0，若为0，忽略该位数，即总长减去1
		len--;
	for (int i = len - 1; i >= 0; i--) // 倒着输出数组内的数字，得到最终结果
		printf("%d", c[i]);
	return 0;
}

下面是一个高精度的例子

Input

Output

Sample Input

32 2

Sample Output

4

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
string s;
int m, k; int i, j; int a[205], aans[205], n[205], ans[205], last[205], now[205], t[205];
int single_j[12] = { 1,1,4,4,2,1,1,4,4,2 };//单循环结
void init() {
    memset(a, 0, sizeof a); memset(last, 0, sizeof last);
    memset(aans, 0, sizeof aans); memset(now, 0, sizeof now);
    memset(ans, 0, sizeof ans); memset(n, 0, sizeof n); memset(t, 0, sizeof t);
    //for (int i = 1;; i++) { if (m == 0) break; n[i] = m % 10; m /= 10; }//将m存入数组n，以便于高精度
}
void multiplyh(int x[], int y[], int z[]) {//高精度高乘
	for (int i = 1; i <= k; i++) {
		for (j = 1; j <= k; j++) {
			z[i + j-1]+= x[i] * y[j];
			z[i + j ] += (z[i + j-1] / 10);
			z[i + j-1] = z[i + j-1] % 10;
		}
	}
}
void multiplyl(int x[], int yy, int z[]) {//高精度低乘
    int up = 0;
    for (int ii = 1; ii <= k; ii++) {
        z[ii] = (x[ii] * yy + up) % 10;
        up = (x[ii] * yy + up) / 10;
    }
}
int main()
{
    //scanf("%d%d", &m, &k);
    init();
    cin >> s;
    cin >> k;
    int temp = 0, len = s.size();
    for (i = len - 1; i >= len - k; i--)
        n[++temp] = s[i] - '0';
    int tmp = 0;
    for (int i = 1; i <= k; i++) ans[i] = n[i];
    for (int i = 1; i < single_j[n[1]]; i++) {
        memset(aans, 0, sizeof(aans));
        multiplyh(ans, n, aans);
        for (int j = 1; j <= k; j++) { ans[j] = aans[j];}//更新为第一次出现末尾循环节的状态
    }
    t[1] = single_j[n[1]];//最低位的循环结
    for (int i = 1; i <= k; i++) now[i] = ans[i];
    int pos = 2;//当前倒数位数
    while (pos <= k) {
        for (int j = 1; j <= k; j++) {
            ans[j] = n[j];
            last[j] = now[j];
        }
        tmp = 0;
        while (tmp < 11) {
            tmp++;
            memset(aans, 0, sizeof aans);
            multiplyh(ans, now, aans);
            for (j = 1; j <= k; j++) {
                ans[j] = aans[j];
            }
            if (ans[pos] == n[pos]) break;//找到循环结
            memset(aans, 0, sizeof(aans));
            multiplyh(last, now, aans);//更新last
            for (j = 1; j <= k; j++) last[j] = aans[j];
        }
        if (tmp >= 11) { cout << -1; return 0; }
        for (int j = 1; j <= k; j++) now[j] = last[j];
        memset(aans, 0, sizeof aans);
        multiplyl(t, tmp, aans);//更新循环节数组
        for (int i = 1; i <= 100; i++)  t[i] = aans[i];
        pos++;
    }
    int flag = 0;//不输出前导0
    for (int i = 100; i >= 1; i--) {
        if (t[i]) flag = 1;
        if (flag) cout << t[i];
    }
    //cout << endl;
    return 0;
}