5 Replies - 358 Views - Last Post: 30 October 2019 - 08:56 AM Rate Topic: -----

#1 robgeek   User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 193
  • Joined: 15-January 13

Segmentation fault: Trying to calculate sieve of eratosthenes.

Posted 29 October 2019 - 06:21 PM

Good evening!

I'm trying to get all prime numbers given a limit. The way I'm doing works fine until 4194304=2^22, but when I try to get all prime numbers until 8388608=2^23 I get the following error message.
#include <iostream>
#include <vector>
#include <cstring>

std::vector<int> eratostenes(int num) {
	bool primes[num];
	std::vector<int> nPrimes;

	memset(primes, true, sizeof(primes));

	for (int p = 2; (p * p) <= num; p++)
		if (primes[p] == true)
			for (int i = (p * 2); i < num; i += p)
				primes[i] = false;
		
	for (int p = 2; p < num; p++)
		if (primes[p])
			nPrimes.push_back(p);

	return nPrimes;
}

void calcPrimes(int num) {
	std::vector<int> lsprimes = eratostenes(num);	
	std::cout << "[ " << num << " ] Total of primes: " << lsprimes.size() << std::endl;	
}

int main(int argc, char *argv[]) {
	int num = std::stoi(argv[1]);

	calcPrimes(num);

	return 0;
}


Segmentation fault (core dumped)


What is happening and how can I fix this?

Is This A Good Question/Topic? 0
  • +

Replies To: Segmentation fault: Trying to calculate sieve of eratosthenes.

#2 jimblumberg   User is offline

  • member icon

Reputation: 5771
  • View blog
  • Posts: 17,672
  • Joined: 25-December 09

Re: Segmentation fault: Trying to calculate sieve of eratosthenes.

Posted 29 October 2019 - 08:45 PM

I can't repeat your stated problem, probably because the code fails to compile for me because Variable Length Arrays are not allowed in C++ (see line 6 for the location of the VLA).

How are you running the program, and what are you providing for the required input parameter?

Lastly run the program with your debugger, the debugger should be able to tell you the exact place where it detects the problem. You should then be able to view the contents of the various variables at the time of the crash.


Jim
Was This Post Helpful? 1
  • +
  • -

#3 Salem_c   User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 2397
  • View blog
  • Posts: 4,530
  • Joined: 30-May 10

Re: Segmentation fault: Trying to calculate sieve of eratosthenes.

Posted 29 October 2019 - 11:03 PM

> but when I try to get all prime numbers until 8388608=2^23 I get the following error message

> bool primes[num];
So num is that large number you type in then.

Well my friend, you just blew up your stack.
The default stack sizes on your average desktop OS vary from 1MB to 8MB.
Which means you can't just go round creating monster arrays without a care in the world.

So this is one way:
bool *primes = new bool[num];

///

delete [] primes;



This is a better way:
std::vector<bool> primes(num,true);  // no need for your memset




> memset(primes, true, sizeof(primes));
This is an awful hack, serving no purpose, but making a lot of assumptions.
Use a for loop to set each primes[i] = true;
Was This Post Helpful? 1
  • +
  • -

#4 robgeek   User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 193
  • Joined: 15-January 13

Re: Segmentation fault: Trying to calculate sieve of eratosthenes.

Posted 30 October 2019 - 08:32 AM

View Postjimblumberg, on 29 October 2019 - 08:45 PM, said:

How are you running the program, and what are you providing for the required input parameter?


[[email protected] ~]$ g++ -o primes main.cpp 
[[email protected] ~]$ ./primes 16777216
[ 16777216 ] Total of primes: 1077871


Is running fine now because I did what Salem_c suggested. I'm using std::vector instead of c style array.

But I have another question:
What if I try a real big number with many bytes long, like 18 bytes or bigger? How can I do that? Probably I'll have problems with the type(c++ does not have BigInteger like java), stoi(), size of std::vector that probably will not understand the size...
Was This Post Helpful? 0
  • +
  • -

#5 jimblumberg   User is offline

  • member icon

Reputation: 5771
  • View blog
  • Posts: 17,672
  • Joined: 25-December 09

Re: Segmentation fault: Trying to calculate sieve of eratosthenes.

Posted 30 October 2019 - 08:53 AM

Quote

Probably I'll have problems with the type(c++ does not have BigInteger like java),

True there is no standard BigInteger type, however with a little bit of searching you should be able to find an adequate implementation of a third party BigInterger type.

Quote

stoi()

Yea, if your string causes an overflow of the integer stoX() will probably throw an exception. Don't forget that there are other types, long, long long, for example. I would recommend you do a little validation of that command line parameter before you try to convert it to a number.

Quote

size of std::vector that probably will not understand the size

The std::vector can hold any type, even user defined types. It does however have a limitation on how many items can be held in the vector (size_t::max).

Jim
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7139
  • View blog
  • Posts: 24,247
  • Joined: 05-May 12

Re: Segmentation fault: Trying to calculate sieve of eratosthenes.

Posted 30 October 2019 - 08:56 AM

Yes, a typical C++ implementation will only support 4 or 8 byte unsigned integers to give you 232 or 264 as your largest integers. Beyond that you'll need to start pulling multiprecision libraries like GMP and its forks.

Did you mean 18 byte integer or 18 digit integer?

An 18 byte integer would be 218*8 == 2144. Do you even have that much memory available to you if you are planning on using the Sieve of Eratosthenes? And even if you had that much memory, you'll have to implement your own memory addressing scheme given that current 64-bit processors only let you access a 264 address space.

On the other hand, an 18 digit integer will fit into an 8 byte (aka 64-bit) integer. This is because log(1018) / log(2) ~= 60.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1