Publication

Faster Integer Multiplication

2009
Conference Papers

Résumé

For more than 35 years, the fastest known method for integer multiplication has been the Schonhage-Strassen algorithm running in time O(n log n log log n). Under certain restrictive conditions, there is a corresponding Omega(n log n) lower bound. All this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is Theta(n log n). We take a major step towards closing the gap between the upper bound and the conjectured lower bound by presenting an algorithm running in time n log n2(O)(log* n). The running time bound holds for multitape Turing machines. The same bound is valid for the size of Boolean circuits.

Source officielle

https://infoscience.epfl.ch/entities/publication/aa410ee6-e9c4-4cf2-b6e5-f7b6596eb076

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

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

2009
Conference Papers

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/aa410ee6-e9c4-4cf2-b6e5-f7b6596eb076

À propos de ce résultat

Concepts associés (31)

Algorithme de multiplication d'entiers

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

Multiplication

thumb|La multiplication de 4 par 3 donne le même résultat que la multiplication de 3 par 4. La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division. Cette opération est souvent notée avec la croix de multiplication « × », mais peut aussi être notée par d'autres symboles (par exemple le point médian « · ») ou par l'absence de symbole. Son résultat s'appelle le produit, les nombres que l'on multiplie sont les facteurs.

Circuit booléen

vignette|Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles. C'est une façon de représenter une fonction booléenne. Un circuit booléen peut être utilisé pour reconnaître un langage formel, c'est-à-dire décider si un mot appartient ou non à un langage particulier. Les caractéristiques des circuits qui reconnaissent un langage permettent de définir (ou redéfinir) des classes de complexité.

Afficher plus

Publications associées (32)

Afficher plus

Faster Integer Multiplication

Chattez avec Graph Search

Additive and geometric transversality of fractal sets in the integers

EdgeAI-Aware Design of In-Memory Computing Architectures

In Medio Stat Virtus: Combining Boolean and Pattern Matching