La représentation des nombres

$00101010_2=32+8+2=42$ — bit de tête $0$ : il vaut $42$ dans les deux conventions. $10101010_2=128+32+8+2=170$ comme positif ; bit de tête $1$, donc en complément à deux : $170-256=-86$. Pour $-5$ : son code est $-5+256=251=11111011_2$ — ou par la recette mécanique : $5=00000101$, bits inversés $11111010$, plus un : $11111011$. ✓ (Les deux méthodes — l'addition de $2^k$ et l'inversion-plus-un — doivent toujours coïncider : se vérifier l'une par l'autre est le contrôle naturel.)

def vers_signe(mot: int, k: int) -> int:
    """Interprète un mot de k bits en complément à deux."""
    assert 0 <= mot < 2 ** k
    return mot if mot < 2 ** (k - 1) else mot - 2 ** k

def addition_machine(x: int, y: int, k: int) -> int:
    """Additionne deux entiers signés comme un processeur k bits (modulo 2^k)."""
    return vers_signe((x + y) % (2 ** k), k)

assert addition_machine(127, 1, 8) == -128       # le tour du compteur
assert addition_machine(-1, 1, 8) == 0           # l'addition uniforme fonctionne
assert addition_machine(-128, -128, 8) == 0      # double débordement !
def oppose_machine(x: int, k: int) -> int:
    return vers_signe((-x) % (2 ** k), k)
assert oppose_machine(-128, 8) == -128           # -(-128) == -128 : l'asymétrie

Le couple « interpréter / réduire modulo $2^k$ » suffit à simuler fidèlement l'arithmétique machine — et les assertions sont les pièges du cours, devenus exécutables. (Python, justement parce que ses entiers ne débordent pas, est l'outil idéal pour étudier les débordements des autres : le modèle est dans le modulo.)

Un décimal est représentable en binaire fini si et seulement si, écrit en fraction irréductible, son dénominateur est une puissance de $2$. Ainsi : $0,5=\frac{1}{2}=0,1_2$ ✓ ; $0,75=\frac{3}{4}=0,11_2$ ✓ ; $0,625=\frac{5}{8}=0,101_2$ ✓ ; mais $0,1=\frac{1}{10}$ et $0,2=\frac{1}{5}$ ont un facteur $5$ au dénominateur : développement binaire infini (périodique), donc arrondi en machine. Vérification expérimentale :

>>> print(f"{0.625:.20f}")
0.62500000000000000000
>>> print(f"{0.1:.20f}")
0.10000000000000000555

(Le critère est le miroir exact de la base dix, où $\frac{1}{3}$ échoue à cause du facteur $3$ : chaque base a ses fractions interdites — la base deux interdit le $5$, et le système décimal de la vie courante en est truffé.)

eps, q = 1.0, 0
while 1.0 + eps / 2 != 1.0:
    # Invariant : 1.0 + eps != 1.0 ; variant : la boucle s'arrête quand
    # eps/2 passe sous l'écart entre flottants voisins de 1
    eps, q = eps / 2, q + 1
print(q, eps)            # 52,  2.220446049250313e-16  (= 2**-52)

gros = float(2 ** 20)
e2, q2 = 1.0, 0
while gros + e2 / 2 != gros:
    e2, q2 = e2 / 2, q2 + 1
print(q2, e2)            # 32,   2.3e-10 : 2**-52 * 2**20

Autour de $1$, l'écart entre flottants consécutifs est $2^{-52}$ — la précision relative de $52$ bits de mantisse. Autour de $2^{20}$, le même calcul donne $2^{-32}$ : l'écart absolu a été multiplié par $2^{20}$, exactement le facteur d'échelle. (C'est la définition vivante de « précision relative » : les flottants offrent partout les mêmes $\sim 16$ chiffres significatifs, donc une précision absolue proportionnelle à la grandeur — d'où la règle des comparaisons à écart relatif pour les grandes valeurs.)

n = 10_000_000
croissant = 0.0
for k in range(1, n + 1):
    croissant += 1 / k**2
decroissant = 0.0
for k in range(n, 0, -1):
    decroissant += 1 / k**2
# croissant   : 1.6449339668472596   (faux dès le 12e chiffre)
# decroissant : 1.6449339668482315   (= la somme exacte arrondie !)

L'écart entre les deux ordres se loge dans les derniers chiffres, et c'est l'ordre décroissant qui est le plus fidèle. Raison : en sommant par $k$ croissant, l'accumulateur devient vite grand ($\approx 1,64$) tandis que les termes deviennent minuscules ($10^{-14}$) — chaque petit terme est partiellement absorbé par l'accumulateur. En sommant par $k$ décroissant, les petits termes s'agrègent d'abord entre eux en sous-totaux de leur taille, qui pèsent ensuite face aux grands : moins de pertes. Règle pratique : sommer du plus petit au plus grand. (L'écart reste ici modeste — la série converge vite — mais le principe gouverne le calcul scientifique réel ; les bibliothèques sérieuses utilisent des sommations compensées qui annulent presque totalement ces pertes, raffinement hors programme dont l'exercice 25 de la banque donne l'idée.)

Les int de Python sont multi-précision : $2^{53}$ et $2^{53}+1$ y sont distincts, et la comparaison entière le confirme. Mais la mantisse d'un flottant porte $52$ bits après le $1$ de tête : elle représente exactement les entiers jusqu'à $2^{53}$, puis un entier sur deux (l'écart entre flottants consécutifs vaut $2$ dans $[2^{53},2^{54}]$), un sur quatre ensuite, etc. $2^{53}+1$, impair et hors plage exacte, est arrondi au flottant voisin $2^{53}$ : les deux conversions coïncident. Règle : convertir en float un entier au-delà de $2^{53}\approx 9\cdot 10^{15}$ peut le modifier — les identifiants, montants en centimes ou compteurs géants restent donc en int de bout en bout, et l'on se méfie des fonctions qui convertissent en douce (math.sqrt, moyennes, numpy). (L'erreur réelle correspondante : des identifiants à $18$ chiffres passés par un tableur ou un float ressortent arrondis — silencieusement faux, le pire genre de faux du chapitre 1.)

import math
x = 1e12
naive = math.sqrt(x + 1) - math.sqrt(x)
stable = 1 / (math.sqrt(x + 1) + math.sqrt(x))
# naive  : 5.00003807246685e-07
# stable : 4.999999999998749e-07

Les deux racines valent $\approx 10^6$ et diffèrent de $\approx 5\cdot 10^{-7}$ : leur soustraction efface $13$ chiffres communs sur les $16$ disponibles — il ne reste que $3$ chiffres fiables, et la version naïve est fausse dès le cinquième chiffre. La reformulation par la quantité conjuguée,

$$\sqrt{x+1}-\sqrt{x}=\frac{1}{\sqrt{x+1}+\sqrt{x}},$$

remplace la soustraction de proches par une addition : tous les chiffres survivent. (La quantité conjuguée du cours de mathématiques n'est donc pas qu'une astuce de calcul de limites : c'est un outil de stabilité numérique — même équivalence mathématique, comportements machine opposés, comme la variance du chapitre 4.)

import random, time
for d in (1000, 10_000, 100_000):
    a = random.randrange(10 ** (d - 1), 10 ** d)
    b = random.randrange(10 ** (d - 1), 10 ** d)
    debut = time.perf_counter()
    for _ in range(100):
        c = a * b
    print(d, (time.perf_counter() - debut) / 100)
# temps typiques :  3e-6 s ;  9e-5 s ;  3e-3 s  — x30 quand d x10 : ni O(1) ni O(d)

Le temps croît environ comme $d^{1,6}$ (exposant de Karatsuba : ${\log }_{2}3\approx 1,585$ — l'algorithme interne de Python est un « diviser pour régner » sur les chiffres, intermédiaire entre l'école et l'optimal) : la multiplication des grands entiers est une vraie fonction croissante de leur taille. Critique de l'analyse du chapitre 5 : pour puissance(2, n), les $O(\log n)$ multiplications portent sur des nombres de plus en plus longs — le dernier produit manipule $\sim n$ bits et coûte à lui seul plus que tous les précédents ; le coût total est dominé par la taille du résultat ($n$ bits), pas par le compte des multiplications. L'analyse « $O(\log n)$ » reste juste en nombre de multiplications, et c'est la bonne mesure quand les nombres sont bornés (flottants, calcul modulaire — où la réduction modulo $p$ borne tout, exercice 7 du chapitre 5) ; elle cesse d'être un temps quand les opérandes enflent. (C'est exactement la « difficulté à évaluer la complexité » que signale le programme : toute analyse repose sur un modèle de coût, et le modèle « opération arithmétique $=O(1)$ » a un domaine de validité qu'il faut savoir énoncer.)

def proches(a: float, b: float, rel: float = 1e-9, abs_: float = 1e-12) -> bool:
    return abs(a - b) <= max(rel * max(abs(a), abs(b)), abs_)

assert proches(0.1 + 0.2, 0.3)                    # le classique
assert proches(1e15 + 1.0, 1e15)                  # grands : le RELATIF juge
assert proches(1e-15, 0.0)                        # près de zéro : l'ABSOLU sauve
assert not proches(1.0, 1.001)

Pourquoi le relatif : pour des grandeurs de l'ordre de $10^{15}$, l'écart d'arrondi normal est de l'ordre de $10^{-1}$ (précision relative $10^{-16}$) — une tolérance absolue fixe de $10^{-12}$ déclarerait différents deux calculs parfaitement concordants. Pourquoi l'absolu : si $b=0$, le terme relatif vaut $\text{rel}\cdot |a|$, et le test $|a-0|\le \text{rel}\cdot |a|$ n'est vrai que pour $a=0$ exactement — comparer à zéro exigerait l'exactitude, précisément ce qu'on fuit ; le plancher absolu rétablit une zone de tolérance autour de $0$. Le max des deux critères couvre ainsi toute la droite réelle. (C'est, à la lettre, le contrat de math.isclose de la bibliothèque standard — qu'on a maintenant les moyens de lire en connaisseur, et dont on comprend les deux paramètres.)

Mathématiques : l'équation caractéristique $r^2=\frac{13}{3}r-\frac{4}{3}$ a pour racines $r=\frac{1}{3}$ et $r=4$ (produit $\frac{4}{3}$, somme $\frac{13}{3}$ ✓) ; la solution générale est $u_n=\alpha 3^{-n}+\beta 4^n$, et les conditions initiales donnent $\alpha =1$, $\beta =0$ : $u_n=3^{-n}$ exactement.

Machine :

u, v = 1.0, 1/3
for _ in range(29):
    u, v = v, 13/3 * v - 4/3 * u
# v vaut   -14.3  au lieu de 3**-30   4.9e-15

Catastrophe totale : $u_{30}$ calculé vaut environ $-14$ — ni la bonne valeur, ni le bon ordre de grandeur, ni même le bon signe. Explication : $\frac{1}{3}$ n'est pas représentable — le $u_1$ machine vaut $\frac{1}{3}+\delta$ avec $\delta \approx 10^{-17}$, soit $\beta \approx \delta \ne 0$ : la composante parasite $\beta \cdot 4^n$, invisible au départ, est multipliée par $4$ à chaque pas et dévore la solution vraie qui, elle, est divisée par $3$. Au rang $n$, le parasite vaut $\sim 10^{-17}\cdot 4^n$ : il dépasse $3^{-n}$ dès $n\approx 15$ et tout est perdu. L'algorithme est instable : il amplifie exponentiellement la moindre erreur d'entrée — aucun raffinement d'arrondi ne le sauvera.

Le calcul correct : ne pas utiliser cette récurrence — calculer directement 3.0 ** -n (stable), ou dérouler la récurrence en exact avec le type Fraction (chapitre 4 des mathématiques de l'atelier : l'arithmétique rationnelle de Python est exacte, au prix de numérateurs qui enflent). (Leçon finale du chapitre : la frontière ne passe pas entre « bonnes et mauvaises machines » mais entre algorithmes stables et instables — une récurrence mathématiquement irréprochable peut être numériquement suicidaire, et c'est l'analyse, pas le test sur trois valeurs, qui le révèle : $u_5$ machine était encore juste à $10^{-12}$ près.)