Unknown crash in a C++ Memory Pointers Exercise

Question

I recently wrote a program to help me understand the basics of memory pointers in C++, I chose a simple prime number finder.

I finally got it to work. (yay for debugging!)

And I let it run to see how far it goes, it gets to prime #815389 with my verbose tells me is the 65076th prime, I get an app crash. The one thing I could think of was my ints overflowing so I changed them to longs, it gets stuck at the same place.

Would someone be able to help explain what limitation is causing this?

comp: WinVista 64-bit Home Premium, 6GB ram AMD 4800+ X2 program crashes at 4,664K memory usage

Source:

#include <cstdlib>

#include <iostream>

\\\\(Backslashes added for readability)

using namespace std;

long number;
long numnum;

class num;

class num {

  public:

         long i;
         void check();
         bool nxt;
         num* nxtnum;
};

void num::check() {

 if (number % i != 0) {
            if (nxt == true) {
                    (*nxtnum).check();
            } else {
                   nxtnum = new num();
                   (*nxtnum).i = number;
                   numnum++;
                   cout << numnum << ":" << number << ", ";
                   nxt = true;
            };
 };
};


int main(long argc, char *argv[]){

  numnum = 1;
  cout << numnum << ":" << 2 << ", ";
  num two;
  two.i = 2;
  for (number = 3; 1<=1000001; number++) {
    two.check();
  };
  cout << endl;
  system("PAUSE");
  return EXIT_SUCCESS;
};

(Nevermind the username it's just an alias I use so I can keep track of all my posts with google)

Answer 1

Stack overflow? I see that check is recursive.

Answer 2

I'd put a guess on the fact that two.nxt isn't initialized. In C, primitive datatypes aren't initialized, meaning they have the value of whatever happened to be in whatever memory it's now occupying. That means that more than likely, in main(), two.nxt = true, which causes check() to be run on an invalid pointer. Try explicitly setting it to false and see if that works for you.

[edit] If this is the issue, the more important initialization would be when you allocate the new num in check().

Answer 3

Couple of problems I can see:

• You're allocating a bunch of nums, but you're not checking for a std::bad_alloc exception. You might simply be running out of memory...
• You're not checking anywhere if nxtnum is != 0, even though I think it's safe to do so as the only places where you dereference it are guarding. Nevertheless, it's not that great a practise.

• As Sean Edwards mentions, the num class doesn't have a constructor, so the members of a newly created num are filled with pretty much random junk. And that random junk might include nxt being set to a nonzero value. I'd add the following constructor to give it a set of safe defaults:

  num::num() : i(0), nxt(false), nxtnum(0) {}

• You don't really need the boolean value, I'd just check for nxtnum being non-zero.

• As Jeff Yates says, you might suffer from a stack overflow as the recursive function is getting nested too deep, but it doesn't look like it'll recurse that deep.

Answer 4

Sean is right, two.nxt is never initialised. In fact, num.nxt is never initialised for any instance of num. The member nxt is unnecessary if the class is made more robust. The nxt pointer can be used instead:

class num
{
private:
    long i;
    num *nxtnum;
public:
    num (long value) : i (value), nxtnum (0) { }
    void check ()
    {
      if (number % i != 0)
      {
        if (nxtnum)
        {
          nxtnum->check ();
        }
        else
        {
          nxtnum = new num (number);
          cout << ++numnum << ":" << number << ", ";
        }
     }
};

Of course, the recursive nature is probably the main culprit, the initialisation issue was hidden as you were probably running a debug build. Converting the recursive form to the iterative form is left as an exercise.

Skizz

Answer 5

Incidentally, if you're using a Microsoft compiler, int and long are the same size when targeting x64. You also have an infinite loop in your main function, as 1 will always be <= 1000001.

Answer 6

I've got it working, thank you Skizz

#include <cstdlib>
#include <iostream>
#include <windows.h>

using namespace std;

long number;
long numnum;
class num;
num *two;
num *nn;
num *bre;

class num
{
    private:
        long i;
        num *nxtnum;
    public:
        num (long value) : i (value), nxtnum (0) { }
        void *check ()
        {
          if (number % i != 0)
          {
            if (nxtnum)
            {
              //nxtnum->check ();
              nn = nxtnum;
            }
            else
            {
              nxtnum = new num(number);
              cout << ++numnum << ":" << number << ", ";
              nn = bre;
            }
         }else{nn=bre;}
        }
};

int main(long argc, char *argv[])
{
    numnum = 1;
    cout << numnum << ":" << 2 << ", ";
    two = new num(2);
    nn=two;
    for (number = 3; 1<=1000001; number++) {
        while (nn!=bre){
                nn->check();
                Sleep(0);
                }
        nn=two;
    };
    cout << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
};

For Those Interested