Number like 0.999999 rounded to 1

Question

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.

Google for big number libraries,eg https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library — Richard Critten, Jul 14 '16 at 22:59
@Richard: Don't even need a bignum library here: this could be done entirely in `uint64_t` arithmetic, if you had the algorithm for computing square roots. — , Jul 14 '16 at 23:00
@Hurkyl square root: start with a guess, square it, adjust guess, repeat until found or no solution — Richard Critten, Jul 14 '16 at 23:01
You can tell 851659987045856130 is not a square even without calculating expensive square roots because in hexadecimal the least significant digit is 2 and only quadratic residues modulo 16 are 0,1,4 and 9 — harold, Jul 14 '16 at 23:06
https://en.wikipedia.org/wiki/Integer_square_root has an algorithm using only integer operations. — Omegaman, Jul 14 '16 at 23:08

score 1 · Answer 1 · answered Jul 14 '16 at 23:03

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 .

Matteo Italia · Answer 2 · 2016-07-14T23:19:01.447

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).

score -1 · Answer 3 · answered Jul 14 '16 at 22:54

-1

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

answered Jul 14 '16 at 22:54

Dan Korn

1,274
9
14

@Matteo: I think you left the number in floating point, rather than remembering to convert back to `uint64_t` – Jul 14 '16 at 22:56
1

@MatteoItalia, really? He proposes to multiply integers. – s.bandara Jul 14 '16 at 22:57
The answer is still wrong, though; you need to round. – Jul 14 '16 at 22:57
True, but not a bad idea to begin with. I wonder if multiplying the least significant digit of that integer already catches a lot if not all cases. – s.bandara Jul 14 '16 at 22:59
@s.bandara actually, it's not really clear where this number comes from - I expected it to be stored in a `double` since the beginning, which means that it starts out not precise enough, but it's true that it will probably come from a 64 bit integer or something like that. The question should be clarified a bit. – Matteo Italia Jul 14 '16 at 23:00
Still, the problem is still present - given that the input cannot be appropriately represented by a `double` you may even get false negatives if you just check the result of `std::sqrt` (you get the square root of the nearest representable `double`, which may not be a perfect square); you can use the result of 'std::sqrt` as a starting guess for integer squaring, though. – Matteo Italia Jul 14 '16 at 23:04

Number like 0.999999 rounded to 1

3 Answers3