Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de multiplication d'entiers
Résumé
Les algorithmes 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.
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).
Technique de la multiplication dans l'Égypte antique
(variante) Technique de multiplication dite russe
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).
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 chiffres, cela exige produits : on dit que le calcul a une complexité en temps quadratique, ou en .
L'apparition des ordinateurs a permis et exigé la mise au point d'algorithmes plus rapides pour les grands nombres, les premiers trouvés ayant une complexité en temps de la forme , où a est un réel positif strictement inférieur à 1. Arnold Schönhage et Volker Strassen ont conjecturé en 1971 que le produit de deux entiers a une complexité en , c'est-à-dire qu'il existe un algorithme ayant cette complexité en temps, et qu'aucun n'en a de meilleure. La meilleure complexité actuelle est depuis 2019 en mais n'est pas utilisable en pratique car elle n'est atteinte que pour des nombres extrêmement grands, supérieurs à dans la publication d'origine.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.