CODEWITHSUNDEEP
csegmentation-fault
Shreyas Kale
Shreyas Kale

Reputation: 65

Segmentation fault in a recursive function

I am implementing Strassen's matrix multiplication algorithm as a part of an assignment. I have coded it correctly but I don't know why it is giving segmentation fault. I have called strassen() as strassen(0,n,0,n); in main. n is a number given by user which is power of two and it is the maximum size of the matrix (2D Array). It is not giving segfault for n=4 but for n=8,16,32, it is giving segfaults. Code is as given below.

    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);
        }
    }

Upvotes: 0

Views: 912

Answers (2)

Rick77
Rick77

Reputation: 3211

Some of the conditions in your else block are infinitely recursive (at least the second and the fourth, didn't checked the other). This can be easily proved with pen and paper: e.g.
strassen(p, q/2, s/2, s) for `0,8,0,8 will yield at each iteration:

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

...

and since none of those results pass your 

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

test, the function will run (and I suspect branch, as the 4th function has the same problem...) until the end of the stack is hit, causing a Segmentation Fault.

Anyway, if what you are trying to do in the else block is to recursively bisect the matrix, a better attempt would be something like:

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);

(keep in mind that I didn't check this code, though)

Upvotes: 2

wildplasser
wildplasser

Reputation: 44240

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);
    }
}

But an easier recursion stopper would be at the beginning of the function, like:

{
    int p1,p2,p3,p4,p5,p6,p7;   
    if(q-p < 2 || s-r < 2) return;
    if(q-p == 2 && s-r == 2)
    { ...

Upvotes: 0

Related Questions