Le milieu qui déborde

Avec int g = 2000000000; et int d = 2100000000;, les deux formes sont mesurées :

INT_MAX          =  2147483647
g + d (en long)  =  4100000000        (au-dela de INT_MAX)
(g + d) / 2      =   -97483648        <-- NEGATIF
g + (d - g) / 2  =  2050000000        correct

Le résultat $-97483648$ n'a rien d'aléatoire : $4100000000-2^{32}=-194967296$, et la division par deux donne $-97483648$. C'est le dépassement en complément à deux du chapitre chap:langage-c, à un endroit où personne ne le cherche. Employé comme indice, ce nombre sort du tableau, et le langage ne le vérifie pas.

Pourquoi la seconde forme est sûre. Si $0\le g\le d\le \text{INT\_MAX}$, alors $d-g$ est compris entre $0$ et $d$, donc tient. Sa moitié aussi. Et $g+(d-g)/2\le g+(d-g)=d$, qui tient par hypothèse. Aucune valeur intermédiaire ne dépasse $d$ : c'est la propriété qu'il faut savoir énoncer, et elle se démontre en une ligne.

La forme générale de la parade. On l'a déjà vue à l'exercice 1.2 : pour tester $x+y\le M$ sans déborder, on écrit $x\le M-y$. Ici, pour calculer une moyenne sans déborder, on calcule un écart puis on l'ajoute. Dans les deux cas, la règle est la même : réorganiser l'expression pour qu'aucun calcul intermédiaire ne sorte de l'intervalle des données.

Ce défaut a vécu neuf ans dans la recherche dichotomique de la bibliothèque standard de Java. Il n'apparaît que sur des tableaux de plus d'un milliard de cases — c'est-à-dire jamais, jusqu'au jour où si. Aucun jeu de tests raisonnable ne l'attrape : c'est un cas où seule la relecture de l'expression, ou une preuve, protège. Le chapitre chap:discipline y revient.