Existe-t-il une alternative à l’utilisation de % (module) en C/C++ ?
https://stackoverflow.com/questions/48053
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai lu quelque part une fois que l'opérateur de module est inefficace sur les petits appareils embarqués comme les microcontrôleurs 8 bits qui n'ont pas d'instruction de division entière.Peut-être que quelqu'un pourra le confirmer, mais je pensais que la différence était 5 à 10 fois plus lente qu'avec une opération de division entière.
Existe-t-il un autre moyen de procéder autre que de conserver une variable de compteur et de la faire déborder manuellement à 0 au point de mod ?
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 < MAXCOUNT; x++)
{
if(fizzcount >= FIZZ)
{
print("Fizz\n");
fizzcount = 0;
}
}
La solution
Ah, les joies de l'arithmétique au niveau du bit.Un effet secondaire de nombreuses routines de division est le module - donc dans quelques cas, la division devrait être 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), donc c'est toujours comparable.Si le processeur dispose d'une routine de division intégrée, vous verrez probablement qu'il fournit également le reste.
Il existe néanmoins une petite branche de la théorie des nombres consacrée à Arithmétique modulaire ce qui nécessite d'être étudié si l'on veut vraiment comprendre comment optimiser un fonctionnement de module.L'arithmatique modulaire, par exemple, est très pratique pour générer carrés magiques.
Alors, dans cette optique, voici un look de très bas niveau aux mathématiques du module pour un exemple de x, qui devrait vous montrer à quel point cela peut être simple par rapport à la division :
Peut-être qu'une meilleure façon de penser au problème est en termes de bases numériques et d'arithmétique modulo.Par exemple, votre objectif est de calculer Dow Mod 7 où Dow est la représentation 16 bits du jour de la semaine.Vous pouvez écrire ceci comme suit :
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 modulo 7 pour les octets élevés et bas.Multipliez le résultat pour le haut de 4 et ajoutez-le au faible puis calculez finalement le modulo de résultat 7.
Le calcul du résultat MOD 7 d'un numéro 8 bits peut être effectué de manière similaire.Vous pouvez écrire un nombre de 8 bits en octal comme ceci :
X = a*64 + b*8 + c
Où a, b et c sont des nombres de 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'une étape octale de plus.La version C complète (non testée) pourrait être écrite comme:
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 pourriez écrire:
uint16 Mod7Word(uint16 X)
{
return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}
Scott
Autres conseils
Si vous calculez un nombre mod d'une puissance de deux, vous pouvez utiliser l'opérateur bit-wise et.Soustrayez simplement un du deuxième nombre.Par exemple:
x % 8 == x & 7
x % 256 == x & 255
Quelques mises en garde :
- Ce ne fonctionne que si le deuxième nombre est une puissance de deux.
- Ce n'est équivalent que si le module est toujours positif.Les standards C et C++ ne précisent pas le signe du module lorsque le premier nombre est négatif (jusqu'au C++11, qui fait garantir qu'il sera négatif, ce que faisaient déjà la plupart des compilateurs).Un peu au niveau du bit et supprime le bit de signe, il sera donc toujours positif (c'est-à-direc'est un vrai module, pas un reste).On dirait que c'est ce que vous voulez de toute façon.
- Votre compilateur le fait probablement déjà lorsqu'il le peut, donc dans la plupart des cas, cela ne vaut pas la peine de le faire manuellement.
Il y a la plupart du temps une surcharge liée à l'utilisation de modulo qui ne sont pas des puissances de 2.Ceci quel que soit le processeur car (AFAIK) même les processeurs avec opérateurs de module sont quelques cycles plus lents pour les opérations de division que pour les opérations de masquage.
Dans la plupart des cas, ce n'est pas une optimisation qui mérite d'être envisagée, et certainement pas la peine de calculer votre propre opération de raccourci (surtout si cela implique toujours de diviser ou de multiplier).
Cependant, une règle générale consiste à sélectionner la taille des tableaux, etc.être des puissances de 2.
Donc, en cas de calcul du jour de la semaine, peut aussi bien utiliser% 7, peu importe si la configuration d'un tampon circulaire d'environ 100 entrées ...pourquoi ne pas en faire 128.Vous pouvez ensuite écrire % 128 et la plupart (tous) les compilateurs feront ceci & 0x7F
À moins que vous n'ayez vraiment besoin de hautes performances sur plusieurs plates-formes embarquées, ne modifiez pas la façon dont vous codez pour des raisons de performances jusqu'à ce que vous établissiez votre profil !
Le code mal écrit pour optimiser les performances est difficile à déboguer et à maintenir.Rédigez un scénario de test et profilez-le sur votre cible.Une fois que vous connaissez le coût réel du module, décidez si la solution alternative vaut la peine d'être codée.
@Matthieu 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 intégré, les opérations de "module" que vous devez faire sont souvent celles qui se décomposent bien en opérations bit que vous pouvez faire avec '&' et '|' et parfois '>>'.
Avez-vous accès à du matériel programmable sur le périphérique intégré ?Comme les compteurs et autres ?Si tel est le cas, vous pourrez peut-être écrire une unité de mod basée sur le matériel, au lieu d'utiliser le % simulé.(Je l'ai fait une fois en VHDL.Je ne sais pas si j'ai toujours le code.)
Attention, vous avez 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 ?(Modifier:J'ai mal compris le message d'origine.J'ai trouvé étrange que la division soit plus rapide que le mod, c'est la même opération.)
Dans votre cas spécifique, cependant, vous recherchez un mod de 6.6 = 2*3.Vous pourriez donc PEUT-ÊTRE obtenir de petits gains si vous vérifiiez d'abord 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 recommande de confirmer que vous obtenez des gains, oui pour les profileurs.Et faire quelques commentaires.Je me sentirais mal pour le prochain gars qui devrait autrement regarder le code.
Vous devriez vraiment vérifier le périphérique intégré dont vous avez besoin.Tous les langages assembleur que j'ai vus (x86, 68000) implémentent le module en utilisant une division.
En fait, l'opération d'assemblage de division renvoie le résultat de la division et le reste dans deux registres différents.
Non pas que ce soit nécessairement mieux, mais vous pourriez avoir une boucle interne qui monte toujours jusqu'à FIZZ, et une boucle externe qui répète le tout un certain nombre de fois.Vous devrez peut-être alors suivre un cas particulier pour les dernières étapes si MAXCOUNT n'est pas divisible de manière égale par FIZZ.
Cela dit, je suggère de faire des recherches et un profilage des performances sur les plates-formes que vous envisagez pour avoir une idée claire des contraintes de performances auxquelles vous êtes soumis.Il existe peut-être des domaines beaucoup plus productifs où consacrer vos efforts d’optimisation.
@JeffV :J'y vois un problème !(Au-delà de cela, votre code d'origine recherchait un mod 6 et maintenant vous recherchez essentiellement un mod 8).Vous continuez à faire un +1 supplémentaire !Espérons que votre compilateur optimise cela, mais pourquoi ne pas simplement tester le démarrage à 2 et passer à MAXCOUNT inclus ?Enfin, vous renvoyez vrai chaque fois que (x+1) n'est PAS divisible par 8.Est-ce que c'est ce que tu veux?(Je suppose que oui, mais je veux juste confirmer.)
Pour le modulo 6, vous pouvez changer le code Python en C/C++ :
def mod6(number):
while number > 7:
number = (number >> 3 << 1) + (number & 0x7)
if number > 5:
number -= 6
return number
L'instruction d'impression 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
if(fizzcount >= FIZZ)
est toujours faux donc "FIZZ " n'est jamais imprimé.
