Comment puis-je déterminer rapidement si un grand entier est un carré parfait à l'aide d'opérations au niveau du bit ?

Bien que l'algorithme soit environ 35 % plus rapide que le code que vous avez donné, les résultats réels peuvent varier selon les différents processeurs (x86) et langages de programmation (C/C). La méthode de cet article est divisée en trois parties :

1. Filtrer les réponses évidentes : inclure les nombres négatifs, vérifier les 4 derniers chiffres (il a été constaté que vérifier les 6 derniers chiffres n'est pas utile), répondez 0. (Lors de la lecture du code suivant, veuillez noter que mon entrée est un int64. Le produit de deux nombres premiers différents, donc le carré modulo 255 n'a qu'un reste d'environ 1/8. Cependant, d'après mon expérience, les coûts d'utilisation de l'opérateur modulo (%) dépassent les avantages, j'ai donc utilisé une petite astuce impliquant 255 pour calculer le reste. (Mieux ou pire, je n'ai pas utilisé l'astuce consistant à lire les octets individuels du mot, juste ET au niveau du bit et en décalant.)

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

J'ai utilisé une table précalculée pour vérifier si le reste est un nombre carré. .

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.

   Essayer de calculer la racine carrée en utilisant une méthode similaire au lemme de Hensel

    : Avant cela, j'utilisais deux La recherche divise tous les restes élevés par des puissances de 2 :

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

À ce stade, pour que notre nombre soit un nombre carré, son module doit être 1 sur 8.

3. La structure de base du lemme de Hensel est la suivante. (Remarque : code non testé ; si cela ne fonctionne pas, essayez t=2 ou 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;

   L'idée est qu'à chaque itération, vous ajoutez un bit à r," La racine carrée de (Notez que si r est la racine carrée de la puissance de .) Puisque notre racine carrée réelle est inférieure à 2 ^ 32, nous pouvons alors vérifier si r ou t/2-r est la racine carrée réelle de x. Dans mon code actuel, j'ai utilisé la boucle modifiée suivante :

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

   Le gain de vitesse ici peut être obtenu de trois manières : valeur de départ précalculée (équivalente à environ 10 itérations de boucle), quitter la boucle plus tôt et ignorez certaines valeurs t. Pour la dernière partie, j'observe z=r-x*x et j'utilise des astuces pour régler t à la plus grande puissance de 2 divisée par z. Cela me permet d'ignorer les valeurs t qui n'affectent pas la valeur r de toute façon. Ma valeur de départ précalculée a sélectionné la racine carrée "la moins positive" modulo 8192 dans mon cas.

   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.

   Même si ce code ne fonctionne pas pour vous plus rapidement, j'espère que vous apprécierez certaines des idées. Le code de test complet est le suivant, y compris les tableaux précalculés.

   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) );

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!