Может ли квадратный корень нецелого числа стать целым числом из-за ошибок округления с плавающей запятой?

Question

На другом несвязанном интернет-форуме был задан вопрос о том, как проверить, является ли квадратный корень данного числа целым числом.Сам по себе это тривиальный домашний вопрос, но я начал задаваться вопросом, верен ли наивный подход при любых обстоятельствах.То есть в псевдокоде:

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

Возможно ли ввести такое значение x, что само по себе x будет не целым числом (или целым числом, которое не являетсяквадрат другого целого числа), но sqrt(x) будет и целым числом из-за ошибок с плавающей запятой?

Answer 1

Да: когда x на краю Машина эпсилон . Рассмотрим x = 1.00 ... 0001, где он все еще представлен в двоичной форме, а не идентично 1.0. Квадратный корень этого числа даст 1,0, что приведет к ложному положительному результату.

Answer 2

Квадратный корень следующего представимого числа с плавающей точкой выше 1,0 (nextafter(1.0) в C) может правдоподобно принять значение 1,0.

Answer 3

Кормление х как поплавок, как 1 + эпсилон, конечно, будет работать. Но для неквадратного целого числа это также работает, если целое число достаточно велико.

Например (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.

Answer 4

Конечно:

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

Это приводит к (C #)

False
True

Answer 5

Во-первых, если числа настолько велики, что точность не распространяется до десятичной точки, то вы получите только целые числа, но они не верны, поэтому я полагаю, вам не важен этот случай .

Относительно точных результатов: это должно быть довольно легко проверить, если у вас есть плавающие IEE754. Просто возьмите двойное число, представляющее собой идеальный целочисленный квадрат, увеличьте или уменьшите его двоичное представление на один бит, а затем проверьте, является ли квадратный корень точным целым числом. Я полагаю, что стандартные операции с плавающей запятой должны быть точными с точностью до 0,5 единиц в последнем месте, поэтому вполне возможно, что целое число на самом деле является правильным ближайшим представимым квадратным корнем.