3

カラツバ法を使って大きな数の乗算を実装しようとしています。回避できないセグメンテーション違反で立ち往生しています。プログラムは、3または4レベルの再帰の後、常にドロップアウトしているようです。sizeof（bint）は20000を返します。私のbintはshortの配列で構成されています。

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

各レベルで、bint型の7つの明示的に宣言された変数があり、さらに2つがksuba（（a1 + a2）、（b1 + b2）、n）の呼び出しに暗黙的に割り当てられます。それらはすべてスタックに入ります。それは180KBです。プログラムが最適化なしでデバッグモードでビルドされている場合、スタックの使用量が大きくなる可能性があります。

180 KBは、クラッシュを説明するのに十分ではないようです。これは、（これがLinuxであると仮定すると）デフォルトで8 MBのスタックが必要であり、3〜4回の反復で不足することはないためです。ただし、Dmitriが言及しているように、ulimitツールを使用するか、リンク時にWl、-stack = xxxxxオプションを使用して指定することにより、スタックサイズを増やすことができます。さらに良いことに、スタックにビントを置かないでください。それらをnew/deleteで動的に割り当て、ポインタのみをスタックに保持します。

于 2012-06-02T05:14:15.807 に答える