Modulo dans tous ses états

Modulo dans tous ses états

Une de mes autres passions est les mathématiques, outil indispensable à l’informaticien .

Nous allons nous pencher aujourd’hui sur un élément assez controversé dans l’algorithmique et dans les mathématiques : le modulo.

Classiquement, on sait qu’un modulo est le reste de la division de deux nombres. Pour l’instant, on a juste, mais comment doit se comporter notre modulo quand on a des nombres négatifs ?

Imaginons que nous souhaitons faire la rotation d’une image selon un angle donné en argument. La fonction rotation de la librairie Imaging SDK par exemple, prend en paramètre uniquement des nombres compris entre 0 et 360. Solution : utiliser un modulo.

angle % 360

Si nous avons en entrée l’angle de 375°, un petit modulo 360 et nous passons à 15°, logique et normal. Maintenant imaginons que l’on passe l’angle de -15° en paramètre. Nous allons nous attendre à avoir 345°, mais non… le modulo nous retourne -15. Alors bug ou pas ?

Les modulos

En fait non, la subtilité est qu’il n’y a pas un type de modulo mais trois :

  • le modulo entier qui retourne un nombre entre 0 et le diviseur (si celui-ci est négatif, le résultat sera négatif)
  • le modulo tronqué qui retourne un nombre du même signe que le dividende
  • le modulo euclidien qui retourne toujours un nombre positif

Au niveau algorithmique, à titre personnel, je préfère le modulo euclidien mais dans le cas du framework .Net,c’est un modulo tronqué, dommage pour nous, c’est le seul qui ne respecte pas la loi modulaire : (x+n) mod n = x mod n

En effet,

-5 % 11 == -5

(-5+11) % 11 = 6

Le modulo euclidien en .Net

Dans notre exemple précédent, nous souhaitons utiliser un modulo euclidien, qui retourne toujours un résultat positif.

Voici une implémentation :

a<0?((a % n) + n) % n:a%n

Un peu plus lourd, mais plutôt efficace.

Et C++?

Jusqu’à C++/11, le comportement du modulo negatif n’était pas indiqué (et de façon explicite), c’était au compilateur/processeur de choisir, pas top pour la portabilité.

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.

 

Ceci dit, dans la majorité des cas, le modulo suivait les règles héritées par le Fortran, c’est à dire, le modulo tronqué.

Avec C++/11 les choses sont devenus plus clair et le choix a été fait d’utiliser obligatoirement le modulo tronqué.

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined. For integral operands the / operator yields the algebraic quotient with any fractional part discarded;81 if the quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a.

 

Bilan

Attention aux a priori et vérifiez toujours ce que les fonctions .Net retournent

Comments are closed.