Les roues de Babbage, à faire tourner

Le DM vous a fait tourner la manivelle à la main, et c’est la bonne façon de comprendre le mécanisme. Voici la même machine en douze lignes, pour la lancer sur des tables que la main ne suivrait pas.

Un tour de manivelle

Toute la machine tient dans une remarque du DM : chaque roue reçoit le contenu de sa voisine de droite, et l’ordre compte. On commence par la roue de gauche, celle qui porte la valeur, et l’on progresse vers la droite. Si l’on faisait l’inverse, la roue $R_0$ recevrait la différence première du rang suivant au lieu de celle du rang courant : au premier tour, elle afficherait $1 + 9 = 10$ au lieu de $1 + 5 = 6$, et toute la table serait fausse.

def tour(roues):
    """Un tour de manivelle. Chaque roue reçoit sa voisine de droite,
    EN COMMENCANT PAR CELLE DE GAUCHE : c'est la question Q10 du DM."""
    for i in range(len(roues) - 1):
        roues[i] += roues[i + 1]
    return roues[0]


def table(roues, n):
    """La valeur de départ, puis n tours de manivelle."""
    sortie = [roues[0]]
    for _ in range(n):
        sortie.append(tour(roues))
    return sortie

C’est tout. Il n’y a pas de multiplication dans ce code, et ce n’est pas une coquetterie : c’est exactement l’argument de Babbage. Une roue dentée sait avancer d’un cran, donc elle sait additionner ; elle ne sait pas multiplier.

La table du DM

Réglez trois roues sur les premiers nombres de chacune des trois lignes du triangle, $1$, $5$ et $4$, et demandez huit tours.

>>> table([1, 5, 4], 8)
[1, 6, 15, 28, 45, 66, 91, 120, 153]

C’est la table $T$ du prologue, celle de $2x^{2} + 3x + 1$, obtenue sans qu’aucun carré n’ait été calculé.

Pour le troisième degré, il suffit d’une roue de plus. La table de $x^{3} - 2x$ démarre sur $0$, $-1$, $6$, $6$.

>>> table([0, -1, 6, 6], 6)
[0, -1, 4, 21, 56, 115, 204]

Le décompte, et pourquoi il décide de tout

Comptez les opérations dans la fonction tour : pour une machine à $r$ roues, elle fait $r - 1$ additions, et pas une multiplication. Une table de mille valeurs demande donc $999$ tours.

>>> valeurs = table([1, 5, 4], 999)
>>> len(valeurs), valeurs[-1]
(1000, 1999000)

Deux mille additions environ, aucune multiplication, pour atteindre un nombre proche de deux millions. Voilà pourquoi la machine était concevable en 1822 : non pas parce que les additions sont peu nombreuses, mais parce qu’une addition est un geste qu’un engrenage sait faire seul, en série, sans qu’une main vienne le conduire à chaque étape.

Prolonger un triangle, et voir la table trahir

La question 23 du DM demandait un septième nombre pour une table de six valeurs qui n’est pas polynomiale. Le prolongement se fait de la ligne la plus basse vers la plus haute, et le code est presque le même que celui de la machine, lu à l’envers.

def differences(t):
    return [t[i + 1] - t[i] for i in range(len(t) - 1)]


def triangle(t):
    """Toutes les lignes de différences, jusqu'à la dernière possible."""
    lignes, courante = [], list(t)
    while len(courante) > 1:
        courante = differences(courante)
        lignes.append(courante)
    return lignes


def prolonger(t):
    """Ajoute une colonne au triangle, en admettant que la dernière
    ligne garde sa valeur, puis rend la valeur produite."""
    lignes = triangle(t)
    ajout = lignes[-1][-1]
    for ligne in reversed(lignes[:-1]):
        ajout += ligne[-1]
    return t[-1] + ajout

Lancez-le sur les six valeurs de $\dfrac{60}{x-4}$ pour $x$ de $5$ à $10$.

>>> valeurs = [60, 30, 20, 15, 12, 10]
>>> triangle(valeurs)
[[-30, -10, -5, -3, -2], [20, 5, 2, 1], [-15, -3, -1], [12, 2], [-10]]
>>> prolonger(valeurs)
0

La machine imprime $0$. La vraie valeur est $r(11) = \dfrac{60}{11-4} = \dfrac{60}{7}$, soit environ $8{,}57$.

Prenez la mesure de ce résultat. Sur les six valeurs fournies, la machine ne s’est pas trompée d’un centième : une expression du cinquième degré passe exactement par ces six points, et une machine à six roues les écrit toutes. C’est au premier point qu’on ne lui a pas donné qu’elle s’effondre, et elle s’effondre spectaculairement, en annonçant zéro là où il fallait huit et demi.

L’expérience qui vaut d’être faite

Reprenez alors le contraste avec la table des puissances de $2$, celle de la question 22.

>>> D = [2 ** k for k in range(9)]
>>> triangle(D)[:3]
[[1, 2, 4, 8, 16, 32, 64, 128], [1, 2, 4, 8, 16, 32, 64], [1, 2, 4, 8, 16, 32]]

Chaque ligne reproduit la table de départ, indéfiniment. Aucune ne se fige, et aucune machine ne l’écrira jamais, quel que soit le nombre de roues : c’est démontré pour tous les entiers, pas constaté sur un échantillon.

Les deux échecs n’ont donc pas la même nature, et c’est le vrai sujet de la dernière question du DM. Celui de $2^{k}$ est définitif. Celui de $\dfrac{60}{x-4}$ est local : il suffit de régler à nouveau la machine un peu plus loin pour repartir juste. C’est exactement ce que faisaient les fabricants de tables de logarithmes, et ce que faisait la deuxième section de Prony en préparant les feuilles tronçon par tronçon.

Modifiez les six valeurs de départ et relancez prolonger : vous verrez que plus la table est proche d’un polynôme sur l’intervalle choisi, plus la trahison est tardive et discrète. C’est toute l’histoire du calcul numérique en une expérience de trois lignes.