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

Question

我正在尝试使用 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 。但这并没有解决问题。有没有办法知道在递归的每一步分配了多少内存？非常感谢任何帮助。

Answer 1

在每个级别，您有 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 动态分配它们，并且只将指针保留在堆栈上。