L'opérateur modulo

Ce billet date de plusieurs années, ses informations peuvent être devenues obsolètes.

Vous croiserez souvent cet opérateur dans votre vie de développeur. En fait, il est fondamental en informatique.

Je vais parler de maths en première partie. Je ne fais pas ça ici souvent, en partie parce que je n'ai jamais eu une très bonne relation avec eux à l'école :) Mais parfois il faut y aller quand même pour comprendre comment ça marche.

Ces notes sur le modulo vous serviront peut-être à comprendre et creuser le sujet si comme moi vous êtes en grande partie autodicacte.

En mathématiques

Divisibilité et vocabulaire

En arithmétique on dit qu'un entier a est divisible par un entier b s'il existe un entier k tel que a = bk. On dit que :

  • a est un multiple de b
  • b divise a
  • b est un diviseur de a

On note alors b | a (avec une barre verticale).

Division euclidienne

C'est la division de deux entiers a / b qu'on apprend à l'école.

Pour deux entiers a et b, il existe un couple unique d'entiers (q, r) vérifiant :

a = bq + r (0 <= r < b)

On appelle a le dividende, b le diviseur, q le quotient et r le reste :

La condition est importante : le reste r est toujours un entier inférieur au diviseur b. Les valeurs possibles du reste sont 0, 1, 2, …, b-1.

a / b
a = bq + r

17 / 3
17 = 3 * 5 + 2

Congruences sur les entiers

La congruence est une technique de l'arithmétique modulaire où l'on raisonne sur les restes de la division euclidienne.

Puisque l'on sait que les valeurs possibles du reste de a / b sont 0, 1, 2, …, b-1, on peut visualiser l'arithmétique modulaire comme un cycle : après un certain nombre, on revient au point de départ. Par exemple si on divise par 3 :

Dividende / Diviseur Reste
3 / 3 0
4 / 3 1
5 / 3 2
6 / 3 0
7 / 3 1
8 / 3 2
9 / 3 0

On parle d'arithmétique de l'horloge quand on compare une horloge à 12 chiffres à un système modulaire à base 12 (en considérant le chiffre 12 comme 0). Si on ajoute 7 au nombre 10, on n'obtient pas 17, mais 5. Dans ce cas, on dit que 17 et 5 sont congrus modulo 12 :

Dividende / Diviseur Reste
5 / 12 5
17 / 12 5

Congruence, du latin congruere, signifie se rencontrer en étant en mouvement. Et modulo, du latin modulus, signifie mesure. Ainsi, dire que 17 et 5 sont congrus modulo 12 signifie que 17 rencontre 5 lorsqu'on prend 12 comme mesure.

Au point de vue mathématique, on dit que deux entiers a et b sont congrus modulo m si leur différence est un multiple de m :

m | (a - b)

En repassant par la case vocabulaire, on peut formuler cela d'une manière différente : (a - b) est divisible par m.

La notation mathématique pour dire que a et b sont congrus modulo m se fait avec le signe (un triple égal) :

a ≡ b (mod m)

On peut aussi dire que a et b ont le même reste dans la division par m.

Les congruences permettent donc de faire des calculs sur des cycles. Mais pas seulement. Il y d'autres usages :

Pour des présentations mathématiques plus complètes, vous pouvez lire :

En informatique c'est presque pareil…

En informatique on obtient le reste de la division grâce à l'opérateur modulo, souvent représenté par %.

On peut déduire de la présentation mathématique ci-dessus des règles pratiques et des exemples d'usage de l'opérateur modulo.

Déterminer la parité d'un nombre

On détermine la parité d'un nombre en testant les restes possibles de la division par 2 qui ne peuvent être que 0 (pour les nombres pairs) ou 1 (pour les nombres impairs).

Faire quelque chose à intervalles réguliers

On sait qu'un entier est divisible par un autre si le reste de la division est 0, on peut donc s'en servir pour trouver des multiples. Par exemple, pour trouver les multiples de 3 et faire quelque chose toutes les trois fois :

if (n % 3 == 0)

Afficher des secondes en heures, minutes et secondes

Comme nous mesurons beaucoup de choses en périodicité, on peut utiliser l'arithmétique modulaire :

hours = seconds / 3600
minutes = (seconds / 60) % 60
seconds = seconds % 60

Revenir au début d'un tableau après avoir atteint le dernier index

Supposons que l'on veuille faire une opération impliquant chaque élément d'un tableau et son succésseur. Pour éviter de sortir des limites du tableau, on peut revenir au début en se servant de l'opérateur modulo :

let arr = 'foobarbaz'.split('');

for (let i = 0; i < arr.length; i++) {
    console.log(i, (i + 2) % arr.length);
}

Rotation d'une image en fonction d'un angle

Comme un tour complet est égal à 360°, on peut borner les chiffres entre 0 et 360 avec le modulo :

angle % 360

…sauf pour le modulo d'un nombre négatif

Avec l'exemple de la rotation d'une image, que se passe-t-il si on veut utiliser un angle de -15° ?

Et bien ça dépend de l'implémentation du modulo par votre langage.

En Python :

>>> -15 % 360
345

En JavaScript :

> -15 % 360
-15

Python implémente le modulo Euclidien qui retourne toujours un résultat positif. Guido van Rossum explique ce choix dans un billet sur la division et un exemple concret est utilisé dans la FAQ.

JavaScript utilise le modulo tronqué qui retourne un nombre du même signe que le dividende. Or ça n'est pas toujours le résultat qu'on attend. On peut retourner un modulo Euclidien en JavaScript comme ça par exemple :

let euclideanModulo = (dividend, divisor) => {
  if (dividend < 0) {
    dividend = (dividend % divisor) + divisor
  }
  return dividend % divisor
}

euclideanModulo(-15, 360)  // 345

Par conséquent ça peut être vraiment utile de savoir comment son langage favori implémente le modulo :)

Avant Prélèvement à la source pour les TNS à l'IS Après Complexité algorithmique et notation Grand O

Tag Kemar Joint