Какой хороший алгоритм, чтобы определить, является ли вход идеальным квадратом? [Дубликат]
-
19-08-2019 - |
Вопрос
Возможный дубликат:
Самый быстрый способ определить, является ли целочисленный квадрат корень - это целое число
Как узнать, является ли число идеальным квадратом ? Р>
bool IsPerfectSquare(long input)
{
// TODO
}
Я использую C #, но это не зависит от языка.
Бонусные баллы за ясность и простоту (это не код-гольф).
<Ч>Изменить. Это оказалось намного сложнее, чем я ожидал! Оказывается, проблемы с двойной точностью проявляются в двух направлениях. Во-первых, Math.Sqrt берет дубль, который не может удерживать длинную (спасибо Джону). Р>
Во-вторых, точность двойного теряет малые значения (.000 ... 00001), когда у вас есть огромный, почти идеальный квадрат. например, моя реализация не прошла этот тест для Math.Pow (10,18) +1 (мой сообщил, что истина).
Решение
bool IsPerfectSquare(long input)
{
long closestRoot = (long) Math.Sqrt(input);
return input == closestRoot * closestRoot;
}
Это может избавить от некоторых проблем, связанных с простой проверкой " является ли квадратный корень целым числом " но, возможно, не все. Возможно, вам нужно немного повеселее:
bool IsPerfectSquare(long input)
{
double root = Math.Sqrt(input);
long rootBits = BitConverter.DoubleToInt64Bits(root);
long lowerBound = (long) BitConverter.Int64BitsToDouble(rootBits-1);
long upperBound = (long) BitConverter.Int64BitsToDouble(rootBits+1);
for (long candidate = lowerBound; candidate <= upperBound; candidate++)
{
if (candidate * candidate == input)
{
return true;
}
}
return false;
}
Неприлично и не нужно ни для чего, кроме действительно больших значений, но я думаю, что должно работать ...
Другие советы
bool IsPerfectSquare(long input)
{
long SquareRoot = (long) Math.Sqrt(input);
return ((SquareRoot * SquareRoot) == input);
}
В Common Lisp я использую следующее:
(defun perfect-square-p (n)
(= (expt (isqrt n) 2)
n))