Écrire une fonction addition base(s, t, b) qui additionne deux…

On aligne les deux écritures à la même longueur en complétant à gauche par des zéros — l'ajout d'un zéro de poids fort ne change pas la valeur — puis on parcourt les positions de droite à gauche en propageant la retenue.


def addition_base(s, t, b):
    """Somme de deux écritures en base b, rendue en base b.

    Précondition : s et t ne contiennent que des chiffres
    valides en base b (donc d'indice < b dans CHIFFRES).
    """
    n = max(len(s), len(t))
    s = s.rjust(n, "0")
    t = t.rjust(n, "0")
    res = ""
    retenue = 0
    for i in range(n - 1, -1, -1):
        somme = CHIFFRES.index(s[i]) + CHIFFRES.index(t[i]) + retenue
        res = CHIFFRES[somme % b] + res
        retenue = somme // b
    if retenue > 0:
        res = CHIFFRES[retenue] + res
    return res

L'invariant. Après avoir traité les positions $i$ à $n - 1$ , la chaîne res contient l'écriture des chiffres de poids faible de la somme, et retenue vaut $0$ ou $1$ : c'est ce qui « déborde » vers la position suivante. La retenue reste toujours inférieure à $b$ car $2 (b - 1) + 1 < 2 b$ , donc $⌊ somme / b ⌋ \leq 1$ .

La validation.


for b in range(2, 17):
    for x in range(0, 60):
        for y in range(0, 60):
            got = addition_base(vers_base(x, b), vers_base(y, b), b)
            assert depuis_base(got, b) == x + y

$54000$ cas passent. Exemples : addition_base("1101", "111", 2) rend "10100" ( $13 + 7 = 20$ ), et addition_base("7EA", "1F", 16) rend "809" ( $2026 + 31 = 2057$ ).

Piège : oublier la dernière ligne. Si la retenue finale est non nulle et qu'on ne l'écrit pas, le résultat est faux d'exactement $b^{n}$ — et il est faux silencieusement.

Énoncé

Corrigé