Arno Eigenwilling & Kurt Mehlhorn

Résumé de l’article

Après avoir rappelé la méthode scolaire généralement utilisée pour effectuer une multiplication, et étudié la complexité suivant le nombre de chiffres, l’auteur présente la méthode de Karatsuba, publiée en 1962, dont l’idée de base est d’organiser différemment le calcul. En introduisant des soustractions, il diminue le nombre total d’opérations.
Il donne les explications détaillées pour les multiplications de nombres à 2 chiffres, puis à 4 chiffres et propose la généralisation :
- ramener la multiplication de 2 nombres à n chiffres à des multiplications de nombres à n/2 chiffres, moins couteuses en opérations, ce qui est une « récursion ».
- diminuer d’un à chaque étape le nombre d’opérations intermédiaires, ce qui au final fournit une énorme économie,

Plan de l’article

• 1. La méthode scolaire
• 2. L’algorithme de Karatsuba

Lire l’article en ligne
Télécharger l’article en pdf dans son intégralité
<redacteur|auteur=500>