Existe-t-il une alternative à l’utilisation de% (module) en C / C ++?

J’ai lu quelque part une fois que l’opérateur de module est inefficace sur de petits dispositifs intégrés, tels que des micro-contrôleurs 8 bits qui ne possèdent pas d’instruction de division entière. Quelqu’un peut peut-être confirmer cela, mais je pensais que la différence était 5-10 fois plus lente qu’avec une opération de division entière.

Y a-t-il un autre moyen de faire cela autre que garder une variable de compteur et déborder manuellement à 0 au sharepoint modification?

const int FIZZ = 6; for(int x = 0; x < MAXCOUNT; x++) { if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems } 

contre:

La façon dont je le fais actuellement:

 const int FIZZ = 6; int fizzcount = 1; for(int x = 1; x = FIZZ) { print("Fizz\n"); fizzcount = 0; } } 

Ah, les joies de l’arithmétique au niveau des bits. Le module est l’un des effets secondaires de nombreuses routines de division. Il est donc rare que la division soit réellement plus rapide que le module. Je suis intéressé de voir la source d’où vous avez obtenu cette information. Les processeurs avec multiplicateurs ont des routines de division intéressantes utilisant le multiplicateur, mais vous pouvez passer du résultat de la division au module en seulement deux étapes supplémentaires (multiplier et soustraire), de sorte que le résultat rest comparable. Si le processeur a une routine de division intégrée, vous verrez probablement le rest.

Néanmoins, il existe une petite twig de la théorie des nombres consacrée à l’ arithmétique modulaire, qui nécessite une étude si vous voulez vraiment comprendre comment optimiser une opération de module. L’arithmatique modulaire, par exemple, est très pratique pour générer des carrés magiques .

Donc, dans cette optique, voici un aperçu très bas du calcul du module pour un exemple de x, ce qui devrait vous montrer à quel point il peut être comparé à la division:


Peut-être une meilleure façon de réfléchir au problème est-elle en termes de bases de nombres et d’arithmétique modulo. Par exemple, votre objective est de calculer DOW mod 7, où DOW est la représentation 16 bits du jour de la semaine. Vous pouvez écrire ceci comme:

  DOW = DOW_HI*256 + DOW_LO DOW%7 = (DOW_HI*256 + DOW_LO) % 7 = ((DOW_HI*256)%7 + (DOW_LO % 7)) %7 = ((DOW_HI%7 * 256%7) + (DOW_LO%7)) %7 = ((DOW_HI%7 * 4) + (DOW_LO%7)) %7 

Exprimé de cette manière, vous pouvez calculer séparément le résultat du modulo 7 pour les octets haut et bas. Multipliez le résultat pour le haut par 4 et ajoutez-le au bas puis calculez finalement le résultat modulo 7.

Le calcul du résultat mod 7 d’un nombre à 8 bits peut être effectué de manière similaire. Vous pouvez écrire un nombre à 8 bits en octal comme ceci:

  X = a*64 + b*8 + c 

Où a, b et c sont des nombres à 3 bits.

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7 = (a%7 + b%7 + c%7) % 7 = (a + b + c) % 7 

depuis 64%7 = 8%7 = 1

Bien sûr, a, b et c sont

  c = X & 7 b = (X>>3) & 7 a = (X>>6) & 7 // (actually, a is only 2-bits). 

La plus grande valeur possible pour a+b+c est 7+7+3 = 17 . Donc, vous aurez besoin d’un pas de plus octal. La version C complète (non testée) pourrait être écrite comme suit:

 unsigned char Mod7Byte(unsigned char X) { X = (X&7) + ((X>>3)&7) + (X>>6); X = (X&7) + (X>>3); return X==7 ? 0 : X; } 

J’ai passé quelques instants à écrire une version PIC. La mise en œuvre réelle est légèrement différente de celle décrite ci-dessus

 Mod7Byte: movwf temp1 ; andlw 7 ;W=c movwf temp2 ;temp2=c rlncf temp1,F ; swapf temp1,W ;W= a*8+b andlw 0x1F addwf temp2,W ;W= a*8+b+c movwf temp2 ;temp2 is now a 6-bit number andlw 0x38 ;get the high 3 bits == a' xorwf temp2,F ;temp2 now has the 3 low bits == b' rlncf WREG,F ;shift the high bits right 4 swapf WREG,F ; addwf temp2,W ;W = a' + b' ; at this point, W is between 0 and 10 addlw -7 bc Mod7Byte_L2 Mod7Byte_L1: addlw 7 Mod7Byte_L2: return 

Voici une petite routine pour tester l’algorithme

  clrf x clrf count TestLoop: movf x,W RCALL Mod7Byte cpfseq count bra fail incf count,W xorlw 7 skpz xorlw 7 movwf count incfsz x,F bra TestLoop passed: 

Enfin, pour le résultat 16 bits (que je n’ai pas testé), vous pouvez écrire:

 uint16 Mod7Word(uint16 X) { return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4); } 

Scott


Si vous calculez un nombre mod d’une puissance de deux, vous pouvez utiliser le bit et l’opérateur. Soustrayez simplement un du deuxième nombre. Par exemple:

 x % 8 == x & 7 x % 256 == x & 255 

Quelques mises en garde:

  1. Cela ne fonctionne que si le deuxième nombre est une puissance de deux.
  2. Ce n’est équivalent que si le module est toujours positif. Les normes C et C ++ ne spécifient pas le signe du module lorsque le premier nombre est négatif (jusqu’au C ++ 11, ce qui garantit qu’il sera négatif, ce que faisaient déjà la plupart des compilateurs). Un peu sage et se débarrasse du bit de signe, il sera donc toujours positif (c’est-à-dire qu’il s’agit d’un vrai module, pas d’un rest). On dirait que c’est ce que vous voulez quand même.
  3. Votre compilateur le fait probablement déjà quand il le peut, donc dans la plupart des cas, il ne vaut pas la peine de le faire manuellement.

La plupart du temps, l’utilisation de modulo entraîne une surcharge qui ne correspond pas à la puissance 2. C’est quel que soit le processeur utilisé (autant que je sache (AFAIK)), même les processeurs dotés d’opérateurs de module sont plus lents que les opérations de division par rapport aux opérations de masque.

Dans la plupart des cas, il ne s’agit pas d’une optimisation à considérer, ni du calcul de votre propre opération de raccourci (surtout si elle implique toujours une division ou une multiplication).

Cependant, une règle empirique consiste à sélectionner des tailles de tableau, etc.

Ainsi, si vous calculez le jour de la semaine, vous pouvez également utiliser% 7, que vous configuriez un tampon circulaire d’environ 100 entrées … pourquoi ne pas en définir 128. Vous pouvez alors écrire% 128 et la plupart des compilateurs effectueront ceci & 0x7F

Sauf si vous avez vraiment besoin de hautes performances sur plusieurs plates-formes intégrées, ne modifiez pas la manière dont vous codez pour des raisons de performance avant de vous profiler!

Le code mal écrit pour optimiser les performances est difficile à déboguer et à maintenir. Rédigez un scénario de test et définissez-le sur votre cible. Une fois que vous connaissez le coût réel du module, décidez ensuite si la solution de rechange vaut la peine d’être codée.

@ Matthew a raison. Essaye ça:

 int main() { int i; for(i = 0; i<=1024; i++) { if (!(i & 0xFF)) printf("& i = %d\n", i); if (!(i % 0x100)) printf("mod i = %d\n", i); } } 
 x%y == (x-(x/y)*y) 

J’espère que cela t’aides.

Dans le monde embarqué, les opérations de “module” que vous devez effectuer sont souvent celles qui se décomposent joliment en opérations que vous pouvez effectuer avec “&” et “|”. et parfois ‘>>’.

Avez-vous access à du matériel programmable sur le périphérique intégré? Comme des comptoirs et autres? Si tel est le cas, vous pourrez peut-être écrire une unité de modement basée sur le matériel, au lieu d’utiliser le% simulé. (Je l’ai déjà fait une fois en VHDL. Je ne sais pas si j’ai toujours le code.)

Remarquez, vous avez bien dit que la division était 5-10 fois plus rapide. Avez-vous envisagé de faire une division, une multiplication et une soustraction pour simuler le mod? (Edit: mal compris le post original. Je pensais qu’il était étrange que la division fût plus rapide que le mod, c’est la même opération.)

Cependant, dans votre cas spécifique, vous recherchez un mod de 6. 6 = 2 * 3. Vous pourriez donc obtenir de petits gains si vous avez d’abord vérifié si le bit le moins significatif était un 0. Quelque chose comme:

 if((!(x & 1)) && (x % 3)) { print("Fizz\n"); } 

Si vous faites cela, cependant, je vous recommanderais de confirmer que vous obtenez des gains, yay pour les profileurs. Et faire des commentaires. Je me sentirais mal pour le prochain gars qui doit regarder le code autrement.

Vous devriez vraiment vérifier le périphérique intégré dont vous avez besoin. Tous les langages d’assemblage que j’ai vus (x86, 68000) implémentent le module à l’aide d’une division.

En réalité, l’opération d’assemblage de la division renvoie le résultat de la division et le rest dans deux registres différents.

Ce n’est pas forcément mieux, mais vous pouvez avoir une boucle interne qui monte toujours jusqu’à FIZZ et une boucle externe qui le répète tous un certain nombre de fois. Vous avez alors peut-être des cas particuliers pour les dernières étapes si MAXCOUNT n’est pas divisible de manière égale par FIZZ.

Cela dit, je vous suggérerais de faire de la recherche et d’établir un profil de performance sur les plates-formes auxquelles vous êtes destiné pour avoir une idée précise des contraintes de performance auxquelles vous êtes soumis. Il peut y avoir des endroits beaucoup plus productifs où dépenser vos efforts d’optimisation.

@ Jeff V: Je vois un problème avec ça! (Au-delà de cela, votre code d’origine cherchait un mod 6 et maintenant vous cherchez essentiellement un mod 8). Vous continuez à faire un +1 supplémentaire! Espérons que votre compilateur optimise cela, mais pourquoi ne pas simplement commencer à 2 et aller à MAXCOUNT inclus? Enfin, vous retournez vrai chaque fois que (x + 1) n’est PAS divisible par 8. Est-ce ce que vous voulez? (Je suppose que c’est le cas, mais je veux juste confirmer.)

L’instruction print prendra des ordres de grandeur plus longs que même l’implémentation la plus lente de l’opérateur de module. Donc, fondamentalement, le commentaire “lent sur certains systèmes” devrait être “lent sur tous les systèmes”.

De plus, les deux extraits de code fournis ne font pas la même chose. Dans le second, la ligne

  si (fizzcount> = FIZZ) 

est toujours faux, donc “FIZZ \ n” n’est jamais imprimé.