Thread: Problem: test if solution is integer

Hey everyone,

for some purpose, I need to check for large numbers if they are pentagonal. By far the fastest check is to solve the following equation:

f(x) = ( sqrt(24x + 1) + 1 ) / 2

if f(x) is an integral value, say n, then x is the nth pentagonal number.

I wrote the following function:

Code:

bool is_pentagonal(int x)
{
double n = ( sqrt(24 * x + 1) + 1 ) / 2;
return n == floor(n);
}

But this already fails for moderately large numbers due to numerical error! The function will give false, while the number entered is actually a pentagonal number.

My question: is there a better way of determining wether a value is integral? I searched the net for algorithms to check for perfect squares, which either used my type of method, or very complicated methods, like Newton's method (which I will dive into if I must).

Is there a simple solution (numerical or otherwise)?

Greets,
Kappie

I tried this code: (I assume this is what you ment)

Code:

bool is_pentagonal(int x)
{
int n = sqrt(24 * x + 1);
return n * n == 24 * x + 1;
}

and it also fails for the 10000th pentagonal number.

Note: I am aware this is not yet the full test, but this should in particular return true for pentagonal numbers.

How to fix this for larger numbers?

is it an overflow problem? maybe you could assign the sqrt return value to an long double instead then?
and then call floor with this value?

Hey guys, thanks for the resources, will try! The factor 2 I put in my initial post is indeed WRONG, it should be factor 6. The code should still return true for all pentagonal numbers, of course.
@ brewbuck: I guess I found that out!

You should definitely follow up on integer sqrt -- floating point is really unsuitable for this.

A few ramblings about int sizes and floating point: I thought I could cover it all in a few sentences but I guess I got carried away:

Originally Posted by Kappie

long long int n = sqrt(24 * x + 1), and now P(100000) fails,

From the wikipedia page, P(n) is (3*n^2 - n)/2. So P(100000) is 14999950000. If your system has 32-bit ints, this won't fit. You should check the width of your ints though -- you can have a look at sizeof(int), or go looking in limits.h (which lists minimum and maximum values for integer types, but GCC seems to like to organise its headers in a spiders web of impenetrable weirdness).

Anyway. On my system the max size of a signed int is 2147483647 (0x7FFFFFFF) - nowhere near big enough. Depending on how you got P(100000), it might be truncated from a bigger type or it might even have an undefined value (signed overflow is undefined). You could get past this by changing x to have a larger type, e.g. unsigned long long - you'd have to do this from the beginning of x's lifetime though: no use trying to cast to a larger type later.

Originally Posted by Kappie

what do the different integer / floating point types do?

Integer types (like char, short, int, long, long long) don't do anything special -- they're just numbers of varying sizes. E.g. sizes on many platforms is char=1 byte, short is 2 bytes, int is 4, long long is 8. Maximum permitted value depends on whether the type is signed or not, but otherwise they're pretty straightforward.

Floats and doubles are more complicated. I won't try to explain any details -- but in a nutshell, a floating point number is encoded as a value ("mantissa") and an exponent (and a sign bit). As well as allowing us to represent real numbers, it also gives us an enormous range. E.g. on my system the maximum value a double can hold is 1.7976931348623158e+308. The problem you'll encounter is that that double only has 15 decimal digits of precision (according to limits.h). When you have a number larger than this, you start to lose accuracy: the least significant digits aren't stored in the encoding any more. A double can represent all 32-bit integers accurately, but with 64-bit integers you'll run into trouble.

I wrote way more than I meant to here -- an awful lot of text when I could have just say "don't use doubles".