입력이 완전 제곱인지 확인하는 좋은 알고리즘은 무엇입니까?

입력이 완전 제곱인지 확인하는 좋은 알고리즘은 무엇입니까? [복제]

---

중복 가능성 :
정수의 제곱근이 정수인지 확인하는 가장 빠른 방법

숫자가 완벽한 제곱 인지 확인하는 방법은 무엇입니까 ?

bool IsPerfectSquare(long input)
{
   // TODO
}

나는 C #을 사용하고 있지만 이것은 언어에 구애받지 않습니다.

명확성과 단순성을위한 보너스 포인트 (코드 골프가 아닙니다).

---

편집 : 이것은 내가 예상했던 것보다 훨씬 더 복잡해졌습니다! 배정 밀도의 문제는 몇 가지 방식으로 나타납니다. 첫째, Math.Sqrt는 정확히 오래 견딜 수없는 double을 취합니다 (Jon에게 감사합니다).

둘째, 거대하고 거의 완벽한 제곱이있을 때 double의 정밀도는 작은 값 (.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;
}

Icky, 정말 큰 값 외에는 필요하지 않지만 작동 해야 한다고 생각합니다 .

---

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

참고 URL : https://stackoverflow.com/questions/343852/whats-a-good-algorithm-to-determine-if-an-input-is-a-perfect-square