# Problem: test if solution is integer

This is a discussion on Problem: test if solution is integer within the C++ Programming forums, part of the General Programming Boards category; Hey everyone, for some purpose, I need to check for large numbers if they are pentagonal. By far the fastest ...

1. ## 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

2. You could compute the square root of (24 * x + 1) as an integer, then check that when multiplied by itself, you get (24 * x + 1). If so, and if that integral square root is odd, then x is a pentagonal number.

3. 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?

4. 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?

5. What compiler are you using and/or how big is an int with that compiler?
What value of x do you pass to check the 10000th pentagonal number?

6. P(10000) = 149995000. I use g++ as compiler. I don't now how large an int is. I couldn't find it on the web either. I'm not very knowledgeable about this kind of technical details, but I'm surely willing to learn. Where could the overflow problem come from, what do the different integer / floating point types do?

EDIT:

I tried using:

long long int n = sqrt(24 * x + 1), and now P(100000) fails, but that integer is more than 100 times as big as the previous fail.

I may live with this, but I don't know for how large values I need to compute this. Is there an algorithm so I can compute whether an arbitrarily large number is a perfect square? Maybe avoiding numerical error altogether (pure int)?

7. Where has the division by 2 gone, and why does wikipedia's pentagonal number formula have a factor of 6 instead?
How are you checking the results?
What does the current code look like?

To calculate the integer square root without worrying about precision issues due to using floating point, refer to http://www.hackersdelight.org/HDcode/isqrt.c.txt
I recommend modifying isqrt4 to use long long.

8. Where did you get your original formula from? When I solve the pentagonal number formula using the quadratic formula, I get an overall divisor of 6, not 2. I.e.,
Code:
( sqrt(24 * x + 1) + 1 ) / 6;
Also, a common "bignum" library is The GNU MP Bignum Library

EDIT: Of course! Beat to the punch...

9. "Exactly an integer" and "floating point calculations" are incompatible concepts. If your algorithm involves a call to sqrt() then your algorithm is flawed.

10. 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!

11. Apart from the issue of using incorrect factors .....

Following up on laserlight's suggestion, it is possible to compute the square root as an integer using the technique in this link. That link even has a code sample which computes the greatest integer less than or equal to the square root.

As to whether you need a bignum library .... that depends on how large your "large numbers" really are.

12. 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".

13. You don't have to "go looking in limits.h" to find the max int (or uint) value. Just print it out with a program:
Code:
#include <stdio.h>
#include <limits.h>
int main(void) {
printf("INT_MAX  : %d\n",  INT_MAX);
printf("UINT_MAX : %u\n",  UINT_MAX);
printf("LONG_MAX : %ld\n", LONG_MAX);
printf("ULONG_MAX: %lu\n", ULONG_MAX);
return 0;
}

14. Originally Posted by grumpy
it is possible to compute the square root as an integer using the technique in this link. That link even has a code sample which computes the greatest integer less than or equal to the square root.
Whilst that algorithm will surely work, it has very slow convergence, i.e. O(sqrt(n)).
The algorithms I linked to have much faster convergence i.e. O(log(n)) and are thus suitable for numbers in the long long range or larger.

But I guess if you need to understand how it works then you might have a slightly better chance with the one grumpy linked.

15. Originally Posted by iMalc
But I guess if you need to understand how it works then you might have a slightly better chance with the one grumpy linked.
If you're going to do that, then you may as well test for "pentagonality" directly like this:
Code:
int isPentagonal(uint n) {
uint i, delta;
for (i = 1, delta = 4; i < n; i += delta, delta += 3)
;
return i == n;
}
You could speed that up with a partial table of pentagonal numbers and their respective deltas (the value of delta that the above algorithm has when that pentagonal number is calculated). The table could be binary-searched and then a linear search could take place in the interval.

Page 1 of 2 12 Last
Popular pages Recent additions