Какой хороший алгоритм, чтобы определить, является ли вход идеальным квадратом?

Question

Возможный дубликат:
Самый быстрый способ определить, является ли целочисленный квадратный корень целым числом

Как узнать, является ли число идеальным квадратом?

bool IsPerfectSquare(long input)
{
   // TODO
}

Я использую C#, но это не зависит от языка.

Бонусные баллы за ясность и простоту (это не означает, что код-гольф).

---

Изменить: это стало намного сложнее, чем я ожидал! Оказывается, проблемы с двойной точностью проявляются в двух направлениях. Во-первых, Math.Sqrt берет дубль, который не может удерживать длинную (спасибо Джону).

Во-вторых, точность двойного теряет малые значения ( .000...00001), когда у вас есть огромный, почти идеальный квадрат. Например, моя реализация не прошла этот тест для Math.Pow(10,18)+1 (мой сообщил, что истина).

Answer 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;
}

Идиотский и ненужный для чего-либо, кроме действительно больших значений, но я думаю, что это должно работать...

Answer 2

bool IsPerfectSquare(long input)
{
    long SquareRoot = (long) Math.Sqrt(input);
    return ((SquareRoot * SquareRoot) == input);
}

Answer 3

В Common Lisp я использую следующее:

(defun perfect-square-p (n)
  (= (expt (isqrt n) 2)
     n))