Le modulo qui déborde

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 18 — Algorithmique des textes

Énoncé

Dans le hachage roulant, on doit rendre positive la quantité $h - T_{i} b^{m - 1}$ avant de multiplier par $b$ . On hésite entre deux écritures :


/* (A) */ ht = ((ht - t[i] * puissance % Q + Q)     * B + t[i + m]) % Q;
/* (B) */ ht = ((ht - t[i] * puissance % Q + Q * Q) * B + t[i + m]) % Q;

Avec Q = 1000000007 et des long long, laquelle est correcte ? Vérifier.

Corrigé

(A) est correcte, (B) déborde — et le débordement est silencieux.

L'analyse. La quantité ht - t[i] * puissance % Q vit dans $(- Q, Q)$ : ht est un reste modulo $Q$ , donc dans $[0, Q)$ , et l'on en retranche un autre reste. Ajouter $Q$ une fois suffit donc à la rendre positive, et le résultat reste $< 2 Q \approx 2 \cdot 1 0^{9}$ . La multiplication par $B = 256$ donne au plus $5, 1 \cdot 1 0^{11}$ , très en deçà de $LLON G_{M} AX = 9, 22 \cdot 1 0^{18}$ .

Ajouter $Q \times Q = 1 0^{18}$ « pour être sûr » détruit tout : le produit par $B$ vaudrait alors environ $2, 6 \cdot 1 0^{20}$ , soit vingt-huit fois la capacité d'un long long.

Mesure. Le programme compilé avec gcc -fsanitize=undefined donne :


runtime error: signed integer overflow:
    1000000014000000049 * 256 cannot be represented in type 'long long'

recherche de "abra" dans "abracadabra abracadabra" :
   version (B) : 0
   version (A) : 0 7 12 19

La version (B) ne trouve qu'une occurrence sur quatre. Le débordement corrompt l'empreinte roulante dès la première fenêtre, et toutes les suivantes sont fausses : l'algorithme cesse silencieusement de trouver quoi que ce soit. Sur $a^{40}$ avec le motif $aaaa$ , il rend la position $0$ au lieu des $37$ positions attendues.

Trois leçons.

« Plus de marge » n'est pas « plus sûr ». En arithmétique bornée, ajouter un terme plus grand rapproche du débordement au lieu d'en éloigner. On ajoute exactement le modulo, une fois, et l'on justifie en une ligne pourquoi une fois suffit.
Le débordement d'entier signé est un comportement indéfini, pas une valeur qui « boucle ». Le compilateur a le droit d'en tirer n'importe quoi. C'est la faute du chapitre chap:langage-c, sous une forme où on ne la cherche pas.
Un test qui vérifie « on trouve l'occurrence en $0$ » aurait passé. Il faut un texte à occurrences multiples, et vérifier qu'on les trouve toutes — un partitionnement de l'espace des entrées au sens du chapitre chap:discipline.

Une dernière précaution, indépendante : t[i] est un char, dont le signe n'est pas fixé par la norme. Sur un texte accentué, il peut être négatif, et l'empreinte devient négative. On écrit donc (unsigned char) t[i] partout, comme le fait déjà la table de Boyer-Moore.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.