CODEWITHSUNDEEP
c++segmentation-fault
user3743746
user3743746

Reputation: 1

Segmentation fault (core dumped) only bigger input

My code works perfectly if the seive(n) is 1000000. If seive(n) is more than 10000000, it shows me segmentation fault (core dumped).I've read about segmentation fault. But i couldn't solve with that.

    #include <stdio.h>
    #include <math.h>

    using namespace std;


    int seive(long int n)
    {
        long int A[n];

        for (long int i = 2; i <= n; i += 1)
        {
            A[i] = i;
        }
        long int root = (int)sqrt(n);

        for(int j = 2; j <= root; j++)
        {

            for(int k = 2*j; k < n ; k = k + j)
            {       
                A[k] = 0;
            }
        }
        int count = 0;
        for (int l = 2; l < n; ++l)
        {
            if(A[l] != 0) count++;
        }
        printf("%d\n", count);

    }

    int main()
    {
        seive( 1000000);
    }

Upvotes: 0

Views: 1829

Answers (3)

WhozCraig
WhozCraig

Reputation: 66194

Your automatic storage space is being taxed beyond its limits on your platform for a number of reasons.

First, each element is needlessly 63 bits larger than it needs to be, assuming your platform unsigned long int is 64bit. A sieve normally needs to represent only one of two values "true" or "false". A array of bool would suffice for this with some minor tweaking to your algorithm.

Second, though the first item is important, it isn't the dominant factor in the size of your array. That privilege belongs to n, the top-limit on your quest. Your requesting a significant amount of space in automatic storage. Assuming you addressed the first and the representation of bool on your platform ere a single byte, A flags-array of 10000000 entries would still require approx. 9.54 MB of automatic storage which is no laughing matter.

The solution is dynamic storage, and can be accomplished a number of ways, some of which are:

  • Use malloc(sizeof(bool)*(n+1)) (discouraged in modern C++ programs)
  • Use new bool[n+1]] (better, but still not great)
  • Use an RAII container like std::vector<bool> (now we're getting somewhere)

A very simple thrown-together sieve example that employs the above appears below. You can improve on this significantly with optimized logic regarding even numbers (no need to even keep them), etc. But that isn't the point. The point is using dynamic storage, preferably something with automatic lifetime, which std::vector<> does for you nicely.

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>

unsigned long int sieve(unsigned long int N)
{
    std::vector<bool> vec(N+1,true);
    unsigned long int res = 1;
    const unsigned long int SR = std::floor(std::sqrtl(static_cast<long double>(N)));

    for (unsigned long int i=2; i<=SR; ++i)
    {
        if (vec[i])
        {
            ++res;
            for (unsigned long int j=(i << 1); j<=N; j+=i)
                vec[j] = false;
        }
    }

    for (unsigned long int i=SR+1; i<=N; ++i)
    {
        if (vec[i])
            ++res;
    }
    return res;
}

int main()
{
    std::cout << sieve(10000000) << '\n';
    return 0;
}

Output

664580

which I believe is correct unless you're of the kind that disregards 1 (some do, dunno why), in which case it's off by one.

Upvotes: 2

Namit Sinha
Namit Sinha

Reputation: 1445

What you are trying to do is trying to allocate an array with large number of elements on stack (stack memory) 

long int A[n];

In general you will be able to allocate a larger array on heap using 

int *A = new int[n]

Upvotes: 2

dascandy
dascandy

Reputation: 7292

long int A[n];

This is an array on the stack. It is really big, if N is big. Your stack is not big enough to hold it in those cases and you will get a stack overflow error.

Solutions include:

Dynamically allocating memory: long int *A = (long int *)malloc(n*sizeof(long int));

Dynamically allocating memory C++ style: long int *A = new long int[n];

Using a statically allocated buffer (that's not on the stack, then): static long int A[n];

Making it global: move that line up 3 lines.

Upvotes: 3

Related Questions