Wie können wir effizient bestimmen, ob eine große Zahl ein perfektes Quadrat ist?

Führen Sie zu Beginn des Programms eine Vorfilterung durch, um den Vorgang zu beschleunigen und offensichtliche nichtquadratische Zahlen herauszufiltern, einschließlich negativer Zahlen und Zahlen, deren letzte 4 Ziffern 0 sind und Zahlen, deren letzte beiden Ziffern bestimmte Anforderungen erfüllen. Die Nummer der Bedingung (5 oder 8 in Dezimalzahl). Stellen Sie sich 0 als Quadratzahl vor.

Als nächstes prüfen Sie mit bitweisen Verfahren, ob der Rest von Modulo 255 = 3 = 3 5 17 eine Quadratzahl ist. Das Array bad255 zeichnet auf, ob jeder Rest eine Quadratzahl ist den Tisch hoch.

Für Zahlen, die den Vorfilter bestehen, dividieren Sie durch alle Potenzen von 2 (in einer binären Suchmethode), bis der Quotient ungerade ist.

Der letzte Schritt besteht darin, die Quadratwurzel mit einer Methode ähnlich dem Hensel-Lemma zu approximieren. Die innere Schleife beginnt mit einem durch das Startarray vorgegebenen Anfangswert, der eine Annäherung an sqrt (mod 8192) liefert. Diese Näherung wird durch aufeinanderfolgende Berechnungen kontinuierlich verbessert, wobei bitweise Tricks zur Verbesserung der Geschwindigkeit eingesetzt werden.

Die grobe Struktur dieser Methode ist wie folgt:

1. Vorfilter zum Entfernen offensichtlicher nichtquadratischer Zahlen.
2. Prüfen Sie, ob der Rest modulo 255 eine Quadratzahl ist.
3. Geteilt durch eine Potenz von 2.
4. Berechnen Sie Quadratwurzeln näherungsweise mithilfe einer Variante des Hensel-Lemmas.

Es ist erwähnenswert, dass der Autor dieses Algorithmus behauptet, dass er 35 % schneller läuft als andere Methoden.

Das obige ist der detaillierte Inhalt vonWie können wir effizient bestimmen, ob eine große Zahl ein perfektes Quadrat ist?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!