C++ Array Allocation Segmentation Fault 11 Newbie

Question

I am learning C++ from Algorithms in C++ by Robert Sedgewick. Right now I am working on the Sieve of Eratosthenes with a user specified upper bound on the largest prime. When I run the code with max 46349, it runs and prints out all primes up to 46349, however when I run the code with max 46350, a Segmentation fault occurs. Can someone help to explain why?

./sieve.exe 46349
 2 3 5 7 11 13 17 19 23 29 31 ...

./sieve.exe 46350
 Segmentation fault: 11

Code:

#include<iostream>

using namespace std;

static const int N = 1000;

int main(int argc, char *argv[]) {
    int i, M;

    //parse argument as integer
    if( argv[1] ) {
        M = atoi(argv[1]);
    }

    if( not M ) {
        M = N;
    }

    //allocate memory to the array
    int *a = new int[M];

    //are we out of memory?
    if( a == 0 ) {
        cout << "Out of memory" << endl;
        return 0;
    }

    // set every number to be prime
    for( i = 2; i < M; i++) {
        a[i] = 1;
    }

    for( i = 2; i < M; i++ ) {
        //if i is prime
        if( a[i] ) {
            //mark its multiples as non-prime
            for( int j = i; j * i < M; j++ ) {
                a[i * j] = 0;
            }
        }
    }

    for( i = 2; i < M; i++ ) {
        if( a[i] ) {
            cout << " " << i;
        }    
    }
    cout << endl;

    return 0;
}

A segmentation fault is typically caused by writing beyond the bounds of allocated memory. You should use the debugger (or add print statements) to track the progress of your program, in order to find out at what point this occurs. — Oliver Charlesworth, Mar 02 '13 at 17:00
Note that `new` will not return `NULL` if allocation fails (unless `nothrow` is specified, which it isn't here). It will throw a `std::bad_alloc` exception. — Cornstalks, Mar 02 '13 at 17:00

NPE · Answer 1 · 2013-03-02T17:08:16.440

5

You have integer overflow here:

        for( int j = i; j * i < M; j++ ) {
            a[i * j] = 0;
        }

46349 * 46349 does not fit in an int.

On my machine, changing the type of j to long makes it possible to run the program for larger inputs:

    for( long j = i; j * i < M; j++ ) {

Depending on your compiler and architecture, you may have to use long long to get the same effect.

edited Mar 02 '13 at 17:08

answered Mar 02 '13 at 17:01

NPE

486,780
108
951
1,012

Olaf Dietsche · Answer 2 · 2013-03-03T01:57:54.793

3

When you run your program with a debugger, you will see that it fails at

a[i * j] = 0;

i * j overflows and becomes negative. This negative number is less than M, that's why it enters the loop once more and then fails on access to a[-2146737495].

edited Mar 03 '13 at 01:57

answered Mar 02 '13 at 17:05

Olaf Dietsche

72,253
8
102
198

Being pedantic, and I'm sure *you* know this, but it technically doesn't have to be -2146737495. – chris Mar 02 '13 at 17:09
@chris This is just cut and paste from gdb. – Olaf Dietsche Mar 02 '13 at 17:16

score 1 · Answer 3 · answered Mar 02 '13 at 17:01

1

I see, the problem was declaring M as an int. When I declare i,M and j as long, this seems to work fine.

answered Mar 02 '13 at 17:01

David Williams

8,388
23
83
171

1

I wouldn't count on `long` to do this. `long` is at least 32 bits, and any implementation in which it is 32 will cause overflow. `long long` is at least 64, though, and it's officially part of C++11. There might then be a problem with speed if the processor is 32-bit and dealing a lot with 64-bit numbers, but I wouldn't know even close to how much of a difference that would make until I had times. – chris Mar 02 '13 at 17:03
As `NPE` says, if `int` is 32 bits, then `i * j` will overflow and bad things (like crashes) can happen. Making it `long` will work if `long` has more bits, which for you and your compiler, it's possible `long` is 64 bits so that `i * j` no longer overflows. – Cornstalks Mar 02 '13 at 17:05

score 1 · Answer 4 · answered Mar 02 '13 at 17:01

1

In any reasonably modern C++, you will not get a null pointer back from new if the allocation fails unless you use a non-throwing new. That part of your code isn't going to work as you expect it to - you'll have to catch std::bad_alloc that might be emitted from the call to new instead.

You also want to declare your array indices as type size_t.

answered Mar 02 '13 at 17:01

Timo Geusch

24,095
5
52
70

Would you recommend any learning materials about this? I'm totally new to this language and havent yet been exposed to memory management. – David Williams Mar 02 '13 at 17:07
2

@DavidWilliams, A [good book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) is always a good start. Keep in mind that modern C++ is not about memory management so much as RAII, where you *don't* have to manage it. – chris Mar 02 '13 at 17:10

C++ Array Allocation Segmentation Fault 11 Newbie

4 Answers4

Linked