Probleme – Le compteur binaire, et son coût amorti

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 3 — Algorithmes, programmes et complexité

Énoncé

On incrémente un compteur binaire de $k$ bits, initialement nul, $n$ fois de suite. Le coût d'une incrémentation est le nombre de bits qu'elle fait basculer.

Écrire l'incrémentation, et donner le coût d'un appel dans le pire cas.
Montrer que le coût total de $n$ incrémentations est $< 2 n$ , et en déduire le coût amorti.
Vérifier la borne par la mesure, et donner la valeur exacte du total.

Corrigé

1. L'incrémentation.


/* Incremente le compteur binaire c[0..k-1] (c[0] est le bit de poids
   faible). Renvoie false en cas de debordement.
   Precondition : chaque c[i] vaut 0 ou 1. */
bool incrementer(int c[], int k) {
    int i = 0;
    /* INVARIANT : les bits c[0..i-1] valaient tous 1 et ont ete mis a 0. */
    while (i < k && c[i] == 1) { c[i] = 0; i = i + 1; }
    if (i == k) { return false; }        /* le compteur etait 11...1 */
    c[i] = 1;
    return true;
}

Pire cas d'un appel : le compteur vaut $11 \dots 1$ sur ses $k$ bits utiles, et l'incrémentation les bascule tous, plus un : $Θ (k) = Θ (lo g n)$ . Mesuré : le $25 6^{e}$ incrément, qui passe de $11111111$ à $100000000$ , coûte $9$ basculements.

2. Le coût total, par comptage par bit. Ne comptons pas par incrémentation, mais par bit — c'est le retournement qui fait tout le problème.

Le bit $0$ bascule à chaque incrémentation : $n$ fois.
Le bit $1$ ne bascule qu'une incrémentation sur deux : $⌊ n /2 ⌋$ fois.
Plus généralement, le bit $j$ bascule $⌊ n / 2^{j} ⌋$ fois.

Le total vaut donc

$j \geq 0 \sum ⌊ \frac{n}{2 ^{j}} ⌋ \leq j \geq 0 \sum \frac{n}{2 ^{j}} = 2 n .$

Le coût amorti d'une incrémentation est donc $< 2$ , c'est-à-dire $O (1)$ — alors que le pire cas d'un appel isolé est $Θ (lo g n)$ .

3. La mesure, et la formule exacte.


      n | basculements | 2n - s2(n) | basculements/n
      1 |            1 |          1 | 1,0000
      2 |            3 |          3 | 1,5000
      4 |            7 |          7 | 1,7500
     16 |           31 |         31 | 1,9375
    100 |          197 |        197 | 1,9700
   1000 |         1994 |       1994 | 1,9940
  10000 |        19995 |      19995 | 1,9995
1000000 |      1999993 |    1999993 | 2,0000

La valeur exacte est $2 n - s_{2} (n)$ , où $s_{2} (n)$ est le nombre de $1$ dans l'écriture binaire de $n$ — la mesure la confirme sur les huit lignes. Le rapport monte vers $2$ sans jamais l'atteindre : la borne $2 n$ est fine, et elle est stricte.

ImportantPourquoi cet exemple, plutôt que le tableau qui double

Les deux illustrent le coût amorti, mais celui-ci est plus honnête sur un point : il n'y a aucune allocation, aucune recopie, aucun $2$ qui sortirait d'un choix d'implémentation. Le facteur $2$ vient de la seule série géométrique $\sum 2^{- j}$ , c'est-à-dire de la structure de la numération binaire. C'est le même argument que pour le tableau dynamique, réduit à son squelette.

Et la garantie est du même type : aucune hypothèse sur les entrées. Il n'y a d'ailleurs pas d'entrée — le compteur ne fait que compter. On ne peut pas construire une « mauvaise suite d'incrémentations » : c'est la différence entre l'amorti et le cas moyen, rendue évidente.

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.