Revisitons la multiplication !

Revisitons la multiplication !

Vous croyez déjà tout savoir sur la multiplication ? Vous allez être surpris !
Voici trois méthodes pour multiplier deux nombres entiers.

  • Multiplication posée du bon élève.
  • Multiplication posée de deux nombres, comment calculer le produit de deux nombres

     

  • Méthode du cancre.
  •  

    Comment multiplier deux nombres, méthode des paresseux

    Mode d’emploi : A gauche on prend toujours la moitié en arrondissant, s’il le faut, vers le bas ; à droite on prend toujours le double. Puis on supprime les lignes (en noir) dont le nombre gauche est pair et à droite on additionne les lignes restantes (en rouge).
     
     

  • Méthode de Karatsuba (publiée en 1962).
  • On sépare chaque facteur en deux parties

    Multiplication selon Karatsuba

    puis on effectue les multiplications suivantes :

    Algorithme pour la multiplication de Karatsuba

    Le résultat est ensuite

    Trouver le produit de deux nombres entiers

Remarque
L’idée de tout ça c’est de se ramener à des opérations élémentaires (opérations entre deux nombres entre 0 et 9). Sur un ordinateur le choix d’un bon algorithme peut accélerer considérablement le temps de calcul — quelques jours pour des facteurs constitués de plusieurs milliards de chiffres ! Le calcul avec de très grands nombres n’est pas une question purement théorique mais a beaucoup d’applications, notamment en théorie de cryptage.
 

Questions

  1. Pourquoi la méthode du cancre fonctionne-t-elle ? Les deux facteurs jouent des rôles différents; lequel choisir pour quel rôle ?
  2. Utilisez la méthode de Karatsuba pour calculer 3116 x 1014. Pourquoi cette méthode fonctionne-t-elle ?
  3. Avec la méthode classique (multiplication posée du bon élève), combien de multiplications élémentaires sont nécessaires pour calculer le produit de deux nombres à n chiffres ?
  4. En réitérant la méthode de Karatsuba on obtient un algorithme. Combien de multiplications élémentaires sont alors nécessaires pour calculer le produit de deux nombres à n chiffres ? Comparer avec l’algorithme classique.

Réponses
Cliquez pour afficher les solutions en format pdf.

Et pour finir une vidéo présentant une méthode qui produit une belle calligraphie — elle s’appelle donc la multiplication chinoise !

L’idée de base de la multiplications chinoise est le fait suivant : un ensemble de n droites parallèles coupe un autre ensemble de m droites parallèles en nxm points.

1 réponse
  1. Anthony
    Anthony dit :

    Toutes ces méthodes fonctionnent effectivement et depuis peu, il est également possible d’aboutir au résultat sans connaitre les tables de multiplication en procédant comme ceci :
    http://www.youtube.com/watch?v=T...

    En appliquant cette dernière méthode à l’exemple figurant dans cet article, il vient :
    36*54 = (40-4)*54 ou 54*4 est obtenue en prenant tour à tour le double de 54 puis le double du double de 54. Il suffit ensuite de copier/coller deux fois cette valeur (une fois pour 40 et une fois pour -4) et d’additionner.

    Répondre

Laisser un commentaire

Rejoindre la discussion?
N’hésitez pas à contribuer !

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *