L'étrange somme 1 + 2 + 4 + 8 + 16... en FORTH

published: 21 December 2024 / updated 21 December 2024

Lire cette page en français

 

Regardez cette vidéo mise en ligne sur Youtube. Elle explique que la somme de tous les carrés de 2 à l'infini donne -1.

Cet étrange résultat semble en contradiction avec le sens commun qui nous laisse supposer que le résultat serait en réalité infini!

La somme 1 + 2 + 4 + 8 + 16...

Commençons par étudier cette somme des carrés de 2:

1 + 2 + 4 + 8... à l'infini

Décomposons chaque terme de cette somme:

Ici, nous nous sommes arrêtés à 4 termes. Mais le raisonnement qui suit est valable pour N termes.

La somme suivante:

(2 EXP 0) + (2 EXP 1) + (2 EXP 2) + (2 EXP 3) ... + (2 EXP (N-1)) 
  = (2 EXP N) -1

Pour 2 termes:

1 + 2
 = (2 EXP 0) + (2 EXP 1)
 = (2 EXP 2) - 1
 = 3

Pour 3 termes:

1 + 2 + 4
 = (2 EXP 0) + (2 EXP 1) + (2 EXP 2)
 = (2 EXP 3) - 1
 = 7

Pour 4 termes:

1 + 2 + 4 + 8
 = (2 EXP 0) + (2 EXP 1) + (2 EXP 2) + (2 EXP 3)
 = (2 EXP 4) - 1
 = 15

A première vue, comment peut-on sortir l'étonnant résultat -1?

La même somme en binaire

Reprenons les termes de cette somme, mais en binaire:

Posons cette addition, à gauche, la valeur en decimal, à droite la valeur en binaire:

 1                1
 2               10
 4              100
 8             1000
16            10000
32           100000
--           ------
63           111111

Petit rappel sur l'addition en binaire:

  0 + 0 =  0
  0 + 1 =  1
  1 + 0 =  1
  1 + 1 = 10

Ne perdez pas de vue que 2 en décimal correspond à 10 en binaire!

Donc, rajoutons maintenant 1 à notre addition:

 1                1
 2               10
 4              100
 8             1000
16            10000
32           100000
--           ------
63           111111
 1                1
--           ------
64          1000000

La somme en langage FORTH

FORTH est un langage interprété qui utilise une pile de données qui n'accepte que des entiers:

1 ( empile 1 sur la pile)
2 ( empile 2 sur la pile)
+ ( effectue la somme 1 et 2)
. ( affiche le résultat)

En FORTH, l'addition est exécutée une fois les deux valeurs à additionner placées sur la pile de données. On peut ainsi exécuter en mode interprèté:

1 2 + .

Affichera 3

Si on exécute ceci:

1 2 + 4 + 8 + .

Affichera 15

Voici un programme en FORTH qui va faire automatiquement la somme de N puissances de 2:

: sum2n ( initial iterations  --- )
   dup 0 > 
   if  \ si le nombre d'itérations n'est pas nul on exécute sum2n
     >R dup 2* r> 
     1 - recurse  \ recurse exécute sum2n
   then 
   +    \ somme des termes
;

La fonction sum2n fonctionne avec 2 valeurs:

C'est une fonction récursive. A chaque tour, on teste si le nombre d'itérations n'est pas nul, sinon on fait la somme des termes.

1 4 sum2n . 31
1 5 sum2n . 63
1 6 sum2n . 127

On peut également exécuter sum2n en demandant le résultat en binaire:

: b. 2 base ! . decimal ;
1 4 sum2n b. 11111
1 5 sum2n b. 111111
1 6 sum2n b. 1111111

A partir de là, vous êtes en train de me demander où nous voulons en venir.

Les entiers en langage FORTH

Le langage FORTH utilise une pile de données. Cette pile exploite des entiers en 16 ou 32 bits. La taile des nombres est donc forcément limitée.

Nous avons fait nos tests ci-avant avec GForth, une version 32 bits du langage FORTH. La fonction sum2n est donc limitée à 2 EXP (32-1)

Vérifions ceci:

1 29 sum2n . 1073741823
1 30 sum2n . 2147483647
1 31 sum2n . -1

Incroyable! Avec 31 itérations, on obtient -1

Avec FORTH, la somme de toutes ces valeurs:

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 4096 8192 16384 16384 32768 65536 65536 
131072 262144 524288 1048576 2097152 4194304 4194304 8388608 16777216 
33554432 67108864 134217728 268435456 536870912 1073741824 2147483648

donne -1 et ceci sans avoir besoin d'aller jusqu'à l'infini!

L'explication

Il n'y a ni bug ni erreur dans notre processus aboutissant à ce résultat qui est -1

Les nombres entiers, en langage FORTH sont signés. Sur les 32 bits servant à décrire une valeur entière, le bit de poids fort correspond à un bit de signe. Voyons ceci sur des entiers signés sur 8 bits:

 000000001 correspond à 1 en décimal
 000000010 correspond à 2 en decimal
 000000011 correspond à 3 en decimal
.....
 011111111 correspond à 127 en decimal
 100000000 correspond à -128 en decimal
 100000001 correspond à -127 en decimal
 100000010 correspond à -126 en decimal
.....
 111111111 correspond à -1 en decimal.

Ca vous choque? Alors faisons la somme de 127 et -127 en binaire:

    011111111
    100000001
    ---------
  1 000000000

Ici, nous avons mis la retenue bien séparée à gauche. On constate que la somme bit à bit des valeurs binaires de 127 et -127 donne bien zéro si on ne tient pas compte de la retenue.

Ce qui est vrai en décimal, 127 - 127 = 0 reste valable en binaire. Nos ordinateurs fonctionnent ainsi.

L'explication donnée ici pour des entiers signés 8 bits reste valable pour ces mêmes entiers signés sur 32 bits manipulés par le langage FORTH.

Et avec des entiers non signés?

Quelque soit la taille de l'entier résultat d'une somme de carrés successifs de 2, le résultat en binaire sera toujours une succession de 1. Exemple:

1 30 sum2n b. 1111111111111111111111111111111

Le simple fait d'ajouter 1 à n'importe quel résultat composé d'une succession de 1 donnera une succession de zéros et s'achevant par une retenue.

Conclusion

Le résultat de la somme des puissances successives de 2: 1 + 2 + 4 +8.... poursuivie aussi loin que vous voudrez donnera donc -1 si vous imposez une limite. Pour n valeurs, cette limite sera 2 EXP N.

Si N est infini, le résultat en binaire sera une succession de 111111111111... infinie, le bit de poids le plus élevé étant considéré comme bit de signe, le résultat sera toujours -1.