Wenig Tore für die Multiplikation

Was ist das beste Ergebnis für die Anzahl der Gatter in einer Schaltung, die zwei n-Bit-Ganzzahlen multipliziert?

Das offensichtliche Verfahren erzeugt -Gatter. Es gibt bessere Ansätze mit und Gates. $\theta(n^2)$ $\theta(n\log n \log\log n)$ $\theta(n\log n2^{\log^*(n)})$

Ich konnte keine boolesche Schaltungsfamilie finden, die die Multiplikation mit Gates verarbeiten kann. Ich frage mich, ob es eine solche Familie von Schaltkreisen gibt. $n\log n$

cc.complexity-theory circuit-complexity Amir
quelle

Suchen Sie eine arithmetische Schaltung oder eine boolesche Schaltung?

Suresh Venkat

Ich suche eine Boolesche Schaltung.

Amir

Was ist der

-Algorithmus für die Aufzeichnung ? würde es nicht so viele Tore benutzen?

O (n \log n)

$O(n \log n)$

vzn

@vzn Nein, der Algorithmus von Martin Fuerer ist der bekannteste und ergibt eine Schaltung mit

Gates. Schönhage-Strassen wird tatsächlich in einigen Computeralgebrasystemen für sehr große Zahlen verwendet.

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

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

Sasho Nikolov

Es ist ein gewisser Aufwand, ein TM in einen Stromkreis umzuwandeln. Türen mit einem Zeit-

-Algorithmus ergeben keine Schaltung mit

Gates. Die allgemeine Übersetzung kann nicht besser sein als die Schaltungskomplexität des Schaltungswertproblems. Andererseits impliziert die beste gleichmäßige Komplexität keine Untergrenze der Schaltungskomplexität, da Overhead auch in umgekehrter Richtung besteht, dh es kann Schaltungen der Größe

selbst wenn bei dieser Ausführung kein TM vorhanden ist Zeit für die Multiplikation.

t (n)

$t(n)$

t (n)

$t(n)$

O (n \lg n)

$O(n\lg n)$

Kaveh

Antworten:

Im Folgenden finden Sie eine detaillierte Umfrage aus dem Jahr 2008, in der die wichtigsten theoretischen Multiplikationsalgorithmen behandelt werden, einschließlich der in den Kommentaren zu Ihrer Frage erörterten (einschließlich des Schönhage-Strassen-Algorithmus und des Fuerer-Algorithmus, siehe Seite 335 der Umfrage). Die Implementierung ist jedoch eine andere Sache, und einige dieser Algorithmen werden möglicherweise nicht als praktisch angesehen. Die Umfrage deckt keine praktischen Implementierungen ab. Obwohl die Umfrage Algorithmen für Polynome, Potenzreihen, reelle Zahlen und 2-adische Zahlen enthält, sind Ganzzahlen ein Sonderfall davon (siehe Abbildung 1 auf Seite 336). $O(n\log n \, 2^{\log^* n})$

Schnelle Multiplikation und ihre Anwendungen , Bernstein (Algorithmische Zahlentheorie / MSRI Publications / Band 44, 2008)

vzn
quelle

Das verlinkte Papier hat keine Seiten 335 oder 336. Vielleicht wollten Sie auf eine andere Datei verlinken?

Argentpepper

Hoppla! Danke für den Tipp. obige Version als Entwurf markiert. diese version mit zitierten pg #s ist vielleicht endgültig?

vzn

@vzn:

$\:$

\log^{*} (n)

$\log^*(n)$

$\;\;\;\;$