c++ - karatsuba乘法，递归问题

我正在尝试使用karatsuba技术实现大数的乘法。我陷入了段错误，无法解决。在3或4个级别的递归之后，该程序似乎总是退出。 sizeof(bint)返回20000。我的bint由一组短裤组成。

friend bint operator+ (const bint& lhs, const bint& rhs)
{
    // adding two big integers
}

bint ksuba(const bint& X, const bint& Y, int n)    // n is always a power of 2
{
    if (n == 4)
        return smul(X, Y);    // naive way of multiplying numbers

    bint a1, b1, a2, b2;
    bint x, y, z;

    int half = n/2;

    for (int i=0; i<half; i++)
    {
        a1.data[SIZE - n + i + half] = X.data[SIZE - n + i];
        a2.data[SIZE - n + i + half] = X.data[SIZE - n + i + half];

        b1.data[SIZE - n + i + half] = Y.data[SIZE - n + i];
        b2.data[SIZE - n + i + half] = Y.data[SIZE - n + i + half];
    }

    a1.idx = SIZE - half;
    b1.idx = SIZE - half;
    a2.idx = SIZE - half;
    b2.idx = SIZE - half;

    x = ksuba(a1, b1, half);
    y = ksuba(a2, b2, half);
    z = ksuba((a1+a2), (b1+b2), n) - x - y;

    x.lshift(n);
    z.lshift(half);

    return x + y + z;
}

使用gdb会产生以下错误-

Program received signal SIGSEGV, Segmentation fault.
0x00000000004018c2 in bint::ksuba (this=<error reading variable: Cannot access memory at address 0x7fffff7ea3a0>, X=<error reading variable: Cannot access memory at address 0x7fffff7ea398>,    Y=<error reading variable: Cannot access memory at address 0x7fffff7ea390>, n=<error reading variable: Cannot access memory at address 0x7fffff7ea38c>) at big.cpp:593
593                 bint ksuba(const bint& X, const bint& Y, int n)

我尝试减少了要声明的Bint变量的数量。具体来说，我通过将ksuba(a2，b2，half)的结果添加到x本身来摆脱y。但这并不能解决问题。有某种方法可以知道递归的每个步骤分配了多少内存？任何帮助将非常感激。

最佳答案

在每个级别上，您有7个显式声明的类型为bint的变量，另外2个隐式分配给ksuba((a1 + a2)，(b1 + b2)，n)的调用。所有这些都进入堆栈。那是180 KB。如果程序是在没有优化的情况下以 Debug模式构建的，则堆栈使用量可能会更大。

180 KB似乎不足以解释崩溃的原因，因为(假设这是Linux)默认情况下，您应该具有8 MB的堆栈，并且仅经过3或4次迭代就不会耗尽。但是，正如Dmitri所述，您可以尝试使用ulimit工具或通过链接时通过Wl，-stack = xxxxx选项指定它来增加堆栈大小。更好的是，不要将bint放在堆栈上。用new / delete动态分配它们，并且仅将指针保留在堆栈中。

关于c++ - karatsuba乘法，递归问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10859770/