Comment puis-je réduire la division de 2^n + 1?

Question

J'ai besoin d'effectuer des divisions entières dans le chemin chaud de mon code. J'ai déjà déterminé via le profilage et le comptage de cycles que les divisions entières me coûtent. J'espère qu'il y a quelque chose que je peux faire pour réduire les divisions en quelque chose de moins cher.

Dans ce chemin, je divise par 2^n + 1, où n est variable. Essentiellement, je veux optimiser cette fonction pour supprimer l'opérateur de division:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    return a/((1 << n) + 1); 
} 

Si je division par 2^n, je remplacerais juste le div avec un décalage à droite par n. Si je divisais par une constante, je laisserais la force du compilateur réduire cette division spécifique, la transformant probablement en une multiplication et quelques changements.

Y a-t-il une optimisation similaire qui s'applique à 2^n + 1?

Édition: il peut y avoir un entier arbitraire de 64 bits. n ne prend que quelques valeurs entre 10 et, disons, 25. Je peux certainement précalculer certaines valeurs pour chaque n, mais pas pour a.

Answer 1

Puisque vous ne pouvez déplacer un int tant d'endroits, vous pouvez mettre tous les cas dans le choix d'un de plusieurs divisions par une constante:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader): 
    switch (n) { 
     case 0: return a/((1 << 0) + 1); 
     case 1: return a/((1 << 1) + 1); 
     case 2: return a/((1 << 2) + 1); 

      // cases 3 through 30... 

     case 31: return a/((1 << 31) + 1); 
    } 
} 

Alors maintenant, chaque division est par une constante, qui Les compilateurs réduisent généralement à une série d'instructions multiplier/déplacer/ajouter (comme la question mentionnée). Voir Does a c/c++ compiler optimize constant divisions by power-of-two value into shifts? pour deatils.

Answer 2

Vous pouvez remplacer la division entière par une constante, par multiplication (modulo wordsize) avec un nombre magique et un décalage.

Les nombres magiques peuvent être précalculés pour des constantes connues.

Puisque n ne peut pas prendre de nombreuses valeurs, par ex. 0..31 il est "facile" de pré-calculer ces nombres magiques pour tout n et de les stocker dans un tableau avec 32 éléments.

Javascript Page for calculating the magic numbers

Un bon compilateur peut calculer les nombres magiques et remplacer la division entière par multiplication et décalage si le diviseur est constant au moment de la compilation. Selon comment le reste du code est structuré autour du code critique de performance, vous pouvez utiliser des astuces macro ou inline pour dérouler toutes les valeurs possibles de n et laisser le compilateur faire le travail de trouver les nombres magiques (similaire à la réponse avec le commutateur, mais je mettrais plus de code dans la région constante sinon il pourrait être un tradeof ne vaut pas la peine - branchement peut vous coûter des performances aussi)

Une description détaillée avec le code pour calculer les nombres magiques peut être financée dans le Livre "Hackers Delight" par Henry S. Warren, Jr. (fortement recommandé doit avoir livre!) pp. 180ff.

Lien vers Google Livres pour le chapitre concerné:

Chapter 10-9 Unsigned Division by Divisors >= 1