Le moyen le plus optimisé pour calculer le module en C

J’ai minimisé le coût de calcul du module dans C. disons que j’ai un nombre x et n est le nombre qui divisera x

quand n == 65536 (soit 2 ^ 16):

mod = x% n (11 instructions d’assemblage produites par GCC) ou
mod = x & 0xffff qui est égal à mod = x & 65535 (4 instructions d’assemblage)

Donc, GCC ne l’optimise pas dans cette mesure.

Dans mon cas, n n’est pas x ^ (int) mais est le plus grand nombre premier inférieur à 2 ^ 16, qui est 65521

comme je l’ai montré pour n == 2 ^ 16, les opérations binarys peuvent optimiser le calcul. Quelles opérations par bits puis-je effectuer lorsque n == 65521 calcule le module.

Premièrement, assurez-vous de regarder le code optimisé avant de tirer une conclusion sur ce que GCC produit (et assurez-vous que cette expression particulière doit vraiment être optimisée). Enfin – ne comptez pas les instructions pour tirer vos conclusions; il se peut qu’une séquence d’instructions à 11 instructions donne de meilleurs résultats qu’une séquence plus courte comprenant une instruction div.

En outre, vous ne pouvez pas en conclure que, car x mod 65536 peut être calculé avec un simple masque de bits, toute opération de modement peut être mise en œuvre de cette manière. Considérez à quel point il est facile de diviser par 10 en décimal plutôt que par un nombre arbitraire.

Avec tout ce qui se cache, vous pourrez peut-être utiliser certaines des techniques du «nombre magique» du livre Hacker’s Delight de Henry Warren:

Il y a un chapitre ajouté sur le site Web qui contient “deux méthodes de calcul du rest de la division sans calculer le quotient!”, Que vous pouvez trouver utile. La première technique ne s’applique qu’à un nombre limité de diviseurs, elle ne fonctionnera donc pas pour votre instance particulière. En fait, je n’ai pas lu le chapitre en ligne, alors je ne sais pas exactement dans quelle mesure l’autre technique pourrait vous être applicable.

x mod 65536 n’est équivalent à x & 0xffff que si x est non signé – pour x signé, il donne un résultat erroné pour les nombres négatifs. Pour x non signé, gcc optimise en effet x % 65536 sur un bit et avec 65535 (même sur -O0, dans mes tests).

Comme 65521 n’est pas une puissance de 2, x mod 65521 ne peut pas être calculé aussi simplement. gcc 4.3.2 sur -O3 le calcule en utilisant x - (x / 65521) * 65521 ; la division entière par une constante est effectuée en utilisant la multiplication d’entier par une constante associée.

Si vous n’êtes pas obligé de réduire complètement vos entiers modulo 65521, vous pouvez utiliser le fait que 65521 est proche de 2 ** 16. En d’autres termes, si x est un entier non signé que vous souhaitez réduire, vous pouvez procéder comme suit:

 unsigned int low = x &0xffff; unsigned int hi = (x >> 16); x = low + 15 * hi; 

Ceci utilise 2 ** 16% 65521 == 15. Notez qu’il ne s’agit pas d’une réduction complète. En commençant par une entrée 32 bits, il vous est uniquement garanti que le résultat obtenu est au maximum de 20 bits et qu’il est bien entendu conforme à l’entrée modulo 65521.

Cette astuce peut être utilisée dans des applications où il existe de nombreuses opérations qui doivent être réduites modulo à la même constante et où les résultats intermédiaires ne doivent pas nécessairement être le plus petit élément de sa classe de résidus.

Par exemple, une application est l’implémentation d’Adler-32, qui utilise le module 65521. Cette fonction de hachage effectue de nombreuses opérations modulo 65521. Pour la mettre en œuvre efficacement, il ne faudrait effectuer des réductions modulaires qu’après un nombre d’ajouts soigneusement calculé. Une réduction indiquée ci-dessus suffit et seul le calcul du hachage nécessitera une opération modulo complète.

L’opération au niveau du bit ne fonctionne bien que si le diviseur est de la forme 2^n . Dans le cas général, ce type d’opération n’existe pas.

Si la constante avec laquelle vous voulez utiliser le modulo est connue au moment de la compilation et que vous avez un compilateur décent (par exemple, gcc), il est généralement préférable de laisser le compilateur fonctionner comme par magie. Il suffit de déclarer le modulo const.

Si vous ne connaissez pas la constante au moment de la compilation, mais que vous allez prendre – disons – un milliard de modulos avec le même nombre, utilisez alors http://libdivide.com/

En tant qu’approche lorsque nous traitons avec des puissances de 2, on peut considérer celle-ci (principalement à saveur de C):

 . . #define THE_DIVISOR 0x8U; /* The modulo value (POWER OF 2). */ . . uint8 CheckIfModulo(const sint32 TheDividend) { uint8 RetVal = 1; /* TheDividend is not modulus THE_DIVISOR. */ if (0 == (TheDividend & (THE_DIVISOR - 1))) { /* code if modulo is satisfied */ RetVal = 0; /* TheDividend IS modulus THE_DIVISOR. */ } else { /* code if modulo is NOT satisfied */ } return RetVal; } 

Si x est un index croissant et que l’incrément i est connu pour être inférieur à n (par exemple, lors d’une itération sur un tableau circulaire de longueur n ), évitez complètement le module. Une boucle va

 x += i; if (x >= n) x -= n; 

est bien plus rapide que

 x = (x + i) % n; 

que vous trouverez malheureusement dans de nombreux manuels …

Si vous avez vraiment besoin d’une expression (par exemple parce que vous l’utilisez dans une instruction for ), vous pouvez utiliser la méthode laide mais efficace.

 x = x + (x+i < n ? i : in) 

idiv – Division entière

L’instruction idiv divise le contenu du nombre entier 64 bits EDX: EAX (construit en considérant EDX comme les quatre octets les plus significatifs et EAX comme les quatre octets les moins significatifs) par la valeur d’opérande spécifiée. Le résultat du quotient de la division est stocké dans EAX, tandis que le rest est placé dans EDX .

source: http://www.cs.virginia.edu/~evans/cs216/guides/x86.html

Implémentation la moins coûteuse de Modulus in C


Que diriez-vous d’implémenter MOD comme suit:

Pour trouver: y = X mod n

 y = X-(X/n)*n 

(En supposant que X et n sont des entiers)

REMARQUE: pour l’optimisation au niveau de l’assemblage, utilisez iDiv comme expliqué ci-dessus par Krystian.