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.
- Méthode du cancre.
- Méthode de Karatsuba (publiée en 1962).
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).
On sépare chaque facteur en deux parties
puis on effectue les multiplications suivantes :
Le résultat est ensuite
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
- Pourquoi la méthode du cancre fonctionne-t-elle ? Les deux facteurs jouent des rôles différents; lequel choisir pour quel rôle ?
- Utilisez la méthode de Karatsuba pour calculer 3116 x 1014. Pourquoi cette méthode fonctionne-t-elle ?
- 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 ?
- 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.
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.