# Problem: test if solution is integer

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 04-27-2012
Kappie
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
• 04-27-2012
laserlight
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.
• 04-27-2012
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?
• 04-27-2012
Skatte
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?
• 04-27-2012
iMalc
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?
• 04-27-2012
Kappie
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)?
• 04-27-2012
iMalc
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.
• 04-27-2012
oogabooga
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...
• 04-27-2012
brewbuck
"Exactly an integer" and "floating point calculations" are incompatible concepts. If your algorithm involves a call to sqrt() then your algorithm is flawed.
• 04-28-2012
Kappie
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!
• 04-28-2012
grumpy
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.
• 04-28-2012
smokeyangel
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:

Quote:

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.

Quote:

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".
• 04-28-2012
oogabooga
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; }```
• 04-28-2012
iMalc
Quote:

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.
• 04-29-2012
oogabooga
Quote:

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.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last