How to deal with this segmentation fault in C++?

Question

I need to calculate factorial of a number mod a large prime number. My program works up to some values but, it fails (segmentation fault) when I reach a higher value like the one mentioned in the program.

How can I make this program work?

Thanks a lot

#define LL unsigned long long
#define ull unsigned long long

const LL mod=1000000009;

LL arr[1048580];

inline ull mulMod(ull a,ull b,ull c)
{
    if(a<=1000000000ULL && b<=1000000000ULL)
    {
        //cout<<((a%c)*(b%c))%c<<endl;
        ull ret = ((a%c)*(b%c))%c;
        return ret;
    }
    ull ret = 0ULL; a=a%c;

    while(b > 0ULL)
    {
        if(b&1ULL) ret = ((ret%c)+(a%c))%c;
        a = (a<<1ULL)%c;
        b>>=1ULL;
    }
    return ret%c;
}

LL fact(LL num)
{
    if(arr[num]==0)
    {
        arr[num]=mulMod(num,fact(num-1),mod);
        return arr[num];
    }
    return arr[num];
}


int main()
{
    arr[0]=1;
    cout<<fact(325720);

}

Since `fact(n)` recursively calls `fact(n-1)`, By calling `fact(325720)` you are asking the system for a call stack of size 325720. This is not going to work. It's just too big. — Daniel Daranas, Mar 07 '14 at 16:38
Why do you use `#define` for type aliases (horrible idea!) and why do you have two different names for the same thing? — Sebastian Redl, Mar 07 '14 at 16:59

Tom Fenech · Answer 1 · 2014-03-07T16:49:40.500

3

You have a Stack Overflow!

The segfault occurs from the recursive calling of mulMod().

If you want to make it work for large numbers, you should probably avoid recursion. A simple for loop implementation:

LL fact2(LL num)
{
    int i;
    for (i = 1; i < num; ++i) {
        arr[num] = mulMod(num,arr[num-1],mod);
    }
    return arr[num];
}

edited Mar 07 '14 at 16:49

answered Mar 07 '14 at 16:39

Tom Fenech

72,334
12
107
141

score 1 · Answer 2 · edited May 23 '17 at 12:03

You can:

move the threshold at which it fails by asking your operating system loader to arrange a more generous stack size limit (e.g. try the ulimit command from Linux/Unix shells - see here), or
rewrite your algorithm or change compiler optimisation options so that it achieves tail recursion optimisation (if you find that possible with your particular algorithm and compiler), or
write an iterative solution that uses for/while instead of recursion.

score 0 · Answer 3 · answered Mar 07 '14 at 17:26

You have three key problems with your code. The obvious one is the stack overflow that you hit. Another is that you are invoking undefined behavior by not populating your array. The third is that you will invoke undefined behavior if you call function fact with a number greater than or equal to 1048580.

It will help to fix the last two issues by keeping track of the array size and the last element that has been set.

const LL arr_size = 1048580;
LL last_arr = 0;
LL arr[arr_size] = {1,0};

The stack overflow problem results from the recursive (non-tail recursive) call to fact. This can be made into a loop. Note that I'm also protecting against numbers that exceed your array size.

LL fact(LL num)
{   
    if (num >= arr_size) {
        LL result = fact(arr_size-1);
        for (LL ii = arr_size; ii <= num; ++ii) {
            result = mulMod(ii,result,mod);
        }   
        return result;
    }   

    if (num > last_arr) {
        for (LL ii = last_arr+1; ii <= num; ++ii) {
            arr[ii] = mulMod(ii,arr[ii-1],mod);
        } 
        last_arr = num;  
    }   

    return arr[num];
}

Note: This is a straightforward transcription of the recursive definition to an iterative one. There are ways to do this more efficiently.

How to deal with this segmentation fault in C++?

3 Answers3