大整数相乘问题--分而治之

// int_multifly.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include<iostream> #include<string> #include<algorithm> using namespace std; int p[350], q[350], r0[500]; string s1, s2; int n; /// <summary> /// /// 整数求和 /// </summary> void d_add(int p[], int q[], int c[], int n) { int i, c1 = 0; for (i = n - 1; i >= 0; i--) { c[i] = p[i] + q[i] + c1; if (c[i] >= 10 && i > 0) { c[i] = c[i] - 10; c1 = 1; } else { c1 = 0; } } } /// <summary> /// 当系数只有两项时，直接计算乘积 /// </summary> void d_product(int p[], int q[], int c[]) { int t1, t2, r[4] = { 0,0,0,0 }; t1 = p[0] * q[0]; c[1] = t1 % 10; c[0] = t1 / 10; t2 = p[1] * q[1]; c[3] = t2 % 10; c[2] = t2 / 10; r[1] = (p[0] + p[1]) * (q[0] + q[1]) - t1 - t2; r[2] = r[1] % 10; r[1] = r[1] / 10; d_add(c, r, c, 4); } /// <summary> /// /// 整数作差，存储到p[]中 /// </summary> void d_minus(int p[], int q[], int n) { //在这个问题中，最高位不会发生结尾情况，即各自独立，因此略去更多代码 int i, c1 = 0; for (int i = n - 1; i >= 0; i--) { p[i] = p[i] - q[i] + c1; if (p[i] < 0 && i > 0) { p[i] = p[i] + 10; c1 = -1; } else { c1 = 0; } } } /// <summary> /// 递归求解两个n位大整数的乘积 /// /// </summary> void integer_product(int p[], int q[], int r0[], int n) { int m; int* r1, * r2, * r3, * r4; r1 = new int[2 * n]; r2 = new int[2 * n]; r3 = new int[2 * n]; r4 = new int[2 * n]; for (int i = 0; i < 2 * n; i++) { r0[i] = r1[i] = r2[i] = r3[i] = r4[i] = 0; } ////--------------------------------------------- //核心的几行代码 if (n == 2) { d_product(p, q, r0); } else { m = n / 2; integer_product(p, q, r0, m);//递归求解get r0 integer_product(p + m, q + m, r1 + 2 * m, m);////递归求解get r1 d_add(p, p + m, r3, m); d_add(q, q + m, r4, m); integer_product(r3, r4, r2 + m, m);//递归求解get r2 d_minus(r2 + m, r0, 2 * m); d_minus(r2 + m, r1 + 2 * m, 2 * m); //combine d_add(r0, r2, r0, 4 * m); d_add(r0, r1, r0, 4 * m); } delete r1; delete r2; delete r3; delete r4; } /// <summary> /// /// 显示因子或乘积的结果 /// </summary> void display(int p[], int n) { int i, k = 0; int work = 0; for (i = 0; i < n; i++) { if (p[i] == 0 && work == 0) { continue; } work = 1; k++; printf("%d,", p[i]); if (k % 30 == 0) { printf("\n"); } } } /// <summary> /// /// 将输入的数据从字符串形式转换到整数形式，并将其补位到2的n次幂 /// </summary> void translate_Bigint(string s, int* p) { //可以修缮一下去掉空格制表符等无效字符 int length = s.length(); int d = 0; int k = 0; //ascii coding //补位成2^n double a = ceil(log2(n)); n = pow(2, a); d = n - length; for (int i = 0; i < length; i++) { while (k < d) { p[k] = 0; k++; } p[d + i] = s[i] - '0';//前d个补成0 } } /// <summary> /// /// 该函数用于自行输入两个n位的数据，存储到程序中并输出乘积 /// </summary> void Input() { printf("input digits of the number:"); scanf_s("%d", &n); printf("input the first number:"); cin >> s1; printf("input the second number:"); cin >> s2; translate_Bigint(s1, p); display(p, n); translate_Bigint(s2, q); display(q, n); system("pause"); printf("multiplying...\n"); integer_product(p, q, r0, n); } /// <summary> /// 利用pi和e的数据，测试pi和e的前n位（n<=100）,便于测试程序 /// /// </summary> void test100() {/// printf("input digits of the number(<=100):"); scanf_s("%d", &n); s1 = "2718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427"; s2 = "3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067"; //正确结果是 //8539734222673567065463550869546574495034888535765114961879601130179228611157330807572563869710473939901094369536683817066038723816482458453336694578829100848854360647354195452748194129920598692109609 translate_Bigint(s1, p); printf("因子:\n"); display(p, n); printf("\n"); translate_Bigint(s2, q); printf("因子:\n"); display(q, n); //system("pause"); printf("multiplying...\n"); integer_product(p, q, r0, n); } int main() { while (true) { //Input();//完全可以利用程序汇总封装的e和pi的前n位来测试如想自行输入数据，取消改行注释并注释掉下一行 test100(); printf("乘积为\n"); display(r0, 2 * n); printf("\n----------------------------------\n"); } }