Accueil » Publications » Le Bulletin Vert » Pour chercher et approfondir » Faire une multiplication … plus vite (...)
  APMEP   Faire une multiplication … plus vite qu’à l’école

Article du bulletin 499

Adhérer ou faire un don

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é

(Article mis en ligne par Armelle BOURGAIN)
 Accueil   Plan du site   Haut de la page   Page précédente