CODEWITHSUNDEEP
mathfloating-pointsquare-root
Vilx-
Vilx-

Reputation: 106980

Can a square root of a non-integer become an integer due to floating point rounding errors?

In another unrelated Internet forum a question was asked on how to check if a square root of a given number is an integer. Now in and of itself that is a trivial homework question, but I started to wonder if the naïve approach is correct under all circumstances. That is, in pseudocode:

declare x, y as double
input x
y = sqrt(x)
if round(y) = y then
    output "Is integer"
else
    output "Isn't integer"

Is it possible to enter such an x, that x itself would not be an integer (or an integer which is not a square of another integer) but sqrt(x) would be and integer because of floating point errors?

Upvotes: 1

Views: 1101

Answers (5)

Anders Forsgren
Anders Forsgren

Reputation: 11111

Feeding x as a float like 1+epsilon will of course work. But for a non-square integer it also works given the integer is large enough.

For example (c#)

ulong i = ulong.MaxValue; // 2^64-1, a non square integer.
double s = Math.Sqrt(i);  // Very nearly 2^32
bool same = Math.Round(s) == s; // true, s is close enough to 2^32.

Upvotes: 0

Petar Ivanov
Petar Ivanov

Reputation: 93070

Of course:

double d = Math.Sqrt(4.000000000000001);
Console.WriteLine(d == 4);
Console.WriteLine(d == 2);

This results in (C#)

False
True

Upvotes: 0

Kerrek SB
Kerrek SB

Reputation: 477444

First off, if the numbers are so large that the precision does not extend down to the decimal point, then you'll only get integers, but they're not correct, so I suppose you don't care about that case.

Concerning exact results: This should be fairly easy to test if you have IEE754 floats. Just take a double that is a perfect integral square, increment or decrement its binary representation by one bit, and then check if the square root is an exact integer. The standard floating point operations are required to be exact to 0.5 units in last place, I believe, so it's possible that the integer is actually the correct nearest representable square root.

Upvotes: 0

Keith Thompson
Keith Thompson

Reputation: 263557

The square root of the next representable floating-point number above 1.0 (nextafter(1.0) in C) could plausibly evaluate to 1.0.

Upvotes: 4

Lyth
Lyth

Reputation: 2211

Yes: when x is on the edge of Machine epsilon. Consider x = 1.00...0001, where it is still representable in its binary form, not identical to 1.0. A square root of this number will give 1.0, yielding false poitive.

Upvotes: 8

Related Questions