-1

我了解了 Karatsuba 算法，它允许我使用分治法将非常大的数字相乘。

这是我的代码。我编写了一个返回数字长度的函数，然后编写了乘法函数，并使用了该方法进行了 4 次递归调用。

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int numberLength(long long value) {
    int counter = 0;
    while (value != 0)
    {
        counter++;
        value /= 10;
    }
    return counter;
}

long long multiply(long x, long y) {
    int xLength = numberLength(x);
    int yLength = numberLength(y);

    int n = max(xLength, yLength);

    if (n < 10) {
        return x*y;
    }

    long multiplier = pow(10, n/2);
    long xS = x/multiplier;
    long xD = x - (xS * multiplier);
    long yS = y/multiplier;
    long yD = y - (yS * multiplier);

    return multiply(xS,yS*pow(10,n)) + multiply(xS,yD*pow(10,n/2)) + multiply(xD,yS*pow(10,n/2)) + multiply(xD,yD);

}

问题是，如果我用一些长度大于 10 的数字调用函数 multiply() ，那么我会收到错误分段错误。问题出在哪里？

4

1 回答 1

1

您将违反堆栈限制，这将导致递归multiply()函数中长度> = 10的数字的堆栈溢出。我尝试了这个驱动程序函数

multiply(123456789, 1234567891);

并用-fsanitize=address. 这是输出：

==1==ERROR: AddressSanitizer: stack-overflow on address 0x7fffe22e9fb8 (pc 0x0000004fb85d bp 0x7fffe22ea050 sp 0x7fffe22e9f00 T0)

另外，尝试编译您的程序以-fsanitize=undefined查看逻辑中的其他错误，其中一个是

if (n < 10) {
    return x*y;
}

传入multiply(123456789, 1234567891)将导致溢出，因为该值无法容纳在 a long（通常为 32 位）中。将其更改为：

if (n < 10) {
    return (long long)x*y;
}
于 2021-04-20T00:12:12.410 回答