Karatsuba Anatolii Alexevich

En 1962, le mathématicien russe Anatolii Alexevich Karatsuba publie une méthode pour multiplier plus vite de grands entiers. Au lieu de calculer séparément tous les produits de chiffres, elle coupe chaque nombre en deux morceaux.

Pour 12 × 34, la méthode combine seulement trois petits produits : 1 × 3, 2 × 4 et (1 + 2) × (3 + 4). Une soustraction retrouve le terme manquant, puis les dizaines et les centaines remettent les morceaux à leur place.

Anatolii Alexevich Karatsuba (1937-2008) est un mathématicien russe connu pour l'algorithme de multiplication rapide publié en 1962. Cette méthode s'applique aux entiers, en traitant séparément le signe si nécessaire, et remplace quatre multiplications de demi-tailles par trois. Les additions et soustractions supplémentaires sont moins coûteuses à grande taille.

Dans une base entière B supérieure ou égale à 2, on choisit une longueur de coupure m. Deux entiers positifs s'écrivent alors x = aB^m + b et y = cB^m + d, où a et c sont les morceaux de poids fort, tandis que b et d sont les morceaux de poids faible. L'identité utilisée est :Elle ne demande que les produits ac, bd et (a + b)(c + d). La même décomposition peut être appliquée récursivement à chacun d'eux, jusqu'à une taille où la multiplication directe est choisie.

Pour deux entiers de n chiffres et des coupures équilibrées, cette récursion conduit à un coût asymptotique en O(n^log₂3), soit environ O(n^1,585), inférieur à O(n²). Karatsuba a aussi travaillé en théorie analytique des nombres, avec un théorème d'approximation sur les séries de Fourier, et en théorie de la complexité, où il a affiné le théorème de Moore relatif aux machines de Moore.

On veut calculer 12 × 34 en base 10. Les données sont les deux entiers 12 et 34, une coupure après un chiffre, les morceaux 1 et 2 pour 12, puis 3 et 4 pour 34.

1. On calcule le produit des morceaux de poids fort : 1 × 3 = 3. Ce résultat fournira les centaines.

2. On calcule le produit des morceaux de poids faible : 2 × 4 = 8. Ce résultat fournira les unités.

3. On calcule le troisième produit : (1 + 2) × (3 + 4) = 3 × 7 = 21. Le coefficient des dizaines vaut alors 21 − 3 − 8 = 10.

4. On replace les trois résultats : 3 × 100 + 10 × 10 + 8 = 408. Le contrôle par la distributivité donne 12 × 34 = 12 × (30 + 4) = 360 + 48 = 408. Le calcul utilise trois multiplications de chiffres au lieu des quatre produits 1 × 3, 1 × 4, 2 × 3 et 2 × 4 de la décomposition scolaire.

Pour multiplier de très grands entiers, on découpe les opérandes en blocs puis on applique récursivement l'identité de Karatsuba. Pour de petites tailles, une multiplication directe reste préférable, car les additions et les appels récursifs ont aussi un coût.

Pour comparer deux algorithmes, on compte leur croissance lorsque le nombre de chiffres augmente. La méthode scolaire demande un nombre de produits qui croît comme n², tandis qu'une décomposition équilibrée de Karatsuba croît comme n^log₂3.

Pour vérifier une implémentation, on conserve un calcul témoin comme 12 × 34. Les trois produits doivent être 3, 8 et 21, le coefficient central doit être 10, et la recomposition doit donner exactement 408.

Karatsuba et l'algorithme de Karatsuba. Le premier nom désigne Anatolii Alexevich Karatsuba, le mathématicien russe né en 1937 et mort en 2008. Le second désigne sa méthode de multiplication publiée en 1962. Une date de vie concerne la personne ; une décomposition en trois produits concerne l'algorithme.

Algorithme de Karatsuba et stratégie « diviser pour régner ». Diviser pour régner est une stratégie générale qui découpe un problème en sous-problèmes. Karatsuba en est une réalisation précise : pour une multiplication, le test distinctif est le remplacement de quatre produits de demi-tailles par trois.

Petits entiers. La meilleure complexité asymptotique ne garantit pas un calcul plus rapide à toute taille. Les additions, soustractions et découpages peuvent coûter davantage que le produit direct. Une implémentation choisit donc un seuil mesuré et arrête au plus tard la récursion lorsque les blocs n'ont plus qu'un chiffre dans la base retenue.

Longueurs impaires. Deux opérandes n'ont pas toujours le même nombre de chiffres, ni un nombre pair de chiffres. On choisit une même puissance B^m pour les deux découpages et l'on autorise des morceaux de longueurs différentes ou des zéros initiaux. L'identité algébrique reste valide.

Entiers négatifs. La décomposition explique directement le calcul sur des valeurs non négatives. Pour des entiers signés, on multiplie les valeurs absolues, puis on applique la règle des signes ; il ne faut pas découper naïvement l'écriture avec son signe.

Lecture de la complexité. O(n^log₂3) décrit une croissance quand n devient grand, sous une récursion équilibrée et un modèle de coût par opérations sur les chiffres. Ce symbole ne donne ni le temps exact d'un calcul, ni un seuil universel de bascule.

Le glossaire algorithme précise ce qui transforme une suite d'opérations en procédure définie et exécutable.

La fiche série de Fourier éclaire l'autre domaine cité parmi les travaux de Karatsuba : l'approximation par des séries trigonométriques.

La fiche théorie analytique des nombres situe le cadre où des outils d'analyse servent à étudier les nombres entiers.