Ganzzahlmultiplikation, wenn eine ganze Zahl festgelegt ist

35

Sei eine feste positive ganze Zahl der Größe Bits.An

Man darf diese ganze Zahl entsprechend vorverarbeiten.

Wie komplex ist die Multiplikation anderen positiven ganzen Zahl einer Größe von Bits ?BmAB

Beachten Sie, dass wir bereits -Algorithmen haben. Die Frage hier ist, ob wir von etwas klügerem nehmen können? ϵ = 0(max(n,m))1+ϵϵ=0

T ....
quelle
6
Mit konstruieren Sie einfach eine Nachschlagetabelle mit Einträgen. (Offensichtlich ist dies nicht das, was Sie wollten, aber ich denke, Sie sollten Ihre Anforderungen A2n
präzisieren
9
Ich denke, dass die Frage im Standard-Booleschen Schaltungsmodell durchaus Sinn macht.
Noam
4
Können Sie die offensichtlichen Ober- und Untergrenzen und die besten Ihnen bekannten Ergebnisse zusammenfassen? Es zeigt, dass Sie sich für das Problem interessieren und darüber nachgedacht haben, und es gibt allen anderen mehr Anreiz, über Ihr Problem nachzudenken.
Robin Kothari
4
Ich denke, der Fragesteller bedeutet implizit, dass der vorverarbeitete Teil nur Platz einnehmen darf . (Der Matrixvektor mult hat diese Eigenschaft.)nO(1)
Ryan Williams
Ich würde gerne wissen, was Sie möchten. Ich habe das Gefühl, ich könnte hier endlose Fälle durchgehen. Dies ist meine erste Antwort, daher bin ich besonders froh, Ihnen so viele Informationen wie möglich zu geben. Wenn Sie möchten, können Sie mir eine E-Mail an [email protected] senden, und ich würde gerne noch viel mehr mit Ihnen zusammenarbeiten.
Matt Groff

Antworten:

20

Es ist zwar nicht immer der effizienteste Algorithmus, aber diese Frage hängt sehr eng mit den Additionsketten zusammen. jeder Algorithmus zur Berechnung von schnell durch Zugabe Ketten führt zu einem Algorithmus zur Berechnung f ( B ) = A B durch wiederholte Addition (jede Zugabe natürlich ist , um ein O ( n ) Betrieb). Im Gegensatz dazu führt ein schneller Algorithmus zum Berechnen von A B für jedes B zu einem schnellen Algorithmus zum Berechnen von AAf(B)=ABO(n)ABBANatürlich muss dieser Algorithmus nicht unbedingt die Form einer Additionskette haben. Dennoch scheint dies ein ausgezeichneter Ausgangspunkt zu sein. Schauen Sie sich http://en.wikipedia.org/wiki/Addition_chain an oder lesen Sie vol. 2 von The Art Of Computer Programming für weitere Details.

Steven Stadnicki
quelle
17

Um die Idee von Steven Stadnicki zu erweitern, können wir schnell einen naiven Algorithmus konstruieren, der besser als die Matrixmultiplikation mit der diskreten Fouriertransformation ist.

Wir zählen die Anzahl von Einsen in . Wenn weniger als die Hälfte der Bits Einsen sind, erstellen wir eine verknüpfte Liste ihrer Positionen. Zum Multiplizieren verschieben wir einfach B um jede Position in der Liste nach links (multiplizieren mit dem dargestellten Bit) und addieren die Ergebnisse.AB

Wenn mehr als die Hälfte der Bits Einsen sind, machen wir dasselbe wie oben, verwenden jedoch stattdessen die Nullen, um die Liste der Positionen aufzufüllen. Die Idee ist, dass wir diese Summe von der Summe subtrahieren, die durch Multiplikation mit allen erhalten würde. Um die Summe aller zu erhalten, verschieben wir um die Anzahl der Bits in A und subtrahieren B davon. Dann können wir unsere erhaltene Summe von der verknüpften Liste abziehen.BAB

Wir können das den naiven Linked-List-Algorithmus nennen. Seine Laufzeit ist im schlimmsten Fall , aber O ( | B | O(n2)im Mittel schneller als DFT für kleine| A| .O(|B||A|2π)|A|

Um die Idee der Listen optimal zu nutzen, setzen wir Divide-and-Conquer ein. Wir teilen in zwei Hälften und ermitteln die Größe der zugehörigen Listen mit dem naiven Algorithmus. Wenn sie größer als 5 sind, rufen wir den naiven Algorithmus erneut für Hälften auf, die größer als 5 sind, bis es uns gelingt, alle Hälften auf weniger als fünf zu reduzieren. (Dies liegt daran, dass wir dies auf 4 Subtraktionen reduzieren können)A

Noch besser ist, dass wir unseren Divide-and-Conquer-Algorithmus verbessern. Wir durchlaufen alle möglichen Kombinationen von Verzweigungen und suchen gierig die beste aus. Diese Vorverarbeitung dauert ungefähr so ​​lange wie die eigentliche Multiplikation.

Wenn wir bei der Vorverarbeitung uneingeschränkte Freiheit haben, lösen wir den optimierten Divide-and-Conquer-Algorithmus für alle Zweige optimal. Dies benötigt im schlimmsten Fall die Zeit , sollte jedoch durch Additionskettenverfahren optimal sein.O(2|A|)

Ich arbeite daran, genauere Werte für die obigen Algorithmen zu berechnen.

Matt Groff
quelle
Hi Matt: Was ist und | B | ? |A||B|
T ....
ist die Größe von A , im Allgemeinen die Anzahl der Elemente in A . Dies ist äquivalent zu Ihrem n , dh | A | n . Gleiches gilt für | B | . Diese Formel gilt jedoch immer noch, wenn n für A und B unterschiedlich ist . |A|AAn|A|n|B|nAB
Matt Groff
17

Die Arbeit Multiplikation mit einer Konstanten ist sublinear ( PDF ) gibt einen Algorithmus für Verschiebungs- / Additionsoperationen, wobeindie Größe der Konstante ist.O(nlogn)n

Im Wesentlichen funktioniert dies, indem die Bits in der Konstanten gesucht, verschoben und die zu multiplizierende Zahl nur für die 1- Bits in der Konstanten addiert werden (wie lange Multiplikation für Binär, wobei ein 0- Bit in der untersten zu multiplizierenden Zahl bedeutet Die Spitze wird nicht verschoben und hinzugefügt, während 1 Bit bedeutet, dass die Spitze verschoben und hinzugefügt wird. Dies ist jedoch immer noch O ( n ) , da die Konstante O ( n ) 1- Bit enthalten kann.1101O(n)O(n) 1

In dem Artikel wird dann über die Änderung der Zahlendarstellung der Konstanten in ein System mit zwei Basen gesprochen, bei dem die Nicht- Bits anscheinend spärlicher sind, wenn die Konvertierung korrekt durchgeführt wird (es ist ein sehr redundantes Zahlensystem). Sie berechnen, wie dünn es ist; Die Anzahl der Nicht-Null-Bits ist auf weniger als 0 ( n ) begrenzt , daher ist eine sublineare Anzahl von Additionen erforderlich. Es ist jedoch immer noch O ( n m0O(n)tatsächliche Operationen aufgrund derO(m)-Kosten jeder Addition (wobeindie Größe der Konstanten undmdie Größe der anderen Zahl ist).O(nmlogn)O(m)nm

Um Ihre Frage zu beantworten: Ja, es gibt ein ähnliches Ergebnis wie bei der Matrix-Vektor-Multiplikation, da Sie eine Beschleunigung erhalten, wenn sie konstant ist. aber natürlich ist diese Beschleunigung nur über naive Langmultiplikation möglich, und es gibt Multiplikationsalgorithmen, die weitaus besser sind als O ( n 2lognSie können mit diesem Algorithmus erhalten.O(n2logn)

Realz Slaw
quelle
@JAS das ist meine Spezialität: D.
Realz Slaw
3
Dies erschien in ARITH 2007 als dx.doi.org/10.1109/ARITH.2007.24 (der Vollständigkeit halber ).
András Salamon
10

Wie von Matt Groff vorgeschlagen, könnten Sie daran interessiert sein, in der Übungsgemeinschaft nach Inspirationen zu suchen (oder wenn in Ihrer Situation innerhalb der Bitbreite einer aktuellen CPU liegt). In der Tat wurde das Problem der ganzzahligen Multiplikation mit einer Konstanten von vielen Compilerschreibern und Schaltungsentwicklern in Betracht gezogen, obwohl sie normalerweise an einem "Multiplikator ohne Multiplikator" (Multiplizieren mit Verschiebung, Addition und Subtraktion) interessiert sind. Eine der frühen Referenzen, die mir bekannt sind, ist (das habe ich in Abschnitt 8.4 von Hacker's Delight erfahren.):n

Bernstein, R. (1986), Multiplikation mit ganzzahligen Konstanten. Software: Praxis und Erfahrung, 16: 641–652. doi: 10.1002 / spe.4380160704

Modernere Arbeit von Vincent Lefèvre kann gefunden werden hier (unbedingt Follow-up - Arbeiten zu sein , um zu sehen), und er stellt auch ein CMU - Projekt auf effiziente Schaltungssynthese (siehe die Referenzen dort). Das letztere Projekt berücksichtigt sogar die gleichzeitige Multiplikation mit einer Reihe von Konstanten.

PS: Ich empfehle Ihnen, in Betracht zu ziehen, Ihren Benutzernamen in einen erkennbaren Namen zu ändern.

Maverick Woo
quelle
8

Ich bin mir nicht sicher, ob dies für die Frage direkt relevant ist, aber das folgende elementare Ergebnis könnte von Interesse sein. Wenn eine feste natürliche Zahl , kann die Operation n k n durch einen sequentiellen Automaten realisiert werden, vorausgesetzt, dass n in umgekehrter binärer Notation geschrieben ist (d. H. Das am wenigsten signifikante Bit zuerst). Die Anzahl der Zustände des Automaten ist k / 2 r, wobei 2 r die größte Potenz von 2 ist, die k teilt . Beispielsweise wird die Operation n 6 n durch den folgenden Automaten realisiert. knknnk/2r2r2kn6nenter image description here

185=1+8+16+32+1286×185=1110=2+4+16+64+10241851001110111100110101000110011101

0011101000011110211200110201
which gives the correct output 01101010001. The type of sequential automaton I am using here was called subsequential by Schützenberger: as you can see there is an initial prefix (in green) and a terminal output function (also in green). For more details how this sequential machine can be computed in a systematic way, see this link.
J.-E. Pin
quelle
Could you elaborate on your comment?
J.-E. Pin
k is prime >2.
T....
The construction of a sequential automaton realizing the operation nkn can be done for any k. However, computing this automaton might be easier for k prime.
J.-E. Pin
k2r is exponential.
T....
k is a fixed constant, not related to n.
J.-E. Pin