0

割り当ての一部として、Strassenの行列乗算アルゴリズムを実装しています。正しくコーディングしましたが、セグメンテーション違反が発生している理由がわかりません。私はstrassen（）をstrassen（0、n、0、n）;と呼んでいます。主に。nは、ユーザーが指定した2の累乗の数値であり、行列（2D配列）の最大サイズです。n = 4の場合はセグメンテーション違反を発生させませんが、n=8,16,32の場合はセグメンテーション違反を発生させます。コードは以下の通りです。

    void strassen(int p, int q, int r, int s)
    {
        int p1,p2,p3,p4,p5,p6,p7;   
        if(((q-p) == 2)&&((s-r) == 2))
        {
            p1 = ((a[p][r] + a[p+1][r+1])*(b[p][r] + b[p+1][r+1]));
            p2 = ((a[p+1][r] + a[p+1][r+1])*b[p][r]);
            p3 = (a[p][r]*(b[p][r+1] - b[p+1][r+1]));
            p4 = (a[p+1][r+1]*(b[p+1][r] - b[p][r]));
            p5 = ((a[p][r] + a[p][r+1])*b[p+1][r+1]);
            p6 = ((a[p+1][r] - a[p][r])*(b[p][r] +b[p][r+1]));
            p7 = ((a[p][r+1] - a[p+1][r+1])*(b[p+1][r] + b[p+1][r+1]));
            c[p][r] = p1 + p4 - p5 + p7;
            c[p][r+1] = p3 + p5;
            c[p+1][r] = p2 + p4;
            c[p+1][r+1] = p1 + p3 - p2 + p6;
        }
        else
        {
            strassen(p, q/2, r, s/2);
            strassen(p, q/2, s/2, s);
            strassen(q/2, q, r, s/2);
            strassen(q/2, q, s/2, s);
        }
    }
4

2 に答える 2

2

else ブロックの条件の一部は、無限に再帰的です (少なくとも 2 番目と 4 番目は、他をチェックしませんでした)。これは紙とペンで簡単に証明でき
strassen(p, q/2, s/2, s)ます。

1) 0, 4, 4, 8

2) 0, 2, 4, 8

3) 0, 1, 4, 8

4) 0, 0, 4, 8

5) 0, 0, 4, 8

...

これらの結果はどれもあなたの

if(((q-p) == 2)&&((s-r) == 2))

テストすると、スタックの最後に達するまで関数が実行され (4 番目の関数にも同じ問題があるため、分岐が疑われます...)、セグメンテーション フォールトが発生します。

とにかく、elseブロックで行おうとしているのが行列を再帰的に 2 等分することである場合、より良い試みは次のようになります。

strassen(p, (q+p)/2, r, (r+s)/2);                                               
strassen(p, (q+p)/2, (r+s)/2, s);                                               
strassen((q+p)/2,q, (r+s)/2, s);                                                
strassen((q+p)/2,q, r, (r+s)/2);

（ただし、このコードをチェックしていないことに注意してください）

于 2013-03-16T16:39:37.627 に答える
0 
void strassen(int p, int q, int r, int s)
{
    int p1,p2,p3,p4,p5,p6,p7;   
    if(q-p == 2 && s-r == 2)
    {
        p1 = (a[p][r] + a[p+1][r+1])   * (b[p][r] + b[p+1][r+1]);
        p2 = (a[p+1][r] + a[p+1][r+1]) * b[p][r];
        p3 = a[p][r]                   * (b[p][r+1] - b[p+1][r+1]);
        p4 = a[p+1][r+1]               * (b[p+1][r] - b[p][r]);
        p5 = (a[p][r] + a[p][r+1])     * b[p+1][r+1];
        p6 = (a[p+1][r] - a[p][r])     * (b[p][r] +b[p][r+1] );
        p7 = (a[p][r+1] - a[p+1][r+1]) * (b[p+1][r] + b[p+1][r+1]);
        c[p][r] = p1 + p4 - p5 + p7;
        c[p][r+1] = p3 + p5;
        c[p+1][r] = p2 + p4;
        c[p+1][r+1] = p1 + p3 - p2 + p6;
    }
    else
    {
        if (q/2-p >= 2 && s/2-r >= 2) strassen(p, q/2, r, s/2);
        if (q/2-p >= 2 && s-s/2 >= 2) strassen(p, q/2, s/2, s);
        if (q-q/2 >= 2 && s/2-r >= 2) strassen(q/2, q, r, s/2);
        if (q-q/2 >= 2 && s-s/2 >= 2) strassen(q/2, q, s/2, s);
    }
}

しかし、より簡単な再帰ストッパーは、次のように関数の先頭にあります。

{
    int p1,p2,p3,p4,p5,p6,p7;   
    if(q-p < 2 || s-r < 2) return;
    if(q-p == 2 && s-r == 2)
    { ...
于 2013-03-16T16:48:45.607 に答える