|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
MULTIPLICATION Chiffre à Chiffre "au fil de l'eau" Algorithme
de multiplication de deux nombres, chiffre après chiffre, pour implémentation
sur calculette
ou ordinateur
en cas de très grands nombres. |
Anglais: algorithm for multiplication of large
numbers
Long multiplication = multiplication posée, comme en primaire
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Multiplication posée Multiplication posée classique avec mise en
évidence des produits partiels complets. Lorsque
ce nombre comprend des dizaines, il y a production d'une retenue dont il faut
tenir compte:
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Principe de l'algorithme On va
calculer les produits partiels complets les uns après les autres. En
parallèle, on va effectuer les additions au fur et à mesure, tout en tenant
compte des retenues.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Calcul de la position du produit
partiel Exemple: 2 x 3 = 6
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||
|
|
Entrer le
nombre A et entrer le nombre B. Les transformer en listes de chiffres. Préparer
une liste C pour y loger les chiffres du produit. Boucles
d'exploration en i et j des chiffres de A et des chiffres de B. Le
produit des chiffres pointés par (i, j) est ajouté au contenu éventuel du nombre dans C en position m
= (i + j – 1). Tout de
suite, la retenue éventuelle est traitée: elle est ajoutée au nombre en
position suivante dans C(m + 1). Tandis que la dizaine correspondante est
retranchée du nombre en cours C(m). La
propagation d'une nouvelle retenue éventuelle est traitée avec le même principe.
Après
épuisement des chiffres, édition du résultat. |
|
|
|
|||
|
Pourquoi se casser la tête ? |
On se contente de faire pratiquement comme à la
main:
|
||
|
|
Commentaires Même départ que précédemment. Le produit C est initialisé à 0. Boucle en i et j, calcul de du produit partiel. Il est simplement ajouté à la valeur courante de C,
pondéré de la puissance de 10 correspondant à sa position. Exemple de calcul
|
||
|
|
||
|
Exemple de calcul
|
Commentaires Entrée des nombres A et B au clavier Conversion des nombres en chaines de caractères
pour être en mesure de traiter chaque caractère, chaque chiffre. Avec [ : : -1],
la chaine de caractères est inversée. La quantité de chiffres (longueur de la chaine)
est calculée en lA et lB. La liste des chiffres de C est mise à 0 avec [0] multiplié par la longueur maximale du
produit (lC = lA+lB). Le nombre décimal C est lui aussi positionné à 0. Boucle sur les chiffres de A avec le pointeur i. Boucle sur les chiffres de B avec le pointeur j. Calcul des chiffres de A et B en position i et j. Calcul du produit de ces deux chiffres.
L'instruction int (pour integer = nombre entier) convertit le caractère en
nombre. Calcul de l'emplacement dans C où loger le
produit: m = i + j – 1 Le produit calculé est ajouté au contenu existant
de C[m]. Calcul de la retenue: quotient (//) du produit par 10 pour avoir les dizaines. S'il y a retenue, elle est ajoutée à C[m+1] et la dizaine correspondante est
retranchée de C[m]. On recommence avec le
chiffre suivant (m + 2) en cas de survenue d'une nouvelle retenue en cascade. En fin de programme, on restitue le nombre
décimal à partir de la liste de ses chiffres et on imprime le résultat,
précédé du calcul direct pour vérification. |
|
Voir Programmation
Python – Index
|
|
||
|
|
Commentaires Après conversion des nombres A et B en base 10
pour disposer de la suite des chiffres dans l'ordre inversé, calcul de tous
les produits partiels. Simples additions de ces produits partiels pondérés par une
puissance de 10 pour les positionner à leur place dans le produit. |
|
|
|
||
|
|
Commentaires Réinitialisation générale. Entrée des nombres A et B et conversion en base 10
qui produit la liste des chiffres en commençant par les unités (le sens dont
nous avons besoin). Création de la liste C, remplie d'autant de 0 que
la taille max du produit. Boucles en i et j jusqu'à la fin donnée par nops, instruction qui compte les éléments de la
liste. Calcul de m, pointeur de la liste C. Calcul du produit tel quel; il est ajouté à la
valeur existante en C. Calcul de la retenue avec la division par 10 du
produit (iquo). S'il y a retenue: report sur le chiffre suivant
(m+1) et soustraction de la dizaine sur C(m). Même opération en cas de création de retenue en
position m + 1. Fin des boucles (od:
od:) Édition du résultat: la liste C (notez
l'inversion des chiffres) et le produit pour vérification; puis, le produit
trouvé par notre calcul. Le nombre est reconstitué en ajoutant les
chiffres de C, chacun pondéré par la puissance de 10 qui convient. |
|
|
|
Test de capacité Sachant que pour les 9-repdigits:
999k x 999k
= 9k-1 8
0k-1 1 |
|
Voir Programmation Maple – Index
|
|
|||
|
|
But Les nombres à multiplier se présentent en blocs
de quatre chiffres (exemple). Comment les multiplier et les présenter en bloc
de quatre chiffres. Principe Rigoureusement le même algorithme que
précédemment en changeant chiffre par bloc. Commentaires Réinitialisation générale. Déclaration du fait
que le bloc vaut quatre chiffres. Entrée des nombres (ici 3 blocs de quatre
chiffres). Formation des listes de blocs pour A et pour B. Calcul du produit pour vérification. Formation de la liste C pour y loger le produit. Programme identique au précédent. La notion de
retenue est amplifiée par un facteur 10bl
(la taille du bloc en exposant). En final, calcul du nombre trouvé à partir des
listes de blocs. Edition des blocs de A, B et C Edition du nombre décimal et différence avec ce
qu'il faut trouver. Rappel: la suite des
blocs est inversée par rapport à la normale. |
||
|
|
Exemple de calcul avec 6 blocs x 5 blocs. |
||
|
Multiplications longues Avec ces
méthodes, il est possible de réaliser
des multiplications avec des nombres aussi grands que l'on veut, dans la
limite de la taille des listes supportables par le logiciel utilisé. Exemple avec le programme Python: nombre
A 123456789123456789123456789 nombre
B 123456789123456789123456789 Calcul:
15241578780673678546105778281054720515622620750190521 Vérification:15241578780673678546105778281054720515622620750190521 Intérêt Intérêt relativement
modeste, car les logiciels, comme
les calculateurs
en ligne, vous donnent un accès à de grands nombres. Pour les calculettes, elles sont souvent dotées
de 32 chiffres, comme celle de votre ordinateur. Exemple de présentation des
trente-deux chiffres:
Pour beaucoup plus de
chiffres, il faudra séparer les nombres en plusieurs blocs
pour pouvoir les entrer, les traiter et les sortir. C'est le principal
intérêt de la méthode selon l'algorithme présenté. Accélération Pour finir, et pour les curieux,
il est possible d'accélérer le calcul des multiplications en utilisant des algorithmes appropriés. |
|
Suite |
|
|
Multiplication |
|
|
Voir |
|
|
Sites |
|
|
Cette page |
