Corrigé CCINP 2026 Informatique MP — Problème 1 (Q1 à Q11) : Multiplication de grands entiers (Karatsuba)

Sujet officiel du concours CCINP, session 2026, épreuve Informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un entier naturel $n$ s'écrit en base $b ⩾ 2$ sous la forme $n = \sum_{i} n_{i} b^{i}$ avec $n_{i} \in {0, \dots, b - 1}$ ; les machines se limitent à un nombre borné de chiffres (32 à 64). On prend $b = 2$ et le langage est Python. Un entier est codé par la liste de ses bits, poids faibles en tête : [0, 1, 0, 1, 0, 1] code $42 = 2 + 8 + 32$ .

Q1. Conséquence de la limitation matérielle sur les entiers manipulables ? Est-ce le cas en Python ?
Q2. Écrire bit_to_int(bit_lst), de coût linéaire.
Q3. Décrire en français un algorithme de somme de deux listes de bits.
Q4. Écrire sum_bits(b_lst_1, b_lst_2) (listes de même longueur), sans passer par les entiers Python.
Q5. Écrire complement(lst_bits, size) : nouvelle liste de taille size codant le même entier ; l'exécution s'interrompt si size est trop petit.
Q6. Écrire int_to_bit, qui renvoie la liste des bits d'un entier.

Pour $u$ et $v$ codés sur $k$ bits ( $k$ pair), on coupe $u = d_{u} + b^{k /2} f_{u}$ et $v = d_{v} + b^{k /2} f_{v}$ (moitié basse, moitié haute), d'où

$u \times v = d_{u} d_{v} + b^{k /2} (f_{u} d_{v} + f_{v} d_{u}) + b^{k} f_{u} f_{v} . (1)$

On calcule récursivement les quatre produits ; découpe, décalages et additions coûtent $O (k)$ . On note $C (k)$ le coût.

Q7. Établir et résoudre l'équation vérifiée par $C (k)$ ( $k$ puissance de 2, $C$ croissante).
Q8. Avec la relation de Karatsuba (admise)

$u \times v = d_{u} d_{v} + b^{k /2} (f_{u} f_{v} + d_{u} d_{v} - (f_{u} - d_{u}) (f_{v} - d_{v})) + b^{k} f_{u} f_{v}, (2)$

combien de multiplications récursives distinctes ? Équation de complexité (on admet ensuite $O (k^{l o g_{2} 3})$ ).
Q9. À quoi correspond la multiplication par $b^{i}$ sur la liste des chiffres ?
Q10. Écrire shift(lst_bits, i), qui renvoie une nouvelle liste.
Q11. On dispose de sum_bit_lst et sub_bit_lst (somme et différence, coût linéaire). Compléter A, B et C :


def karatsuba(lst1, lst2):
    n = max (len(lst1), len(lst2))
    lst1 = complement(lst1, n)
    lst2 = complement(lst2, n)
    if n == 0:
        # A : compléter ici
    if n == 1:
        # B : compléter ici
    else:
        h = n//2
        d1 = lst1[0:h]
        f1 = lst1[h:]
        d2 = lst2[0:h]
        f2 = lst2[h:]
        # C : compléter ici

Corrigé

Q1. Avec $p$ bits, on ne représente que $2^{p}$ entiers distincts : l'ensemble des entiers machine est fini ( $[[0, 2^{p} - 1]]$ en non signé, $[[- 2^{p - 1}, 2^{p - 1} - 1]]$ en complément à deux). Un calcul dont le résultat sort de cet intervalle subit un dépassement de capacité : le résultat est calculé modulo $2^{p}$ (par exemple, sur 64 bits signés, $2^{63} - 1 + 1$ donne $- 2^{63}$ ). Ce n'est pas le cas en Python : ses entiers (int) sont en multi-précision, stockés sur autant de mots machine que nécessaire ; seule la mémoire les borne (et le coût des opérations croît avec leur taille).

Q2. On applique le schéma de Horner en partant du bit de poids fort : $n = n_{0} + 2 (n_{1} + 2 (n_{2} + \dots))$ .


def bit_to_int(bit_lst):
    valeur = 0
    for i in range(len(bit_lst) - 1, -1, -1):
        valeur = 2 * valeur + bit_lst[i]
    return valeur

Invariant : après le traitement de l'indice $i$ , valeur $= \sum_{j ⩾ i} n_{j} 2^{j - i}$ ; pour $i = 0$ c'est l'entier codé. Une opération par bit : coût linéaire. On obtient bien bit_to_int([0, 1, 0, 1, 0, 1]) == 42 et 0 pour la liste vide.

Q3. C'est l'addition posée de l'école primaire, en base 2. On parcourt les deux listes du début (poids faibles) vers la fin, en tenant une retenue $r$ , nulle au départ. Au rang $i$ , on calcule $s = a_{i} + b_{i} + r \in {0, 1, 2, 3}$ ; le bit de rang $i$ du résultat est $s mod 2$ et la nouvelle retenue $s / / 2 \in {0, 1}$ . Après le dernier rang, la retenue restante devient le bit de poids fort du résultat (la somme de deux entiers de $k$ bits tient sur $k + 1$ bits).

Q4.


def sum_bits(b_lst_1, b_lst_2):
    k = len(b_lst_1)          # les deux listes ont la même longueur
    res = []
    retenue = 0
    for i in range(k):
        s = b_lst_1[i] + b_lst_2[i] + retenue
        res.append(s % 2)
        retenue = s // 2
    res.append(retenue)
    return res

Invariant : après le rang $i$ , $\sum_{j ⩽ i} res [j] 2^{j} + retenue \cdot 2^{i + 1} = \sum_{j ⩽ i} (a_{j} + b_{j}) 2^{j}$ (on a seulement réécrit $s = (s mod 2) + 2 (s / /2)$ ). En fin de boucle, la retenue ajoutée en dernière position donne exactement $a + b$ . La liste renvoyée est neuve, de longueur $k + 1$ ; le coût est linéaire. Essai : sum_bits([1, 1], [1, 0]) vaut [0, 0, 1], soit $3 + 1 = 4$ ; vérifié aussi sur 3 000 couples aléatoires contre bit_to_int.

Q5. Compléter par des zéros en fin de liste, c'est-à-dire du côté des poids forts, ne change pas la valeur.


def complement(lst_bits, size):
    assert size >= len(lst_bits), "taille demandée trop petite"
    return lst_bits + [0] * (size - len(lst_bits))

L'opérateur + sur les listes construit une nouvelle liste : l'argument n'est pas modifié (et même pour size == len(lst_bits), on renvoie une copie). Ce que le correcteur attend : « supérieur » s'entend au sens large ; une assertion stricte ferait échouer karatsuba (Q11), qui appelle complement(lst1, n) avec n égal à la longueur de la plus longue liste.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →