Calculs cycliques et modulo

Le modulo

L’opération arithmétique modulo est souvent utilisée en informatique, et plus particulièrement dans le développement.

Elle est souvent présentée comme le reste d’une division entière. Par exemple :

7 ÷ 2 = 3 reste 1. Ainsi, 7 modulo 2 = 1.

27 ÷ 24 = 1 reste 3. Ainsi, 27 modulo 24 = 3.

C’est une opération qui se révèle très utile dès que l’on a affaire à des calculs cycliques, le plus connu étant le problème de l’horloge.

En effet, une horloge (digitale dans notre exemple) indique l’heure de la journée de façon numérique, les heures allant de 0 (minuit) à 23. Une heure après 23 heures, il est minuit. L’horloge recommence un cycle à zéro.

Il existe bien sûr d’autres exemples, ayant des cycles différents. Par exemple, une montre analogique a un cycle de 12 : lorsque l’aiguille a fait un tour complet, elle reprend à 1.


Les angles (en degrés) ont un cycle de 360, etc.

Calculs cycliques

Lorsque des calculs cycliques doivent être effectués, il faut tenir compte de la durée du cycle.

Par exemple, s’il est 10 heures et que l’on souhaite calculer l’heure qu’il sera dans 5 heures, il suffit de faire une addition : 10 + 5 = 15 heures.
Par contre, si il est 22 heures (et que l’on souhaite encore calculer l’heure qu’il sera dans 5 heures), la simple addition abouti à un résultat erroné : 22 + 5 = 27 heures.

Le problème vient du fait que toutes les 24 heures, l’horloge recommence à zéro. Elle travaille donc dans une arithmétique modulaire (cyclique) dont le cycle, nous l’avons vu, est de 24 heures.

L’opération arithmétique modulo permet de tenir compte du cycle. Ainsi, pour garantir que le résultat soit toujours conforme au cycle de 24 heures de l’horloge, il suffit d’appliquer un modulo à l’addition :

heure ultérieure = (heure actuelle + décalage) modulo 24.

En reprenant notre exemple :

heure ultérieure = (22 + 5) modulo 24 = 3

Ce qui est correct : 5 heures après 22 heures, il sera 3 heures du matin.

Maintenant, essayons de faire la même chose mais pour calculer une heure précédente.

Par exemple, s’il est 11 heures et que l’on souhaite calculer l’heure qu’il était il y a 7 heures, il suffit de faire une soustraction : 11 – 7 = 4 heures.
Par contre, s’il est 6 heures (et que l’on souhaite encore calculer l’heure qu’il était il y a 7 heures), la simple soustraction aboutit à un résultat erroné : 6 -7 = -1 heures. Ce n’est pas une surprise.

Dès lors, il semble logique qu’il faille appliquer la technique du modulo :

heure précédente = (heure actuelle – décalage) modulo 24.

ou selon notre exemple : heure précédente = -1 modulo 24.

Mais quel est le reste de la division de -1 par 24 ?

-1 ÷ 24 = 0 reste -1

C’est là que les problèmes commencent : dans le cas d’une arithmétique cyclique, le résultat attendu n’est pas -1 mais 23.

Cet exemple met en lumière que le reste d’une division entière et le modulo ne sont pas interchangeables :

  • Tant que les calculs sont effectués sur des nombres positifs, le reste de la division entière et le modulo donnent des résultats identiques.
  • Dès qu’un des nombres de la division est négatif, les deux opérations ne fournissent plus les mêmes résultats.

En résumé

Nous venons de voir que le modulo n’est pas une opération identique au reste de la division entière. Elle diffère en particulier lorsque le dividende et/ou le diviseur sont négatifs.

Voici un tableau récapitulatif :

Dividende Diviseur Quotient Reste Modulo
27 24 1 3 3
24 24 1 0 0
15 24 0 15 15
0 24 0 0 0
-1 24 0 -1 23

Reprenons la façon de calculer le reste d’une division :

La partie intéressante est l’arrondi : quel arrondi utiliser pour convertir le résultat de la division (un nombre réel) en un nombre entier ? Car il y a bien sûr plusieurs façons d’arrondir un nombre.

La réponse la plus évidente est de ne garder que la partie entière du résultat (c’est une troncature). Par exemple, la partie entière de 3.4 est 3. La partie entière de 4.9 est 4.

Il en résulte que la partie entière est toujours inférieure ou égale au nombre réel.

Qu’en est-il lorsque le résultat est négatif ?

Si l’on fait une troncature, la partie entière de -3.4 est -3. La partie entière de -4.9 est -4.

On constate qu’avec cette méthode le sens de l’arrondi change pour les nombres négatifs : les nombres arrondis sont supérieurs ou égaux aux nombres réels.

Une autre alternative serait alors d’arrondir le nombre réel au nombre entier inférieur (arrondi vers -∞). Ainsi, l’arrondi de -3.4 serait -4 et celui de -4.9 serait -5. Ainsi, peu importe que le nombre à arrondir soit positif ou négatif, son arrondi est toujours égal ou inférieur.

Il y a donc deux façons d’arrondir un nombre à virgule qui nous intéresse et qui donnerait des résultats corrects : soit en effectuant une troncature(arrondi vers zéro), soit en effectuant un arrondi vers -∞.

Ces deux façons de faire aboutissent au même résultat pour les nombres positifs, mais à des résultats différents pour les nombres négatifs.

C’est cette différence de méthode d’arrondi qui débouche soit sur le calcul d’un reste de la division (troncature), soit sur le modulo (arrondi vers -∞).

En résumé :

L’opérateur modulo en C++

Voyons maintenant comment réagit l’opérateur modulo en C++, symbolisé par le symbole % :

cout << 27 % 24 << "\n" // affiche 3
cout << -1 % 24 << "\n" // affiche -1

On voit que l’opérateur modulo (%) est mal nommé : il ne calcule pas le modulo, mais le reste de la division entière. Ceci provient du fait qu’en C++, la division entière utilise la troncature
pour convertir un résultat réel en entier.

Pour calculer le modulo en C++, il faut donc écrire notre propre fonction, qui utilisera un arrondi vers -∞ :

int modulo(int Dividende, int Diviseur) {
   return Dividende - std::floor(static_cast<double>(Dividende)/Diviseur) * Diviseur;
}

La fonction floor() (de la bibliothèque cmath) effectue un aarrondi vers -∞.

Le static_cast<double>() permet de forcer la division à être effectuée sur des nombres réels. Sans cela, la division retournerait directement un résultat entier (obtenu par troncature
) et la fonction floor() n’aurait plus aucun effet.

Par souci de clarté, on pourrait également écrire notre propre fonction calculant le reste de la division, en utilisant une troncature :

int remainder(int Dividende, int Diviseur) {
   return Dividende - Dividende/Diviseur * Diviseur;
}

Mais vous l’avez compris, cette fonction fait double emploi avec l’opérateur %.

Excel et VBA

Excel propose la fonction MOD(), qui calcule bel et bien le modulo.

Par contre, il faut faire attention à l’opérateur Mod de VBA, qui calcule, comme son nom ne l’indique pas, le reste !

Dividende Diviseur Quotient Reste Modulo Fonction Excel MOD() Opérateur VBA Mod
27 24 1 3 3 3 3
24 24 1 0 0 0 0
15 24 0 15 15 15 15
0 24 0 0 0 0 0
-1 24 0 -1 23 23 -1

C’est bien beau, mais à quoi ça sert ?

Voici un exemple concret qui illustre bien l’intérêt de comprendre la différence entre le reste et le modulo. Nous allons réaliser un petit programme de codage/décodage au moyen du chiffre de César.

Le chiffre de César est une méthode de chiffrement très simple (et peu robuste). Elle consiste à remplacer chaque lettre d’une phrase par une lettre à distance fixe dans l’ordre de l’alphabet. Par exemple, avec un décalage de 3, la lettre A devient D, la lettre J devient M, etc.

Ainsi, la phrase BONJOUR LES AMIS, avec un décalage de 3, deviendra ERQMRXU OHV DPLV !

Pour implémenter dans un langage informatique cette méthode de chiffrement, il faut au préalable numéroter chaque lettre (lui donner un numéro), afin de pouvoir faire le calcul du décalage.

Lors du calcul du décalage, il faut tenir compte de l’aspect cyclique de la numérotation des lettres de l’alphabet : après la lettre Z (qui a le numéro 25), il faut reprendre à la lettre A (qui a le numéro 0). Cette difficulté est contournée par l’utilisation du modulo.

Voici une première implémentation en C++ de notre application :

// Codage/décodage au moyen du chiffre de César
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int modulo(int Dividende, int Diviseur);
int numeroDeLettre(char Letter);
char lettreDeNumero(int LetterNumber);
bool estUnCaractere(char Char);
string encodeCesar(string Phrase, int Shift);
string decodeCesar(string Phrase, int Shift);

// Programme principal
int main() {
    string Phrase;
    int Decalage = 0;

    // Saisie de la phrase et du décalage
    cout << "Phrase a coder : ";
    getline(cin, Phrase);

    // Converti la phrase en majuscules
    transform(Phrase.begin(), Phrase.end(), Phrase.begin(), ::toupper);

    cout << "Decalage : ";
    cin >> Decalage;

    // Codage et décodage
    string PhraseEncodee = encodeCesar(Phrase, Decalage);
    cout << "\nPhrase codee :  " << PhraseEncodee << "\n\n";

    return 0;
}

// Retourne le numéro de la lettre donnée en paramètre.
int numeroDeLettre(char Lettre) {
    return Lettre - 'A';
}

// Retourne la lettre correspondant au numéro donné en paramètre.
char lettreDeNumero(int NumeroDeLettre) {
    return NumeroDeLettre + 'A';
}

// Retourne un booléen indiquant si le caractère donné correspond à une
// lettre de l'alphabet.
// Par souci de simplification, les lettres accentuées sont ignorées.
bool estUnCaractere(char Caractere) {
    return Caractere >= 'A' && Caractere <= 'Z';
}

// Encode la chaîne passée en paramètre avec le décalage donné.
string encodeCesar(string Phrase, int Decalage) {
    string::iterator it = Phrase.begin();
    // Chaque caractère de la phrase est codé l'un après l'autre
    for(; it != Phrase.end(); it++) {
        if (estUnCaractere(*it)) {
            int NumeroDeLettre = numeroDeLettre(*it);
            int NumeroDeLettreDecalee = (NumeroDeLettre + Decalage) % 26;
            (*it) = lettreDeNumero(NumeroDeLettreDecalee);
        }
    }
    return Phrase;
}

Voici le résultat de ce petit programme :

Phrase a coder : COMMENT ALLEZ-VOUS ?
Decalage : 3

Phrase codee :  FRPPHQW DOOHC-YRXV ?

Press <RETURN> to close this window...

Le décodage, par contre, met en lumière la différence entre le modulo et le reste de la division entière. Si la lettre A (numéro 0) doit être décalée d’une position à gauche (-1), la lettre à obtenir est la lettre Z (numéro 25) et non pas le numéro -1, qui ne correspond à aucune lettre.

Dividende Diviseur Quotient Reste Modulo
25 26 0 25 25
26 26 0 0 0
0 26 0 0 0
-1 26 0 -1 25

C’est donc bel et bien le calcul du modulo qu’il faut utiliser et non pas celui du reste. En C++, il ne faut donc pas utiliser l’opérateur %, mais plutôt la fonction modulo() vue plus haut.

La fonction de décodage peut donc être écrite ainsi :

// Décode la chaîne passée en paramètre avec le décalage donné.
string decodeCesar(string Phrase, int Decalage) {
    string::iterator it = Phrase.begin();
    for(; it != Phrase.end(); it++) {
        if (estUnCaractere(*it)) {
            int NumeroDeLettreCodee = numeroDeLettre(*it);
            int NumeroDeLettreDecodee = modulo(NumeroDeLettreCodee - Decalage, 26);
            (*it) = lettreDeNumero(NumeroDeLettreDecodee);
        }
    }
    return Phrase;
}

Sources :

Wikipédia : modulo informatique

Wikipedia : modulo operation

The math forum : Mod function and Negative Numbers

Tags: , , ,

One Response to “Calculs cycliques et modulo”

  1. Illimité says:

    Illimité…

    […]Calculs cycliques et modulo « 0xBADDC0DE[…]…