Segmentation fault in a recursive function

Question

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

Most likely the termination-condition is not correct, and the function recurses until it overflows the stack. You should at least check what happens when running in a debugger. If the debugger stops at one of the assignments to the `c` array, check the indexes so they are not out of bounds. — Some programmer dude, Mar 16 '13 at 16:22
Don't leave us guessing. What's the cause of the segfault, a stack overflow or overruning the array bounds? Whack it in gdb and provide more information. — Nicholas Wilson, Mar 16 '13 at 16:24
You can also try and place the `int` declarations inside the first `if`. Although I think Joachim is correct. Are you sure the conditions are `==` and not `<=`? Say `p` and `q` are 10 and 10. Then we have (10,10) (10,5) (10,2) (10,1) (10,0) ... — artless noise, Mar 16 '13 at 16:25
I would start by removing the unneeded parentheses and add some whitespace around the operators. The recursion does not stop if `if(q-p < 2 && s-r < 2)` It should stop. — wildplasser, Mar 16 '13 at 16:26
Where are `a`, `b`, and `c` coming from? I guess they are globals and the parameters are the array dimensions. Please consider editing your question to clarify this. Not everyone maybe familiar with *Strassen's matrix multiplication algorithm*. Providing a link would be helpful. — artless noise, Mar 16 '13 at 16:31
a[] and b[] are the matrices [2D arrays] to be multiplied. c[] is the result of the multiplication. They are globals and I am doing some computation on a and b to get c. I'm not much familiar with gdb, I'll use it with a cheatsheet and come up with something if it is not solved. — Shreyas Kale, Mar 16 '13 at 16:38
See also: http://stackoverflow.com/questions/13559928/why-is-my-strassens-matrix-multiplication-slow — artless noise, Mar 17 '13 at 14:08

score 2 · Accepted Answer · edited Mar 16 '13 at 17:54

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)

Thanks, I will again try and look over it with pen n paper and gdb too. — Shreyas Kale, Mar 16 '13 at 16:43
Please, should my answer satisfy you question, don't forget to mark it as the solution ;-) — Rick77, Mar 17 '13 at 10:36

wildplasser · Answer 2 · 2013-03-16T16:56:56.093

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)
    { ...

Segmentation fault in a recursive function

2 Answers2