Das höchstwertige Bit der Ganzzahlmultiplikation und der binären Entscheidungsdiagramme

15

Sei und y zwei Binärzahlen mit n Bits und z = x y die Binärzahl (Länge 2 n ) des Produkts von x und y . Wir wollen das signifikanteste Bit z 2 n - 1 des Produkts berechnen .xynz=xy 2nxyz2n-1z=z2n-1z0

Um die Komplexität dieser Funktion im Modell von binären Entscheidungsdiagrammen (insbesondere von Einmal-Lese-Verzweigungsprogrammen) zu analysieren, versuche ich, nach äquivalenten Ausdrücken für den Fall zu suchen . Das erste offensichtliche Ding ist (hier sind und die entsprechenden ganzen Zahlen zu den Binärzahlen). Ich möchte eine Vorstellung davon bekommen, was passiert, wenn ich einige Eingabebits konstant halte. Wenn ich z. B. das höchstwertige Eingangsbit von und auf 0 setze, erhalte ich die konstante 0-Funktion. Bits mit geringerer Bedeutung haben jedoch keinen solchen Einfluss auf das Ergebnis.z 2 n - 1 = 1 x y 2 2 n - 1 x y x yz2n-1=1z2n-1=1xy22n-1xyxy

Gibt es andere äquivalente Ausdrücke für den Fall die mehr dazu beitragen, zu sehen, was passiert, wenn ich einige Eingabebits korrigiere? Gibt es verfeinerte Methoden, um das Produkt zweier Binärzahlen zu berechnen, die helfen können? Oder haben Sie eine andere Herangehensweise an dieses Problem?z2n-1=1

Marc Bury
quelle
Ich finde die drei Fragen im letzten Absatz ziemlich vage. Bitte überlegen Sie, eine konkretere Frage zu stellen.
Slimton
Die Fragen sind absichtlich vage. Vielleicht hat jemand einen neuen Ansatz oder neue Ideen für dieses Problem.
Marc Bury
Suchen Sie die Breite einer BDD für das Problem?
Sylvain Peyronnet
Ich interessiere mich für eine Untergrenze der BDD-Größe.
Marc Bury
1
Du meinst eine Polynomuntergrenze? Die Multiplikation ist in L, daher hat sie BDDs mit einheitlicher Polynomgröße (gerade Breite 5, da sie in einheitlichem ). NC1
Emil Jeřábek unterstützt Monica

Antworten:

5

Eine interessante Quelle ist DE Knuth: Die Kunst der Computerprogrammierung, Band 4, Fascicle 1, Bitwise Tricks & Techniques; Binäre Entscheidungsdiagramme , Addison-Wesley, Pearson Education 2009

Auf Seite 96 gibt es eine BDD für alle Bits von z = x⋅y, wobei x und y 3 Bits haben. Es zeigt sich, dass im Fall von 3 Bits BDD, das das höchstwertige Bit darstellt, 7 nicht-terminale Knoten aufweist. Siehe das Bild unten, ich habe es mit Ihren Indizes x = (x2, x1, x0) und y = (y2, y1, y0) neu gezeichnet.

Auf Seite 140 in Knuths Buch steht die Frage (Nr. 183), ob BDD das höchstwertige Bit für die Multiplikation zweier Zahlen mit unendlich vielen Bits darstellt (es wird "Begrenzung der führenden Bitfunktion" genannt) suchen nach! Die Antwort auf Seite 223 gibt die ersten Ebenen der resultierenden BDD an und erläutert die Anzahl der Knoten auf allen Ebenen. Leider gibt es keinen Algorithmus zum Erstellen einer solchen BDD.

Das höchstwertige Bit zur Multiplikation von zwei 3-Bit-Zahlen

Abb. 1: Das höchstwertige Bit zur Multiplikation von (x2, x1, x0) * (y2, y1, y0)

meolic
quelle
1
Vielen Dank für diesen Hinweis. Ich wusste nicht, dass binäre Entscheidungsdiagramme Teil dieser "Programmierenzyklopädie" sind.
Marc Bury