c++ problem

[imperialrage15]

Hello, I'm a complete noob to c++ programming. Anyway, for practice, I was working on a program to find prime numbers. I have it storing all the primes in an array. It's also set up to record how long the program takes. I set it to 10,000 primes, it took .3 seconds. 100,000 primes, 4 seconds. So why not try 1 million? Might be a good way to benchmark my computers, like the program that finds pi to a million digits. Well, it crashes if I try a million. I tried some various other numbers, pretty much anything above 250,000 crashes it. Why? I mean, its 4 bytes per number, so 1 million digits would only be 4mb of ram needed. I have 512.

So is there some kind of limit or what? And is there an easy way around this?

[rock]

How does it crash? My first guess would be a memory leak of some kind.

What algorithm are you using? A good seive should get all the primes under a million in a second or so. My version using an interpreted 4GL returns in about 2-3 seconds.

BTW, there are 78,498 primes under 1,000,000 and the last one is 999,983.


EDIT: I misread your post a little. Looking for a million primes, not primes under a million, which is what mine does.

[imperialrage15]

It crashes as soon as the program starts. A box pops up, if I hit debug, it says something along the lines of "Unhandled exception: Stack overflow." I guess it's trying to use too much memory, even though it's only using 4mb. There must be some way to use more memory, but I don't know how.

[rock]

malloc (http://www.cplusplus.com/ref/cstdlib/malloc.html)

[Malone]

Quick and dirty C++ memory tutorial:

There are two areas of memory you can work with in C++, the stack and the heap.

The stack is where all your local variables reside (and probably global variables too, I can't remember). for instance


void myFunction()
{
int num_1 = 0;
int num_2 = 2;
float num_3 = 3.5f;
std::string name = "Bubba";

/*
...
*/
}


The stack begins at a certain memory address and grows downward. Whenever you call a function, space is allocated on the stack for that function's variables. If you call a funtion, that calls a function, that calls a function, that calls a funtion, then you have four functions taking up stack space. However, the stack has a limited size, determined by the operating system, and your program will crash if it tries to exceed that size limit. So, for instance, if you try to allocate an array to hold 1 million integers on the stack, depending on the operating system and the current state of the stack, your program might crash.



Fortunately, C++ offers nifty new and delete operators (that are easier to use than malloc, although that's what you would use in a C program). Using the new operator you can allocate space on the heap, which is usually has much more empty space than the stack.


void myFunction()
{
/* local variables allocated on the stack */
int localInt = 20;
int localArray[5] = {1, 2, 3, 4, 5};

/* dynamic variables allocated on the heap */
int * dynamicInt = new int(20); // allocates a single integer with value 20
int * dynamicArray = new int[1000000]; // allocates an array
// of a million integers

// Now you can treat dynamicArray just like a normal array
for(int i=0; i<1000000; i++)
{
dynamicArray[i] = i;
}

// For regular dynamic variables, you use the dereference operator
// to get their value
std::cout << *dynamicInt;

// DON'T FORGET TO DE-ALLOCATE YOUR DYNAMIC DATA!!!
delete dynamicInt; // de-allocate regular dynamic variable
delete[] dynamicArray; // de-allocate dynamic array
}


Hope that helps.

[imperialrage15]

Yep, that fixes it. Thanks! Took 50 seconds to find 'em. :)

I was reading through my c++ book, and rember thinking "When am I going to use this?" during the pointers section . Guess they're useful after all. :D