先介绍一下背景:
- 我是第一次发布海报，是一名大学学生(不是编程专业)。
- 这不是作业题，我只是为了好玩才这样做。
- 我的编程经验包括一个学期(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;}

最佳答案

Karatsuba 是一个很好的算法，并且不太难编程。如果您只是为了好玩，那么以 10 为基数工作甚至不是一个坏主意——它会极大地减慢您的速度，但它也会减慢原始实现的速度，因此您仍然有一个比较这两种方法的基础。

但是，您绝对必须放弃在递归树的每个节点动态分配和释放工作空间的想法。你只是买不起。您必须在计算开始时分配所需的工作空间，并智能地处理您的指针，以便树的每一层都能获得所需的工作空间，而无需分配它。

此外，在每个级别测试负面产品是没有意义的。只需在顶层执行此操作，并在计算期间专门使用正数。

不是说它与你的问题相关，而是每当我看到类似的东西时

bool negative = one[size_a] == two[size_b]? false : true;

我的心微微一缩。想想所有那些浪费的像素!我恭敬地建议:

bool negative = one[size_a] != two[size_b] ;

关于c++ - 需要帮助在 C++ 中实现 Karatsuba 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7985883/