Schnellster Weg zu bestimmen, ob die Quadratwurzel einer ganzen Zahl eine ganze Zahl ist

Question

Ich suche nach dem schnellsten Weg, um festzustellen, ob ein long-Wert eine Quadratzahl ist (d. h., ob seine Quadratwurzel eine andere ganze Zahl ist):

1. Ich habe es auf einfache Weise gemacht, indem ich die integrierte Math.sqrt() Funktion verwendet habe, aber ich frage mich, ob es einen schnelleren Weg gibt, indem man sich auf den Bereich der Ganzzahlen beschränkt.
2. Das Führen einer Lookup-Tabelle ist unpraktisch (da es etwa 231,5 Ganzzahlen gibt, deren Quadrat kleiner als 263 ist).

Hier ist der sehr einfache und direkte Weg, den ich jetzt gehe:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

_{Hinweis: Ich verwende diese Funktion in vielen <a href="http://projecteuler.net/" rel="noreferrer">Project Euler</a> Problemen. Also wird niemand anderer jemals diesen Code pflegen müssen. Und diese Art von Mikro-Optimierung könnte tatsächlich einen Unterschied machen, da ein Teil der Herausforderung darin besteht, jeden Algorithmus in weniger als einer Minute auszuführen, und diese Funktion in einigen Problemen Millionen von Malen aufgerufen werden muss.}

---

Ich habe die verschiedenen Lösungen für das Problem ausprobiert:

• Nach umfangreichen Tests habe ich festgestellt, dass das Hinzufügen von 0.5 zum Ergebnis von Math.sqrt() nicht notwendig ist, zumindest nicht auf meinem Computer.
• Der schnelle Kehrwert der Quadratwurzel war schneller, gab aber falsche Ergebnisse für n >= 410881. Jedoch, wie von BobbyShaftoe vorgeschlagen, können wir den FISR-Hack für n < 410881 verwenden.
• Newton's Methode war deutlich langsamer als Math.sqrt(). Das liegt wahrscheinlich daran, dass Math.sqrt() etwas Ähnliches wie Newton's Methode verwendet, aber in der Hardware implementiert ist, so dass sie viel schneller als in Java ist. Außerdem erforderte Newton's Methode immer noch die Verwendung von Doubles.
• Eine modifizierte Newton-Methode, die ein paar Tricks verwendete, so dass nur Ganzzahlenmathematik beteiligt war, erforderte einige Hacks, um Überlauf zu vermeiden (Ich möchte, dass diese Funktion mit allen positiven 64-Bit-Ganzzahlen funktioniert), und war immer noch langsamer als Math.sqrt().
• Die binäre Suche war noch langsamer. Das ergibt Sinn, da die binäre Suche im Durchschnitt 16 Durchläufe benötigen wird, um die Quadratwurzel einer 64-Bit-Zahl zu finden.
• Laut Johns Tests ist die Verwendung von or-Anweisungen in C++ schneller als die Verwendung eines switch, aber in Java und C# scheint es keinen Unterschied zwischen or und switch zu geben.
• Ich habe auch versucht, eine Lookup-Tabelle zu erstellen (als ein privates statisches Array von 64 booleschen Werten). Dann anstatt eines Switch- oder or-Statements würde ich einfach sagen if(lookup[(int)(n&0x3F)]) { test } else return false;. Zu meiner Überraschung war dies (nur leicht) langsamer. Das liegt daran, dass in Java Arraygrenzen überprüft werden.

Answer 1

Nur der Vollständigkeit halber, ein anderer Ansatz besteht darin, die Primfaktorzerlegung zu verwenden. Wenn jeder Faktor der Zerlegung gerade ist, dann ist die Zahl ein perfektes Quadrat. Also, was du sehen möchtest, ist, ob eine Zahl als Produkt von Quadraten von Primzahlen zerlegt werden kann. Natürlich musst du keine solche Zerlegung erhalten, sondern nur sehen, ob sie existiert.

Erstelle zunächst eine Tabelle mit Quadraten von Primzahlen, die kleiner als 2^32 sind. Diese ist deutlich kleiner als eine Tabelle aller ganzen Zahlen bis zu diesem Limit.

Ein Lösungsansatz könnte dann so aussehen:

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

Ich denke, das ist ein bisschen kryptisch. Was es tut, ist bei jedem Schritt zu überprüfen, ob das Quadrat einer Primzahl die Eingabezahl teilt. Wenn dies der Fall ist, wird die Zahl durch das Quadrat geteilt, solange dies möglich ist, um dieses Quadrat aus der Primfaktorzerlegung zu entfernen. Wenn wir dabei zu 1 kommen, dann war die Eingabezahl eine Zerlegung von Quadraten von Primzahlen. Wenn das Quadrat größer als die Zahl selbst wird, dann gibt es keine Möglichkeit, dass dieses Quadrat oder größere Quadrate sie teilen können, also kann die Zahl keine Zerlegung von Quadraten von Primzahlen sein.

Aufgrund der heutigen sqrt-Hardwareberechnung und der Notwendigkeit, hier Primzahlen zu berechnen, denke ich, dass diese Lösung viel langsamer ist. Aber sie sollte bessere Ergebnisse liefern als die Lösung mit sqrt, die über 2^54 nicht funktionieren wird, wie mrzl in seiner Antwort sagt.

Answer 2

Die folgende Vereinfachung von maaartinus Lösung scheint einige Prozentpunkte von der Laufzeit abzuschneiden, aber ich bin nicht gut genug im Benchmarking, um einen Benchmark zu erstellen, dem ich vertrauen kann:

long goodMask; // 0xC840C04048404040 unten berechnet
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // Dies testet, ob die 6 am wenigsten signifikanten Bits richtig sind.
    // Das Verschieben des zu testenden Bits an die höchste Position spart uns die Maskierung.
    if (goodMask << x >= 0) return false;
    // Entfernen einer geraden Anzahl von nachfolgenden Nullen, sodass höchstens eine übrig bleibt.
    x >>= (Long.numberOfTrailingZeros(x) & (-2));
    // Wiederholen des Tests auf den 6 am wenigsten signifikanten verbleibenden Bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Mach es auf klassische Weise.
    // Die Korrektheit ist nicht trivial, da die Umwandlung von long in double Verluste verursacht!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

Es wäre interessant zu überprüfen, wie sich die Leistung auswirken würde, wenn der erste Test ausgelassen würde:

if (goodMask << x >= 0) return false;

würde die Leistung beeinträchtigen.

Answer 3

Es wurde darauf hingewiesen, dass die letzten d Ziffern eines perfekten Quadrats nur bestimmte Werte annehmen können. Die letzten d Ziffern (im Basis b) einer Zahl n entspricht dem Rest, wenn n durch b``d geteilt wird, d.h. in C Notation n % pow(b, d).

Dies kann auf jedes Modul m verallgemeinert werden, d.h. n % m kann verwendet werden, um einen bestimmten Prozentsatz von Zahlen auszuschließen, die perfekte Quadrate sein könnten. Das Modul, das Sie derzeit verwenden, ist 64, was 12, d.h. 19% der Reste, als mögliche Quadrate ermöglicht. Mit etwas Codierung fand ich das Modul 110880, das nur 2016, d.h. 1,8% der Reste als mögliche Quadrate zulässt. Je nach Kosten einer Moduloperation (d.h. Division) und einer Tabellensuche im Vergleich zu einer Quadratwurzel auf Ihrem Gerät kann die Verwendung dieses Moduls schneller sein.

Übrigens, wenn Java eine Möglichkeit hat, ein gepacktes Array von Bits für die Suchtabelle zu speichern, verwenden Sie es nicht. 110880 32-Bit Wörter sind heutzutage nicht viel RAM und das Abrufen eines Maschinenworts wird schneller sein als das Abrufen eines einzelnen Bits.

Answer 4

Für die Leistung musst du sehr oft Kompromisse eingehen. Andere haben verschiedene Methoden vorgeschlagen, aber du hast festgestellt, dass Carmacks Hack bis zu bestimmten Werten von N schneller ist. Dann solltest du den Wert "n" überprüfen und wenn er kleiner als diese Zahl N ist, Carmacks Hack verwenden, ansonsten eine andere hier in den Antworten beschriebene Methode verwenden.

Answer 5

Dies ist die schnellste Java-Implementierung, die ich entwickeln konnte, unter Verwendung einer Kombination von Techniken, die von anderen in diesem Thread vorgeschlagen wurden.

• Mod-256-Test
• Ungefährer Mod-3465-Test (vermeidet Ganzzahldivision auf Kosten einiger falscher Treffer)
• Gleitkommazahl Quadratwurzel, runden und mit Eingabewert vergleichen

Ich habe auch mit diesen Modifikationen experimentiert, aber sie haben die Leistung nicht verbessert:

• Zusätzlicher Modulo-255-Test
• Unterteilen des Eingabewerts durch Potenzen von 4

• Schnelle Inverse Quadratwurzel (um für hohe Werte von N zu arbeiten, benötigt es 3 Iterationen, genug um es langsamer als die Hardware-Quadratwurzel-Funktion zu machen.)

  public class QuadratTester {

  public static boolean istPerfektesQuadrat(long n) {
      if (n < 0) {
          return false;
      } else {
          switch ((byte) n) {
          case -128: case -127: case -124: case -119: case -112:
          case -111: case -103: case  -95: case  -92: case  -87:
          case  -79: case  -71: case  -64: case  -63: case  -60:
          case  -55: case  -47: case  -39: case  -31: case  -28:
          case  -23: case  -15: case   -7: case    0: case    1:
          case    4: case    9: case   16: case   17: case   25:
          case   33: case   36: case   41: case   49: case   57:
          case   64: case   65: case   68: case   73: case   81:
          case   89: case   97: case  100: case  105: case  113:
          case  121:
              long i = (n * INV3465) >>> 52;
              if (! good3465[(int) i]) {
                  return false;
              } else {
                  long r = runden(Math.sqrt(n));
                  return r*r == n; 
              }
          default:
              return false;
          }
      }
  }
  
  private static int runde(double x) {
      return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
  }
  
  /** 3465-1 Modulo 264 */
  private static final long INV3465 = 0x8ffed161732e78b9L;
  
  private static final boolean[] good3465 =
      new boolean[0x1000];
  
  static {
      for (int r = 0; r < 3465; ++ r) {
          int i = (int) ((r * r * INV3465) >>> 52);
          good3465[i] = good3465[i+1] = true;
      }
  }

  }