CODEWITHSUNDEEP
c++
Jorge Esteban
Jorge Esteban

Reputation: 9

Number like 0.999999 rounded to 1

In C/C++:

I need to find if some big numbers are perfect squares, but my code finds numbers like 851659987045856130 to be valid, when 922854261.00000000487617621781778 is the actual square root(to a larger precision) and is not an integer. Is there any way to delay the rounding for a better precision? I know that the number above doesn't even have "perfect square last digit(s)", but I want to know in general if it is possible to check if such a big number is in fact a perfect square with a reasonable but higher precision than standard.

Upvotes: 0

Views: 524

Answers (3)

Matteo Italia
Matteo Italia

Reputation: 126787

It's not just like std::sqrt is not precise enough, it's that doubles aren't even precise enough to represent your input correctly. To have a valid result, you have to perform your "real" check in integer arithmetic.

A simplistic alternative to the integer square root method can be to use the result of std::sqrt as a hint for an exact search of the square:

bool is_square(int64_t val) {
    int64_t guess = std::sqrt(val);
    for(int64_t g=guess;;++g) {
        if(g*g==val) return true;
        if(g*g>val) break;
    }
    for(int64_t g=guess-1;;--g) {
        if(g*g==val) return true;
        if(g*g<val) break;
    }
    return false;
}

I suspect that this may be faster than the "real thing" in most cases, given that the floating point square root algorithm may even be implemented in hardware and thus should give the starting point really quickly (the rest of the algorithm should be extremely fast, both loops should exit after a handful of iterations).

Upvotes: 1

user1084944
user1084944

Reputation:

The best thing to do here is to use an exact square root algorithm. If that number is representative of the size you're testing, you wouldn't even need a multiprecision arithmetic package — however, such a package would be the easiest place to obtain an implementation of such an algorithm. In fact, it would probably implement is_square directly (and might be faster than by computing a square root).

If you were curious about rolling your own implementation, the usual approach is Newton's method; e.g. as seen at https://en.wikipedia.org/wiki/Integer_square_root .

Upvotes: 1

Dan Korn
Dan Korn

Reputation: 1294

Truncate the result to int, then multiply it by itself to see if you end up with the original number.

Upvotes: -1

Related Questions