Algorithme De Multiplication


Algorithme De Multiplication

Algorithme de multiplication

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

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).

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.

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.

Autres multiplications

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Algorithme de multiplication ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme De Multiplication de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme de multiplication — 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 1… …   Wikipédia en Français

  • Algorithme De Strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969.[1] La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme de strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969.[1] La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme de Strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969[1]. La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme de Fürer — L algorithme de Fürer est un algorithme de multiplication de très grands entiers. L algorithme a été publié par Martin Fürer de Penn State en 2007[1]. Cet algorithme possède asymptotiquement la plus faible complexité parmi les algorithmes de… …   Wikipédia en Français

  • Algorithme de Karatsuba — L algorithme de Karatsuba (1960) est une méthode permettant de multiplier rapidement deux nombres avec une complexité en au lieu de O(n2) pour la méthode naïve. Note : . Énoncé Pour multiplier deux nombres de n chiffres, la méthode naïve… …   Wikipédia en Français

  • Algorithme Toom-Cook — L algorithme de Toom Cook, aussi appelé Toom 3, est un algorithme de multiplication dû à Andrei Toom (en) et Stephen Cook, utilisé pour multiplier deux grands nombres. Ces grands nombres sont découpés en plus petits nombres sur lesquels on… …   Wikipédia en Français

  • Algorithme de Schönhage-Strassen — L algorithme de Schönhage Strassen est un algorithme de multiplication de grands entiers par transformée de Fourier rapide publié en 1971 par Arnold Schönhage et Volker Strassen[1]. Dans le modèle de complexité courant des machines de Turing à… …   Wikipédia en Français

  • Multiplication — Cet article concerne l opération arithmétique. Pour les autres significations, voir Multiplication (homonymie). La multiplication de 4 par 3 donne le même résultat que la multiplication de 3 par 4 La multiplica …   Wikipédia en Français

  • Algorithme D'Euclide Étendu — L algorithme d Euclide étendu est une variante de l algorithme d Euclide qui permet, à partir de deux entiers a et b, de calculer non seulement leur plus grand commun diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout (deux …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.