Moins de portes pour la multiplication

Quel est le meilleur résultat pour le nombre de portes dans un circuit multipliant deux entiers de n bits?

La méthode évidente génère des portes . Il existe de meilleures approches avec les portes et . $\theta(n^2)$ $\theta(n\log n \log\log n)$ $\theta(n\log n2^{\log^*(n)})$

Je n'ai trouvé aucune famille de circuits booléens capable de gérer la multiplication avec portes . Je me demande si une telle famille de circuits existe. $n\log n$

cc.complexity-theory circuit-complexity Amir
la source

vous cherchez un circuit arithmétique ou un circuit booléen?

Suresh Venkat

Je recherche un circuit booléen.

Amir

pour mémoire, quel est l' algorithme

? cela n'utiliserait-il pas autant de portes?

O (n \log n)

$O(n \log n)$

vzn

@vzn Non, l'algorithme de Martin Fuerer est le plus connu, et il donne un circuit avec des portes

. Schonhage-Strassen est en fait utilisé dans certains systèmes d'algèbre informatique pour de très grands nombres.

O (n \log n 2^{\log^{*} n})

$O(n\log n 2^{\log^* n})$

Sasho Nikolov

Il y a des frais généraux pour transformer une MT en circuit. Un algorithme de temps

ne donne pas un circuit avec des portes

. La traduction générale ne peut pas être meilleure que la complexité du circuit du problème de valeur de circuit. D'un autre côté, la meilleure complexité uniforme n'implique pas une limite inférieure sur la complexité du circuit car il y a un surdébit également dans le sens inverse, c'est-à-dire qu'il peut y avoir des circuits de taille

même s'il n'y a pas de MT avec ce fonctionnement le temps de la multiplication.

t (n)

$t(n)$

t (n)

$t(n)$

O (n \lg n)

$O(n\lg n)$

Kaveh

Réponses:

Vous trouverez ci-dessous une enquête détaillée de 2008 qui couvre les meilleurs algorithmes théoriques de multiplication, y compris ceux discutés dans les commentaires de votre question (y compris l'algorithme de Schönhage – Strassen et l' Algorithme de Fuerer, voir page 335 de l'enquête). Cependant, l'implémentation est une question différente et certains de ces algorithmes peuvent ne pas être considérés comme pratiques; l'enquête ne couvre pas les implémentations pratiques. Bien que l'enquête comprenne des algorithmes pour les polynômes, les séries de puissance, les nombres réels et les nombres 2-adiques, les entiers en sont un cas particulier (voir la figure 1 à la page 336). $O(n\log n \, 2^{\log^* n})$

La multiplication rapide et ses applications , Bernstein (Théorie algorithmique des nombres / Publications MSRI / Volume 44, 2008)

vzn
la source

Le document lié n'a pas les pages 335 ou 336. Peut-être vouliez-vous créer un lien vers un autre fichier?

argentpepper

Oops! merci pour le pourboire. la version ci-dessus marquée comme brouillon. cette version avec les pg #s cités est peut-être définitive?

vzn

@vzn:

$\:$

\log^{*} (n)

$\log^*(n)$

$\;\;\;\;$