3

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

4

1 回答 1

1

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

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

于 2012-06-02T05:14:15.807 回答