Wie kann ich mithilfe bitweiser Operationen schnell feststellen, ob eine große ganze Zahl ein perfektes Quadrat ist?

Obwohl der Algorithmus etwa 35 % schneller ist als der von Ihnen angegebene Code, können die tatsächlichen Ergebnisse zwischen verschiedenen CPUs (x86) und Programmiersprachen (C/C) variieren. Die Methode in diesem Artikel ist in drei Teile unterteilt:

1. Offensichtliche Antworten filtern: Negative Zahlen einschließen, die letzten 4 Ziffern überprüfen (ich habe festgestellt, dass die letzten 6 Ziffern überprüft werden). ist nicht hilfreich), Antwort 0. (Bitte beachten Sie beim Lesen des folgenden Codes, dass meine Eingabe ein int64 ist. Das Produkt zweier verschiedener Primzahlen, sodass das Quadratmodulo 255 nur einen Rest von etwa 1/8 hat. Meiner Erfahrung nach überwiegen jedoch die Kosten für die Verwendung des Modulo-Operators (%) die Vorteile, daher habe ich einen kleinen Trick mit 255 angewendet, um den Rest zu berechnen. (Gut oder schlecht, ich habe nicht den Trick angewendet, einzelne Bytes aus dem Wort abzulesen, sondern nur bitweises UND und Verschieben.)

   if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
       return false;
   if( x == 0 )
       return true;

Ich habe eine vorberechnete Tabelle verwendet, um tatsächlich zu überprüfen, ob der Rest eine Quadratzahl ist .

2. int64 y = x;
   y = (y & 4294967295LL) + (y >> 32); 
   y = (y & 65535) + (y >> 16);
   y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
   // At this point, y is between 0 and 511.  More code can reduce it farther.

   Ich versuche, die Quadratwurzel mit einer Methode zu berechnen, die Hensels Lemma ähnelt.

   : Vorher habe ich zwei verwendet Die Suche dividiert alle durch Zweierpotenzen erhöhten Reste:

   if( bad255[y] )
       return false;
   // However, I just use a table of size 512

Damit unsere Zahl an diesem Punkt eine Quadratzahl ist, muss ihr Modul 1 über 8 sein.

3. Die Grundstruktur von Hensels Lemma ist wie folgt. (Hinweis: ungetesteter Code; wenn das nicht funktioniert, versuchen Sie es mit t=2 oder 8.)

   if((x & 4294967295LL) == 0)
       x >>= 32;
   if((x & 65535) == 0)
       x >>= 16;
   if((x & 255) == 0)
       x >>= 8;
   if((x & 15) == 0)
       x >>= 4;
   if((x & 3) == 0)
       x >>= 2;

   Die Idee ist, dass Sie bei jeder Iteration ein Bit zu r hinzufügen, der Quadratwurzel von (Beachten Sie Folgendes: Wenn r die Quadratwurzel der Potenz von ist.) Da unsere tatsächliche Quadratwurzel kleiner als 2^32 ist, können wir an diesem Punkt tatsächlich prüfen, ob r oder t/2-r die tatsächliche Quadratwurzel von x ist. In meinem eigentlichen Code habe ich die folgende modifizierte Schleife verwendet:

   if((x & 7) != 1)
       return false;

   Der Geschwindigkeitsgewinn kann hier auf drei Arten erreicht werden: Vorberechneter Startwert (entspricht etwa 10 Schleifeniterationen), früheres Verlassen der Schleife und Überspringen Sie einige t-Werte. Für den letzten Teil beobachte ich z=r-x*x und verwende Bittricks, um t auf die größte Potenz von 2 dividiert durch z zu setzen. Dadurch kann ich die t-Werte überspringen, die ohnehin keinen Einfluss auf den r-Wert haben. Mein vorberechneter Startwert hat in meinem Fall die „am wenigsten positive“ Quadratwurzel Modulo 8192 ermittelt.

   int64 t = 4, r = 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   // Repeat until t is 2^33 or so.  Use a loop if you want.

   Auch wenn dieser Code bei Ihnen nicht schneller funktioniert, hoffe ich, dass Ihnen einige der Ideen gefallen. Der vollständige Testcode lautet wie folgt, einschließlich vorberechneter Tabellen.

   int64 r, t, z;
   r = start[(x >> 3) & 1023];
   do {
       z = x - r * r;
       if( z == 0 )
           return true;
       if( z < 0 )
           return false;
       t = z & (-z);
       r += (z & t) >> 1;
       if( r > (t >> 1) )
           r = t - r;
   } while( t <= (1LL << 33) );

Das obige ist der detaillierte Inhalt vonWie kann ich mithilfe bitweiser Operationen schnell feststellen, ob eine große ganze Zahl ein perfektes Quadrat ist?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!