Le moyen le plus rapide d'obtenir un modulo positif en C / C ++

Question

Souvent dans mes boucles internes-je besoin pour indexer un tableau dans un "wrap-around", de façon que si la taille de la matrice est de 100 et mon code demande pour l'élément -2, il devrait être donné élément 98. Dans de nombreux langages tels que Python, on peut le faire simplement avec de l' my_array[index % array_size], mais pour une raison quelconque C de l'arithmétique des nombres entiers (généralement) de tours vers zéro au lieu de systématiquement arrondi vers le bas, et, par conséquent, son opérateur modulo retourne un résultat négatif lors d'une négative premier argument.

Souvent je sais qu' index ne sera pas inférieur -array_size, et dans ces cas je ne l' my_array[(index + array_size) % array_size]. Cependant, parfois, ce ne peut être garanti, et pour les cas je voudrais savoir le moyen le plus rapide à mettre en œuvre un toujours positif modulo fonction. Il y a plusieurs "intelligents" les moyens de le faire sans ramification, tels que

inline int positive_modulo(int i, int n) {
    return (n + (i % n)) % n
}

ou

inline int positive_modulo(int i, int n) {
    return (i % n) + (n * (i < 0))
}

Bien sûr, je peux le profil de ces à savoir qui est le plus rapide sur mon système, mais je ne peux pas l'aider à se soucier que je pourrais avoir manqué un meilleur, ou que ce qui est rapide sur ma machine peut être lente sur une autre.

Donc, il y a un moyen standard pour ce faire, ou quelque astuce que j'ai raté qui est susceptible d'être le plus rapidement possible?

Aussi, je sais que c'est sans doute un vœu pieux, mais si il y a une façon de le faire qui peut être auto-vectorielle, ce serait formidable.

Answer 1

Le standard de la façon que j'ai appris est

inline int positive_modulo(int i, int n) {
    return (i % n + n) % n;
}

Cette fonction est essentiellement de votre première variante sans l' abs (ce qui, en fait, permet de retourner le résultat erroné). Je ne serais pas surpris si un compilateur optimisant pourrait reconnaître ce modèle et de le compiler en code machine qui calcule un "unsigned modulo".

Edit:

De passer à votre deuxième variante: tout d'Abord, il contient un bug, trop -- l' n < 0 devrait être i < 0.

Cette variante ne peut pas regarder comme si c'branches, mais sur beaucoup d'architectures, l' i < 0 de compiler en un saut conditionnel. Dans tous les cas, il sera au moins aussi rapide pour remplacer (n * (i < 0)) avec i < 0? n: 0, ce qui évite la multiplication; en outre, il est plus "propre" car elle évite de relire le bool comme un int.

À laquelle de ces deux variantes est plus rapide, que, probablement, dépend du compilateur et de l'architecture du processeur -- temps, les deux variantes et de voir. Je ne pense pas qu'il y a un moyen plus rapide que l'autre de ces deux variantes, bien que.

Answer 2

Modulo une puissance de deux, les œuvres suivantes (en supposant une représentation complémentaire de deux):

 return i & (n-1);
 

Answer 3

Une manière à l'ancienne d'obtenir l'addend optionnel en utilisant la propagation de bits de signe à deux compléments:

 int positive_mod(int i, int n)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int m = i%n;
    return m+ (m>>shift & n);
}
 

Answer 4

Vous pouvez ainsi faire array[(i+array_size*N) % array_size], où N est assez grand entier pour garantir argument positif, mais assez petit pour ne pas faire déborder.

Lorsque le array_size est constante, il y a des techniques pour calculer le module sans division. En plus de la puissance de deux qui approche, on peut calculer une somme pondérée de bitgroups multiplié par 2^i % n, où i est le bit le moins significatif dans chaque groupe:

par exemple, un entier 32 bits 0xaabbccdd % 100 = dd + cc*[2]56 + bb*[655]36 + aa*[167772]16, ayant une portée maximale de (1+56+36+16)*255 = 27795. Avec des applications répétées et les différentes subdivisions, on peut réduire l'opération à quelques conditionnelle soustractions.

Commun des pratiques comprennent également le rapprochement de la division réciproque de 2^32 / n, ce qui peut généralement gérer raisonnablement large gamme d'arguments.

 i - ((i * 655)>>16)*100; // (gives 100*n % 100 == 100 requiring adjusting...)