L'opération modulo cache bien des surprises

Modulo or not modulo, that is the question.

Image d'entête

par skywodd | | Licence (voir pied de page)

Catégories : Dossiers | Mots clefs : Math Algo


Combien fait -1 modulo 10 ? C'est la question que je me suis posée après avoir découvert un comportement bizarre sur un de mes programmes. Aussi bizarre que cela puisse paraître, il n'y a pas une réponse possible, mais plusieurs.

Sommaire

Bonjour à toutes et à tous !

L'opération modulo est une opération mathématique basique que je pensai bien connaitre depuis le temps que je l'utilise. On pense tous la connaitre, mais elle nous réserve encore bien des surprises. J'en ai fait les frais pas plus tard qu'hier soir.

J'étais en train de réaliser un programme pour un article, comme d'habitude, jusque là rien de bien palpitant. Il s'agissait d'un programme en JavaScript, la bête noire de tous les développeurs back-end.

JavaScript est un langage de programmation côté client utilisé sur la quasi-totalité des sites web pour ajouter de la dynamique, des fonctionnalités et autres petites touches d'intelligence à de bêtes pages de texte.

JavaScript est bien connu en informatique pour deux choses :

  • Sa syntaxe proche du Java, mais complètement déstructurée et incohérente (tout l'inverse de Java donc),

  • Ses défauts d'implémentation et ses bugs "par design" qui transforment vite le moindre morceau de code en une partie de démineur.

Pour vous donner une idée du massacre (c'est juste un aperçu, Google est rempli d'autres exemples) :

1
2
"1" + 1 = "11"
"1"  1 = 0

Avec ce genre de perle un peu partout dans la syntaxe, autant vous dire que le debug devient vite un concours de celui qui criera le plus fort.

Bref, j'étais en train de faire mon programme, quand j'ai eu besoin d'utiliser un modulo. J'avais besoin qu'un nombre soit compris entre 0 et 9. Cas d'usage classique du modulo.

Je fais mon code, et là c'est le drame, un bug apparait. Mon chiffre n'est pas compris entre 0 et 9 mais entre -9 et 9. Je creuse donc un peu pour comprendre l'origine du bug et je me rends vite compte qu'en JavaScript -1 modulo 10 ne fait pas 9 mais -1.

L'impensable s'est produit. Il y a un "bug" dans l'implémentation d'une opération basique comme le modulo (un bug de plus ou de moins, on est plus à ça prés). Je fais part de ma découverte sur Twitter et surprise, comme souvent dans ce genre de cas, il y plusieurs points de vue.

Pour certains, -1 est la bonne réponse, pour d'autres c'est 9. Pour moi la bonne réponse me semblait être 9, j'y mettrais ma main à couper. Après tout, on m'a appris et j'ai toujours vu l'opération modulo retourner des nombres exclusivement positifs (sauf sur la version x86 de GCC pour PC, qui retourne des nombres négatifs suivant le cas, cela aurait dû me faire tilter). J'avais tort. Mon Dieu que j'avais tort.

Thèse

Un abonné sur Twitter m'a transmis un lien vers un court article expliquant la base de l'opération modulo. Lisez-le, il explique tout.

Pour résumer, il existe non pas un, mais trois modulos (cf lien ci-dessus) :

  • le modulo entier qui retourne un nombre entier entre 0 et le diviseur. Si le diviseur est négatif, le résultat est 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.

Haaaaaa, vive les mathématiques. Pourquoi faire simple quand on peut faire compliquer.

D'après cette description, le modulo qui retourne 9 à la question -1 % 10 = ? est de type euclidien. Celui qui répond -1 est de type tronqué. Et celui qui répond 0 a bien abusé sur la boisson **ick**.

Antithèse

S'il existe trois modulos différents, lequel est le bon (en informatique) ? Aucun et tous à la fois. Il n'y a pas de réponse claire.

Un développeur bas niveau / embarqué comme moi aura tendance à utiliser le modulo euclidien, car celui-ci peut s'implémenter avec une simple boucle "tant que la valeur est inférieure à 0 ou supérieure au diviseur: ajoute / soustrait le diviseur à la valeur" ou un masque binaire pour les puissances de deux.

Mais que pensent les autres développeurs, en particulier ceux qui s'occupent de l'implémentation des compilateurs, voire même de l'écrire des standards informatiques ?

Malaise

Pour répondre à cette question, j'ai lancé une machine virtuelle vierge, puis codé rapidement un code de test affichant le résultat de -1 % 10 en console avec divers langage de programmation.

Les résultats sont … perturbants. C'est le moins qu'on puisse dire.

J'ai obtenu sept fois la réponse 9 de la part de logiciel que j'utilise quotidiennement :

  • Python 2

  • Python 3

  • Lua

  • Perl

  • Ruby

  • LibreOffice Calc

  • Excel (N.B. Retourne un nombre du même signe que le diviseur).

En parallèle, j'ai aussi obtenu onze fois la réponse -1 :

  • Bash

  • Java

  • Groovy

  • JavaScript (Chrome)

  • JavaScript (Firefox)

  • C99 (x86)

  • C++14 (x86)

  • Objectif-C

  • VB.net

  • PHP

  • Go

Conclusion

Quand on croit trop bien maîtriser quelque chose, on finit toujours par se faire avoir. Aujourd'hui, c'était mon tour. Et pour le coup, autant vous faire profiter de ma bêtise. Cela évitera peut-être à quelques lecteurs de faire la même erreur à l'avenir.

Au final, on apprend de nouvelles choses tous les jours, même sur des choses aussi basiques qu'un modulo.