通常印象中的乘法：
位数增加时，许多编程语言中，往往连long_int类型都无法存储一定程度上的大整数
根据乘法算式的思想，将大整数分块计算，每个子运算都是一位数乘一位数，通过数组的形式输出到屏幕，可以做到所谓的大整数乘法
#include <iostream> #include <cstring> using namespace std; const int MAX_Length = 1000; void long_multiplication(int* res, int* num1, int* num2); void long_multiplication(int* res, int* num1, int* num2) { //num1[0]和num2[0]存储位数，这里res[0]取其加和，因为2位数乘2位数，最多4位数，99*99=9801 res[0] = num1[0] + num2[0]; //逐位相乘，想不明白搞个11*11，看一下121中的2是怎么来的 for (int i = 1; i <= num1[0]; i++) { for (int j = 1; j <= num2[0]; j++) { res[i + j] += num1[i] * num2[j]; } } //因为有res中有2位数，所以处理进位 for (int x = 1; x <= res[0]; x++) { if (res[x] < 10) { //小于10没有事了，让它跳出当前循环，继续走判断下一个res continue; } else { //让它的前一位加进位 res[x + 1] += res[x] / 10; //自身去模10 res[x] = res[x] % 10; //循环次数一定要等于大整数结果的长度，res[0]还要自加 x == res[0] && res[0]++; } } } int main(int argc, char** argv) { char str1[MAX_Length], str2[MAX_Length]; int num1[MAX_Length], num2[MAX_Length], res[MAX_Length] = { 0 }; //注意res数组需要初始化，否则结果可能不正确 cin >> str1; cout << "imput the 2" << endl; cin >> str2; //获取num1大数长度 num1[0] = strlen(str1); //倒着写入num1,2的数组 for (int i = 0; str1[i]; i++) { num1[num1[0] - i] = str1[i] - '0'; } //获取num1大数长度 num2[0] = strlen(str2); for (int i = 0; str2[i]; i++) { num2[num2[0] - i] = str2[i] - '0'; } long_multiplication(res, num1, num2); for (int i = res[0]; i >=2; i--) { //第0位用来保存长度，第一位并没有使用 std::cout << res[i]; } cout << endl; return 0; }这种算法的时间复杂度是n^2量级的，有没有一种方法能在保证解决大整数乘法情况下，适当降低时间复杂度
根据分治法的思想，将一个大问题，转换为多个子问题，然后将比较容易操作的子问题得出结果，再次合并，得到原问题的结果
对于大整数乘法，我们同样采取这样的思想
当子问题中的算式分裂到个位数乘个位数，求和合并，这实际上与分块算式乘法很类似，实际上根据分治的思想，每次都是将大整数一分为二，每一部分乘属于它的数量级。
A*B = （A1+A2）*（B1+B2） = （A11+A12）*（A21+A22）*（B11+B12）*（B21+B22）=.........
根据该逻辑，推测时间复杂度为log2N的数量级
为了代码和思路的简洁性，采用递归程序
#include <cstdio> #include <cmath> /*递归思想 * 对X = 1234 和 Y = 5678来分析： divideConquer（1234， 5678， 4） ———————————————————————— X=1234 | A=12 | B=34 | A-B=-22 Y=5678 | C=56 | D=78 | D-C=22 三次递归： AC = divideConquer（12， 56， 2） BD = divideConquer（34， 78， 2） (A-B)(D-C) = divideConquer（-22， 22， 2） AC递归 ———————————————————————— X=12 | A1=1 | B1=2 | A1-B1=-1 Y=56 | C1=5 | D1=6 | D1-C1=1 A1*C1 = divideConquer（1， 5， 1） = 5 B1*D1 = divideConquer（2， 6， 1） = 12 （A1-B1） * （D1-C1） = divideConquer（-1， 1， 1） = -1； 所以AC递归求得的值为：5 * 10 ^ 2 + （-1 + 5 + 12）* 10 + 12 = 672 同理可得 BD = 2652 和 (A-B)(D-C) = -484 最终可得 X * Y = 7006652 */ using namespace std; int long_multiplication(int* x, int* y, int len) { if (*x == 0 || *y == 0) { return 0; } else if(len == 1){ return(*x) * (*y); } else { int A_F = (int)*x / pow(10, (int)len / 2);//A大整数的第一部分 int A_S = *x - A_F * pow(10,(int)len /2);//A大整数的第二部分（分界点n/2） int B_F = (int)*y / pow(10, (int)len / 2);//B大整数的第一部分 int B_S = *y - B_F * pow(10, (int)len / 2);//B大整数的第二部分 int A_FmulB_F = long_multiplication(&A_F, &B_F, len / 2);//第一部分与第一部分相乘 int A_SmulB_S = long_multiplication(&A_S, &B_S, len / 2);//第二部分与第二部分相乘 //A1-B1 int temp1 = A_F - A_S; //B2-B1 int temp2 = B_S - B_F; int ALL_AB = long_multiplication(&temp1, &temp2, len / 2) + A_FmulB_F + A_SmulB_S; //AC * pow(10 , n) + ABDC * pow(10, (int)(n / 2)) + BD return A_FmulB_F * pow(10, len) + ALL_AB * pow(10, (int)(len / 2)) + A_SmulB_S; } } int main(int argc, char** argv[]) { int A; int B; A = 1234; B = 5678; printf("%d", long_multiplication(&A, &B, 4)); }
