Comment vérifier si un entier est une puissance de 3?

Question

J'ai vu cette question et fait surgir cette idée.

Answer 1

Il existe une méthode assez rapide pour les entiers de taille limitée (par exemple les entiers 32 bits).

Notez que pour un entier N qui est une puissance de 3, ce qui suit est vrai:

1. Pour tout M <= N qui est une puissance de 3, M divise N.
2. Pour tout M <= N qui n'est pas une puissance 3, M ne divise pas N.

La plus grande puissance de 3 compatible avec 32 bits est 3486784401 . Cela donne le code suivant:

 bool isPower3(std::uint32_t value) {
    return value != 0 && 3486784401u % value == 0;
}
 

Answer 2

 while (n % 3 == 0) {
    n /= 3;
}
return n == 1;
 

Notez que 1 est le pouvoir zéro de trois.

Edit: Vous devez également vérifier la valeur zéro avant la boucle, car celle-ci ne se terminera pas pour n = 0 (grâce à Bruno Rothgiesser).

Answer 3

Je me trouve un peu en train de penser que si par "entier", vous voulez dire "entier signé de 32 bits", alors (pseudocode)

 return (n == 1) 
    or (n == 3)
    or (n == 9)
    ... 
    or (n == 1162261467)
 

a une certaine belle simplicité (le dernier chiffre est 3 ^ 19, il n’ya donc pas un nombre absurde de cas). Même pour un entier non signé de 64 bits, il ne reste plus que 41 cas (merci à Alexandru de m'avoir signalé un casse-tête). Et bien sûr, serait impossible pour une arithmétique de précision arbitraire ...

Answer 4

Je suis surpris de voir à présent. Tout le monde semble avoir manqué l'algorithme le plus rapide de tous.

L'algorithme suivant est en moyenne plus vite et beaucoup plus rapide dans certains cas - qu'un simple while(n%3==0) n/=3; boucle:

bool IsPowerOfThree(uint n)
{
  // Optimizing lines to handle the most common cases extremely quickly
  if(n%3 != 0) return n==1;
  if(n%9 != 0) return n==3;

  // General algorithm - works for any uint
  uint r;
  n = Math.DivRem(n, 59049, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r, 243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;
}

Les constantes numériques dans le code sont 3^10, 3^5, et 3^3.

Les calculs de la Performance

Dans les Processeurs modernes, DivRem est souvent la seule instruction qui prend un cycle. Sur d'autres, il se développe à une div suivie par une mul et un complément, qui seraient prend plus de trois cycles au total. Chaque étape de l'algorithme général semble longue mais en fait il est uniquement constitué de: DivRem, cmp, cmove, cmp, cand, cjmp, add. Il y a beaucoup de parallélisme disponible, donc sur un type de deux-chemin superscalar processeur de chaque étape sera probablement exécuter en 4 cycles d'horloge, donnant une garantie des cas les pires temps d'exécution d'environ 25 cycles d'horloge.

Si les valeurs d'entrée sont répartis uniformément sur toute la gamme de UInt32, voici les probabilités associées avec cet algorithme:

• De retour dans le ou avant le premier optimisation de la ligne: 66% du temps
• De retour dans le ou avant le deuxième optimisation de la ligne: 89% du temps
• De retour dans le ou avant le premier algorithme général de l'étape: de 99,998% du temps
• De retour à ou avant la deuxième étape de l'algorithme: 99.99998% du temps
• De retour dans le ou avant le troisième algorithme général de l'étape: 99.999997% du temps

Cet algorithme est plus performante que la simple while(n%3==0) n/=3 boucle, qui a les probabilités suivantes:

• De retour dans la première itération: 66% du temps
• De retour dans les deux premières itérations: 89% du temps
• De retour dans les trois premières itérations: 97% du temps
• De retour dans les quatre premières itérations: 98.8% du temps
• De retour dans les cinq premières itérations: 99,6% du temps ... et ainsi de suite ...
• De retour dans la première période de douze itérations: 99,9998% des temps ... et au-delà ...

Ce qui est peut-être encore plus important, cet algorithme gère les moyennes et les grandes puissances de trois (et leurs multiples) beaucoup plus efficacement: Dans le pire des cas, l'algorithme simple consomment plus de 100 cycles de CPU, car il sera en boucle de 20 fois (41 fois pour 64 bits). L'algorithme que je présente ici ne seront jamais prendre plus que d'environ 25 cycles.

L'extension à 64 bits

L'extension de l'algorithme ci-dessus à 64 bits est simple - il suffit d'ajouter une étape de plus. Voici une version 64 bits de l'algorithme ci-dessus optimisé pour les processeurs efficace sans la 64 bits de la division:

bool IsPowerOfThree(ulong nL)
{
  // General algorithm only
  ulong rL;
  nL = Math.DivRem(nL, 3486784401, out rL); if(nL!=0 && rL!=0) return false;
  nL = Math.DivRem(nL+rL,   59049, out rL); if(nL!=0 && rL!=0) return false;
  uint n = (uint)nL + (uint)rL;
  n = Math.DivRem(n,   243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;

}

La nouvelle constante est 3^20. L'optimisation des lignes sont omis dans le haut de la méthode, car, en vertu de notre hypothèse que la version 64 bits de la division est lent, ils pourraient ralentir les choses.

Pourquoi cette technique fonctionne

Dire je veux savoir si "100000000000000000" est une puissance de 10. Je pourrais suivre ces étapes:

1. Je le divise par 10^10 et obtenir un quotient de 10000000 et un reste de 0. Ces ajouter à 10000000.
2. Je le divise par 10^5 et obtenir un quotient de 100 et un reste de 0. Ceux-ci ajoutent à 100.
3. Je le divise par 10^3 et obtenir un quotient de 0 et un remainderof 100. Ceux-ci ajoutent à 100.
4. Je le divise par 10^2 et d'obtenir un quotient de 1 et un reste de 0. Ceux-ci ajoutent à 1.

Parce que j'ai commencé avec une puissance de 10, à chaque fois que j'ai divisé par une puissance de 10 je me suis retrouvé avec un zéro quotient ou un zéro reste. Avais-je commencé avec rien, sauf une puissance de 10, j'aurais tôt ou tard, il a terminé avec une différente de zéro quotient ou de ce qui reste.

Dans cet exemple j'ai choisi exposants de 10, 5 et 3 pour correspondre le code fourni précédemment, et a ajouté 2 juste pour le fun. D'autres représentants également de travailler: Il existe un algorithme simple pour la sélection de l'idéal exposants, compte tenu de votre maximum de la valeur d'entrée et la puissance maximale de 10 a permis à la sortie, mais cette marge n'a pas assez de place pour le contenir.

REMARQUE: Vous pouvez avoir été pensée en base dix tout au long de cette explication, mais l'ensemble de l'explication ci-dessus peut être lu et compris à l'identique si vous êtes en train de penser dans la base de trois, sauf les exposants aurait été exprimées différemment (au lieu de "10", "5", "3" et "2", je dois dire "101", "12", "10" et "2").

Answer 5

si (log n) / (log 3) est intégrale, alors n est une puissance de 3.