Algorithme de multiplication
Un article de Wikipédia, l'encyclopédie libre.
Les techniques de multiplication permettent de calculer le résultat d'une multiplication.
Graphiquement, il s'agit de transformer un rectangle multiplicateur × multiplicande en une ligne, en conservant le nombre d'éléments.
Exemples:
Sommaire |
[modifier] Multiplication basée sur le nombre 2
Ce type de multiplication n'utilise que des additions et des multiplications ou des divisions par 2. Elle ne nécessite pas de connaître de table de multiplication (autre que la multiplication par 2).
[modifier] Multiplication basée sur la notation décimale
Ce type de multiplication utilise la décomposition décimale des nombres et nécessite de multiplier chaque chiffre du premier nombre par chaque chiffre du second. Elle nécessite de connaître les tables de multiplications d'un chiffre par un autre. Cependant, plusieurs types de disposition ont été adoptés au cours des temps.
- Technique de la multiplication en Chine antique
- Technique de la multiplication par glissement
- Technique de la multiplication par jalousies
- Technique de multiplication à la main (avec la table de multiplication)
- Technique graphique de multiplication par décompte de points d'intersection (ne nécessite pas de connaître la table de multiplication).
[modifier] Multiplication rapide
Les méthodes décrites dans les pages précédentes nécessitent pour la plupart de multiplier chaque chiffre du multiplicateur par chaque chiffre du multiplicande. Si ces deux nombres ont n chiffres, cela exige n² produits on dit que le calcul est en O(n²).
L'apparition des ordinateurs a permis et exigé la mise au point d'algorithmes plus rapides pour les grands nombres, avec un temps de calcul qui peut descendre à O(n1+ε), où ε est un réel positif arbitraire. La plupart des algorithmes ci-dessous ont été mis au point à partir de 1960.
- Algorithme de Karatsuba
- Algorithme Toom-Cook ou "Toom3"
- Algorithme de Schönhage et Strassen (méthode utilisant la transformée de Fourier rapide)
