首先是一点背景：
- 我是第一次发帖，是大学学生（不是编程）。
- 这不是作业问题，我只是为了好玩。
- 我的编程经验包括一个学期（3 个月）的 C++ 和一些高中 QBasic。
- 是的，我看过 GMP 和 Bignum 库；从原始代码中学习东西是非常困难的，尤其是在不了解程序员的意图的情况下。此外，我想学习如何为自己做这件事。
我正在为任意大的整数编写乘法函数。我使用字符数组来表示这些数字，最后用 + 或 - 作为标记（例如“12345+”、“31415-”）。
我目前正在实施 Karatsuba 算法。问题在于，使用递归和动态内存分配，该函数比简单方法慢 5 倍。
我可以使用一些提示来减少运行时间。
char* dam(char* one, char* two){ // Karatsuba method
char* zero = intochar(0, 0);
int size_a = char_size(one) - 1;
int size_b = char_size(two) - 1;
if(compare(one, zero) == 0 || compare(two, zero) == 0)
return zero; // if either array is zero, product is zero
delete[] zero;
if(size_a < 4 && size_b < 4) // if both numbers are 3 digits or less, just return their product
return multiplication(one, two);
// is the product negative?
bool negative = one[size_a] == two[size_b]? false : true;
int digits = size_a > size_b ? size_a : size_b;
digits += digits & 1; // add one if digits is odd
int size = digits / 2 + 1; // half the digits plus sentinel
char* a, *b; // a and b represent one and two but with even digits
if(size_a != digits)
a = pad_char(one, digits - size_a); // pad the numbers with leading zeros so they have even digits
else
a = copy_char(one);
if(size_b != digits)
b = pad_char(two, digits - size_b);
else
b = copy_char(two);
char* a_left = new char[size]; // left half of number a
char* a_rite = new char[size]; // right half of number a
char* b_left = new char[size];
char* b_rite = new char[size];
memcpy(a_left, a, size - 1);
a_left[size - 1] = a[digits];
memcpy(a_rite, a + size - 1, size);
memcpy(b_left, b, size - 1);
b_left[size - 1] = b[digits];
memcpy(b_rite, b + size - 1, size);
delete[] a;
delete[] b;
char* p0 = dam(a_left, b_left); // Karatsuba product = p1*10^n + (p0+p2-p1)*10^(n/2) + p2
char* p2 = dam(a_rite, b_rite);
deduct(a_left, a_rite);
deduct(b_left, b_rite);
char* p1 = dam(a_left, b_left);
char* p3 = intochar(0, digits - 1); // p3 = p0 + p2 - p1
append(p3, p0); // append does naive addition
append(p3, p2);
deduct(p3, p1);
delete[] a_left;
delete[] a_rite;
delete[] b_left;
delete[] b_rite;
int sum_size = 2 * digits; // product of two numbers can have a maximum of n1 + n2 digits
char* sum = new char[sum_size + 1];
memset(sum, 0, sum_size);
if(negative)
sum[sum_size] = '-';
else
sum[sum_size] = '+';
char* left = extend_char(p0, digits, false); // extend returns a new array with trailing zeros
char* mid = extend_char(p3, size - 1, false);
append(sum, left);
append(sum, mid);
append(sum, p2);
delete[] p0;
delete[] p1;
delete[] p2;
delete[] p3;
delete[] left;
delete[] mid;
return sum;}