Mitigating stack overflows

[nullcoding]

A friend and I have written a basic Proth number tester that asks for k and an upper/lower bound of n, then tests with N=k*(2^n)-1 with a nice do-while loop.

That all works fine...unless we input an upper bound greater than 33 or so. I've yet to determine what exactly causes the program to hang, but it appears as though it cannot handle an N larger than 11 digits.

Quite an improvement over the previous version, which could not handle larger than (2^31)-1.

You can see our code here: http://code.google.com/p/gjsieve/source/browse/main_5.cpp

We believe it's a stack problem. I'm just not sure how to increase it properly. We were told to increase max stack size in linking options for the compiler, but that changed nothing.

If we try with k = 3, lower = 3, and upper = 33, it works fine.

[Stewbond]

k is 1, then it should be able to handle anything up to (2^63)-1 assuming that uint64_t actually gives you a 64bit unsigned integer. Try playing with other ways of making a 64-bit integer. It'll be compiler-specific:

You could try unsigned long long or unsigned __int64 based on this link below:
http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.80).aspx

If that is insufficient then you'll need to build a class to handle this. The class would have several ints (maybe a vector of ints) that would take all overflowing bits. You'd need to overload the basic math operators (*, / , %, +, -) and you would need to write your own pow() function.

[JLBorges]

inline uint64_t pow(uint64_t x, uint64_t y)
{
    return pow((uint64_t)x,(uint64_t)y);
}

This recursive call is certain to cause a stack overflow, no matter what the size of the stack is.

[Computergeek01]

@ JLBorges: That's because it's a recursive loop without an escape, you are correct but you're also cheating. Why are you casting the arguments in the call by the way?

EDIT: I would also like to add that you don't know if your compiler is actually going to inline a function call, it's just a suggestion. I would also like to ask that if your compiler does inline the function call, afterall it's only a suggestion, then what part of this is getting pushed to the stack?

[JLBorges]

> @ JLBorges: That's because it's a recursive loop without an escape

Thank you very much. That was an astute and profound observation.


> but you're also cheating. Why are you casting the arguments in the call by the way?

Read the first post in the thread which has this piece of information:

You can see our code here: http://code.google.com/p/gjsieve/source/browse/main_5.cpp

And though shalt be enlightened.


> if your compiler does inline the function call, afterall it's only a suggestion,
> then what part of this is getting pushed to the stack?

Also read up on inlining - in particular try to understand what can be inlined, and what can't.

[nullcoding]

Ok - thanks for the pointers.

Even using MSVC++ and having replaced uint64_t with unsigned __int64 (which I understand to be the same thing), it still hangs at the same points it did before.

Writing our own pow() function sounds a bit too advanced for where we stand in coding knowledge and experience at the moment - unless it's actually easily done. I don't know.

Making a class to handle overflows sounds more feasible. My partner did say that it would make more sense to write this with several applications rather than a single cpp fie. I'm totally lost on vectors, though. Haven't quite gotten there in my self-teaching yet.

[JLBorges]

Repeat: I don't know if control ever reaches this function:

inline uint64_t pow(uint64_t x, uint64_t y)
{
    return pow((uint64_t)x,(uint64_t)y);
}

But if it does, it will result in an infinite recursion.

Also, just noticed this on line number 101: i = i++;
This construct leads to undefined behaviour.

[nullcoding]

i = i++; is supposed to be how the number N is factored. If the only value of i happens to be i == N, then the number is prime (or, for our purposes, assumed to be).

If the inlining is wrong or useless then should it be moved or removed? If I comment it out, nothing changes, leading me to believe you're right about control not reaching it.

Sorry, my beginner-ness is really showing on this one.

Recursion shouldn't be infinite, by the way - it should only run the algorithm from n(lower) to n(upper).

[JLBorges]

> i = i++; is supposed to be how the number N is factored.

You want to increment i ; just do ++i ; - NOT i = i++ ;


> If the inlining is wrong or useless then should it be moved or removed?

It's not the inline that is wrong; the function would be equally wrong without the inline. Just remove the whole function from your program.


The standard C++ library has overloads of the pow() function in <cmath> as given here:
http://en.cppreference.com/w/cpp/numeric/math/pow
So if you are not using C++11, write

template< typename T, typename U >
inline std::uint64_t my_pow( T a, U b )
{ return std::pow( (double)a, (double)b ) + 0.5 ; }

and then replace all calls to pow() with my_pow()

If N happens to be a very large prime number (let us say a 13 digit prime number with 9 as the first digit), this loop is going to take a huge amount of time:

                N = ((k*(pow((long double)2,(long double)j))-1));

                do
                {

                    // quotient = N/i; // unnecessary, quotient is computed later.


                    //i = i++; // undefined; replace with ++i 
                   ++i ;

                }
                while ((N%i) != 0);

                quotient = N/i;

Assuming that the hardware can do one billion 64-bit integer divisions per second, it will take about three hours.

You need to speed it up by exiting the loop once i is greater than the square root of N. Better, limit the divisions to prime numbers up to the square root of N. (Using a suitable sieve algorithm, pre-generate all prime numbers up to the square root of the largest value of N that you intend to handle).

[nullcoding]

Excellent. That helps a lot. Thanks!

One issue is though - when I replaced the original inline with this updated template of yours, it wants an initializer before "template" and I don't know what to give it. I suppose you meant to insert it where the original inline was.

My partner is absolutely no help in this manner...I think he might be a bit lost as well.

However, you're right about the loop taking a huge amount of time. On this system, a 32-bit XP build on a Celeron, I'd expect three to four hours for this unrefined loop. That's reasonable. As long as I can be sure it isn't hanging, I'm fine with it.

[JLBorges]

> I suppose you meant to insert it where the original inline was.

Yes.



> I'd expect three to four hours for this unrefined loop. That's reasonable.
> As long as I can be sure it isn't hanging, I'm fine with it.

I just realized that I made a mistake.

... a very large prime number (let us say a 13 digit prime number with 9 as the first digit)
... the hardware can do one billion 64-bit integer divisions per second
... it will take about three hours.

That last line should have been: it will take about 28 hours. With that loop in there, the code just doesn't scale to large numbers.

[nullcoding]

I don't care. As long as it is not hanging, I consider this a step in the right direction.

I'm well aware of the applications out there that do have scaling code (gwnum and llr among them) and this is certainly not an attempt at replicating them...but I did want to a) try my hand at C++ and b) try to emulate what large-scale prime searches do.

See, I've used your code properly now. It runs fine. Still hangs though. Uses 100% CPU and exactly 1024K memory. I suppose it would run fine if we could somehow allocate more memory.

[JLBorges]

> I've used your code properly now.

Have you changed the code to limit the loop to test with prime numbers up to the square root?



> Still hangs though. Uses 100% CPU and exactly 1024K memory.

How do you know it is hanging? It is probably just taking a lot of time to execute that loop. Let in run for a day or so and see if it makes any progress.


> I suppose it would run fine if we could somehow allocate more memory.

The problem is not related to the amount of memory - this program needs only a very (very) small amount of memory.