Was ist ein guter Algorithmus, um zu bestimmen, ob eine Eingabe ein perfektes Quadrat ist? [Duplikat]

Question

  

Mögliche Duplizieren:
   schnellsten Weg, wenn eine ganze Zahl Platz zu bestimmen, root eine ganze Zahl

Was ist ein Weg, um zu sehen, ob eine Zahl ein Quadrat ist?

bool IsPerfectSquare(long input)
{
   // TODO
}

Ich bin mit C #, aber das ist sprachunabhängig.

Bonuspunkte für Klarheit und Einfachheit (ist dies nicht dazu gedacht, Code-Golf zu sein).

---

Edit: Das hat sehr viel komplexer als ich erwartet hatte! Es stellt sich heraus, die Probleme mit doppelter Genauigkeit selbst ein paar Weise manifestieren. Zuerst nimmt Math.Sqrt eine doppelte, die nicht gerade eine lange (dank Jon) halten kann.

Zweitens ein doppelte Präzisions wird kleine Werte verlieren (0,000 ... 00001), wenn Sie einen großen, nahezu perfekten Platz. beispielsweise versagt meine Implementierung dieser Test für Math.Pow (10,18) +1 (Mine berichtet true).

Answer 1

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

Das kann weg von einige der Probleme nur Überprüfung „ist die Quadratwurzel eine ganze Zahl“, aber möglicherweise nicht alle. Sie müssen möglicherweise ein wenig funkier zu bekommen:

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 und unnötig für etwas anderes als wirklich große Werte, aber ich denke, es ist sollte Arbeit ...

Answer 2

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

Answer 3

In Common Lisp, verwende ich die folgenden:

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