입력이 완벽한 정사각형인지 확인하기위한 좋은 알고리즘은 무엇입니까? [복제하다

Question

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

숫자가 완전 제곱?

bool IsPerfectSquare(long input)
{
   // TODO
}

나는 C#을 사용하고 있지만 이것은 언어 불가지론입니다.

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

---

편집하다: 이것은 내가 예상했던 것보다 훨씬 더 복잡해졌습니다! 이중 정밀도의 문제는 몇 가지 방법으로 나타납니다. 첫째, Math.sqrt는 정확하게 길게 붙잡을 수없는 두 배를 차지합니다 (Jon에게 감사합니다).

둘째, 이중의 정밀도는 거대하고 완벽한 사각형이있을 때 작은 값 (.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

일반적인 LISP에서는 다음을 사용합니다.

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