Like Tree5Likes

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. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    10

    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. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,981
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    10
    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. #4
    Registered User
    Join Date
    Apr 2012
    Posts
    2
    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. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Feb 2012
    Posts
    10
    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)?
    Last edited by Kappie; 04-27-2012 at 01:59 PM.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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...
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,160
    "Exactly an integer" and "floating point calculations" are incompatible concepts. If your algorithm involves a call to sqrt() then your algorithm is flawed.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Registered User
    Join Date
    Feb 2012
    Posts
    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. #11
    Registered User
    Join Date
    Jun 2005
    Posts
    5,886
    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.
    Right 98% of the time, and don't care about the other 3%.

  12. #12
    Registered User
    Join Date
    Mar 2010
    Posts
    531
    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".

  13. #13
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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;
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    Quote Originally Posted by grumpy View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by iMalc View Post
    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.
    iMalc likes this.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Intersect-test-solution, whats it called?
    By Raven Arkadon in forum C++ Programming
    Replies: 2
    Last Post: 04-12-2008, 08:09 PM
  2. How can I test if something is an integer or not?
    By e66n06 in forum C Programming
    Replies: 45
    Last Post: 01-22-2007, 12:02 AM
  3. Replies: 11
    Last Post: 12-24-2002, 10:00 AM
  4. test integer, float or not
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 01-23-2002, 02:29 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21