Arithmetische Hausaufgaben

Lyoshenka, Lyoshenka, tu mir einen Gefallen!
Lernen Sie, Aljoschenka, die Multiplikationstabelle!
Agnia Barto


Erste Aufgabe für einen Erstklässler. Es wird eine positive Zahl angegeben. Sie müssen eine andere Zahl damit multiplizieren, die im Voraus nicht bekannt ist. Die Frage ist, wie werden die edlen Dons dazu raten ??? Ein erfahrener Entwickler wird mit Sicherheit sagen, man sage, man setze den Multiplikator und mache sich keine Sorgen um mein Gehirn. Und vielleicht wird es von Grund auf falsch sein! Denn neben den Monstern von Alterra und Xilinx gibt es auch eine so wunderbare Familie wie den iCE-40 von Lattice . Ultra Mikrokonsum. Sehr billig Ja, das Problem ist, dass sie schmerzhaft klein sind, und leider gibt es dort keine Multiplikatoren. Ich bin darauf vor ungefähr 4 Jahren gestoßen, als ich einen bestimmten ADPCM-Codec vom Assembler adsp-2185 auf einen solchen Kristall portierte.

Nein, ohne einen Allzweckmultiplikator (für zwei Variablen) wäre das sicherlich nicht möglich gewesen. Ich musste es mit Stiften machen und er nahm den halben Kristall. Das Problem ist, dass er in jedem meiner Schritte dreschte, d.h. überhaupt keine Fenster. Neben der Multiplikation der Variablen im Algorithmus gab es feste Koeffizienten, die ebenfalls multipliziert werden mussten. Und es gab keine Möglichkeit, den Multiplikator dafür zu verwenden, es gab einfach kein Fenster mehr. Und da der Kampf in dem Projekt durch jede Zelle ging, war ich natürlich sehr daran interessiert, wie man ausweicht und die Eigenschaften dieser Koeffizienten verwendet, um das optimale Multiplikationsschema mit ihnen zu erzielen (kein Allzweckmultiplikator, sondern ein Multiplikationsgerät mit einer bestimmten Zahl!). Nun, wie ein kompletter Traum wird wahr - so dass die Multiplikationsschemata mit verschiedenen Koeffizienten einige gemeinsame Kristallressourcen optimal nutzen.

Von der Aufgabe für den Erstklässler gingen wir nahtlos zur Aufgabe für den Ingenieur und Mathematiker über. Wie erstelle ich ein optimales Multiplikationsschema für eine bestimmte Zahl?

Erinnern wir uns ein wenig daran, wie wir im Allgemeinen die Zahl A mit B multiplizieren.

1. Setzen Sie das Ergebnis zunächst auf Null.
2. Lassen Sie uns über Bits A gehen .
3. Wenn in Entladung 0, tun wir nichts.
4. Wenn in Bit 1, verschieben wir B um die entsprechende Anzahl von Bits und addieren zum Ergebnis.

Insgesamt ist es umso einfacher, mit der Zahl zu multiplizieren, je weniger Einheiten A in den Ziffern enthalten sind. Das Multiplizieren mit 2, 4 oder 8 ist einfach. Es ist nur eine Schicht erforderlich. Etwas schwerer mit 3, 5 oder 10 zu multiplizieren. Es wird eine Addition dauern. Noch schwerer mit 11 zu multiplizieren. Je mehr Einheiten, desto schwerer.

Nun, was ist mit 255 multipliziert? Bis zu 8 Einheiten, eine Alptraumaufgabe, richtig? Und hier sind die Figuren! Machen wir eine knifflige Finte mit unseren Ohren. Multiplizieren Sie unser B mit 256 (d. H. Verschieben Sie es um 8 Stellen) und subtrahieren Sie es vom Ergebnis. Es stellt sich heraus, dass das Multiplizieren mit 255 so einfach ist wie das Multiplizieren mit 10. Es ist genauso einfach, mit 254, mit 240 und mit 224 zu multiplizieren (wenn Sie möchten, überprüfen Sie!).

Insgesamt hilft die Subtraktion bei der Multiplikation. Erinnern Sie sich an diesen wertvollen Gedanken. In der Zwischenzeit bezeichnen wir die Schwierigkeit einer Zahl als die minimale Anzahl von Additions- (oder Subtraktions-) Operationen, die erforderlich sind, um mit ihr zu multiplizieren. Schichten werden nicht berücksichtigt. Denn im Rahmen des Problems (wir haben Schaltkreise, keine Programmierung!) Werden sie umsonst beschafft. Formulieren wir eine offensichtliche, aber nützliche Aussage:

Die Schwierigkeit einer Zahl ist kleiner oder gleich der Anzahl der Einheiten in der Binärnotation.
Wenn wir ehrlich ohne Subtraktionstricks multiplizieren, wie wir es in der Schule gelehrt haben, entspricht die Anzahl der Additionen der Anzahl der Einheiten in Binär- A. Und wenn wir anfangen zu tricksen und außerdem Glück haben, werden wir die Anzahl der Operationen reduzieren.

Eine interessante Konsequenz dieser Aussage:
Die Schwierigkeit einer n-Bit-Zahl ist immer kleiner als n .
Immerhin ist die größte Anzahl von Einheiten in einer n- stelligen Zahl n für eine Zahl wie 255. Andererseits ist klar, dass der Fokus wie bei der Multiplikation mit 255 für Zahlen beliebiger Bittiefe wiederholt werden kann. Dies eröffnet Perspektiven für die Optimierung von Universalmultiplikatoren.

Lassen Sie uns unsere Argumentation regelmäßiger betrachten. Lassen Sie uns zunächst bereits eine Art Multiplikationsschema von A haben. Wir nehmen als Einheit. Dann werden alle Terme so verschoben, addiert und subtrahiert, dass das Ergebnis das gleiche A ist. Insgesamt ist unser Multiplikationsschema mit A nichts anderes als eine Darstellung der Zahl A als die Summe von Zweierpotenzen, in der die Terme sowohl mit dem + -Zeichen als auch mit dem - -Zeichen sein können. Und Sie können die positiven und negativen Terme gruppieren und sagen, dass das Schema durch die Differenz einiger Zahlen A + und A- , gleich A, beschrieben wird. Das ist schlecht ... Die Glieder der Differenz können beliebig groß sein. Überlegen wir, ob es irgendwelche Überlegungen gibt, um sie einzuschränken.
Zunächst stellen wir fest, dass jede Zweierpotenz nur einmal in den Stromkreis eintreten kann. Wenn sie zweimal mit demselben Vorzeichen eintritt, kann dies durch eine Zweierpotenz durch eine Einheit größer ersetzt werden. Tritt sie zweimal mit unterschiedlichen Vorzeichen ein, werden diese voneinander subtrahiert. Insgesamt ist das Schema der üblichen binären Darstellung von A sehr ähnlich . Der einzige Unterschied ist, dass seine "Bits" (im Folgenden werden wir sie Trits nennen ) nicht zwei, sondern drei Werte annehmen können: 1, 0 und -1.

Total Wenn A eine n- Bit-Binärzahl ist, wird das Multiplikationsschema durch die Summe beschrieben:

$$

$$A = {t_m} 2 ^ m + {t_ {m-1}} 2 ^ {m-1} + .... + {t_1} 2 + {t_0}$$

wo $$${t_i}$- trits mit den Werten 1, 0 und -1 und m ist eine unbekannte Zahl.

Im Folgenden werden wir einen solchen Ausdruck ein ternäres Schema oder einfach ein Schema oder ein Multiplikationsschema für die Zahl A nennen.

Lassen Sie uns versuchen, m zu finden. Wie aus dem Beispiel mit der Multiplikation mit 255 hervorgeht, ist m keineswegs kleiner als n . Mal sehen, ob es gleich n + 1 sein kann .
A sei wie bisher eine positive n- stellige Zahl. Dann ist das Multiplikationsschema definiert als:

$$

$$A = {t_ {n + 1}} 2 ^ {n + 1} + {t_ {n}} 2 ^ {n} + {t_ {n-1}} 2 ^ {n-1} .... + {t_1} 2 + {t_0}$$

Daran erinnern $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$
Daher kann der höchste Trit in keiner Weise gleich -1 sein. Selbst wenn alle anderen 1 sind, ist die Summe immer noch -1. Und unter der Bedingung A ist positiv. Nun sei der oberste Trit 1. In diesem Fall sollte der nächste Trit -1 sein. Andernfalls ist die Menge zu groß. In der Tat, wenn der nächste Trit 0 ist, wird die Summe nicht weniger als sein $$$2 ^ {n + 1} - (2 ^ {n-1} + ... + 1) = 2 ^ {n + 1} - (2 ^ n - 1) = 2 ^ n + 1$
Während n- Bit A nicht mehr ist $$$2 ^ n - 1$. Aber wenn der oberste Trit 1 und der nächste -1 ist, dann ist die Summe der beiden obersten Glieder $$$2 ^ {n + 1} -2 ^ n = 2 ^ n$. Der oberste Trit ist also 0.

Damit ist eine wichtige Aussage bewiesen: m = n .

Mit anderen Worten, um ein Multiplikationsschema mit einem n- Bit A darzustellen, sind n + 1 Zweierpotenzen ausreichend - von 0 bis n (eine mehr als die binäre Darstellung), was uns sofort vor der Unendlichkeit bewahrt.

Nun können Sie versuchen, die Schwierigkeiten (siehe oben) einer bestimmten Zahl zu berechnen. Das Einfachste ist, das zu tun, was wir tun, indem wir die Binärzahlen der Reihe nach schreiben. Nur erstens haben wir hier keine Bits, sondern Trites (drei mögliche Werte), zweitens geben einige Kombinationen von Trites negative Zahlen und sie müssen verworfen werden, drittens können einige Kombinationen übereinstimmende Zahlen ergeben. Dies bedeutet, dass es für eine solche Nummer mehrere Schemata gibt.

Wir werden in Python schreiben. Nicht weil ich so ein Fan von ihm bin, sondern weil es sehr praktisch ist, mit ihm in Jupyter-Notizbüchern zu arbeiten. Zunächst schreiben wir die TriScheme-Klasse, die mit den oben eingeführten ternären Schemata arbeitet, die allSchemes-Funktion, die mit einer einfachen Aufzählung alle Schemata für Zahlen einer bestimmten Bitgröße berechnet, und die printSchemes-Funktion, die das Ergebnis ausgibt:


Wir berechnen die Schemata für alle 4-Bit-Zahlen:

0 0 1
1 1 5 [0000+, 000 + -, 00 + -, 0 + ---, + ----]
2 1 4 [000 + 0, 00 + -0, 0 + - 0, + --- 0]
3 2 7 [000 ++, 00 + - +, 00 + 0-, 0 + - +, 0 + -0-, + --- +, + - 0-]
4 1 3 [00 + 00, 0 + -00, + - 00]
5 2 8 [00 + 0 +, 00 ++ -, 0 + + -0 +, 0 + - + -, 0 + 0--, + - 0+, + - + -, + -0--]
6 2 5 [00 ++ 0, 0 + - + 0, 0 + 0-0, + - + 0, + -0-0]
7 2 7 [00 +++, 0 + - ++, 0 + 0- +, 0 + 00-, + - ++, + -0- +, + -00-]
8 1 2 [0 + 000, + -000]
9 2 7 [0 + 00 +, 0 + 0 + -, 0 ++ -, + -00 +, + -0 + -, + - + -, +0 ---]
10 2 5 [0 + 0 + 0, 0 ++ - 0, + -0 + 0, + - + - 0, + 0-0]
11 3 8 [0 + 0 ++, 0 ++ - +, 0 ++ 0-, + -0 ++, + - + - +, + - + 0-, +0 - +, + 0-0 -]
12 2 3 [0 ++ 00, + - + 00, + 0-00]
13 3 7 [0 ++ 0 +, 0 +++ -, + - + 0+, + - ++ -, + 0-0 +, +0 - + -, + 00--]
14 2 4 [0 +++ 0, + - ++ 0, + 0- + 0, + 00-0]
15 2 5 [0 ++++, + - +++, +0 - ++, + 00- +, + 000-]

Hier am Anfang der Zeile steht eine Zahl, gefolgt von ihrer Schwierigkeit (der minimalen Anzahl von Nicht-Null-Elementen in der Schaltung), dann der Anzahl von Schaltungen und schließlich einer Liste von Schaltungen.

In dem Schema bedeutet + 1, 0 - 0 und - - -1. Der älteste Stich links (wie bei der üblichen Zahlenschreibung)

Die Tabelle zeigt zum einen, dass nur die Nummern 13 und 11 die Schwierigkeit 3 ​​haben (das Maximum für 4-Bit-Nummern, wie oben gezeigt). Und zweitens ist die Anzahl der verschiedenen Schemata für jede Zahl ziemlich groß. Dies deutet zum einen darauf hin, dass die Multiplikation meistens viel einfacher ist, als wir es in der Schule gelernt haben. Und zweitens ist die Auswahl an Schaltungen für die Implementierung von Vorrichtungen zum Multiplizieren mit mehreren Konstanten unter Verwendung gemeinsamer Kristallressourcen ziemlich groß. Noch interessanter sind die Daten zu längeren Zahlen. Für 14-Bit-Nummern beträgt die maximale Schwierigkeit 8, und die maximale Anzahl von Schaltkreisen beträgt 937.

Alles wäre in Ordnung, aber der obige Algorithmus ist zu teuer. Ihre Komplexität wächst mit $$$3 ^ n$abhängig von der Länge der Zahlen n . Für 8 Stellen zählt sofort. Für 14 Minuten. Für 16 Stunden. Wenn Sie die Schaltkreise FÜR ALLE n- Bit-Nummern lesen müssen, können Sie leider nichts anderes tun, als sie in C umzuschreiben und einen leistungsfähigeren Computer zu verwenden. Der Algorithmus ist jedoch perfekt parallelisiert und kann durchaus auf der GPU oder im Cluster ausgeführt werden.

Zum Entwerfen bestimmter Verschraubungen sind normalerweise Listen von Schemata für bestimmte Nummern erforderlich. Und ALLES ist wünschenswert und nicht nur optimal. Die Wahl kann von den Umständen abhängen (z. B. ein Gerät zum Multiplizieren mit mehreren Konstanten). Und hier können Sie einen viel humaneren Algorithmus anbieten. Wir erinnern uns noch einmal an die bemerkenswerte Gleichheit: $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$.

Im Kontext der Aufgabe bedeutet dies Folgendes. Angenommen, es sind mehrere ältere Trit-Schemata bekannt. Alle kleinen Trits, die an Position k beginnen, sind unbekannt und werden zuvor als gleich Null betrachtet. Wenn Sie dann die unbekannten Trits auf irgendeine Weise ändern, ändern Sie den Wert der Schaltung um nicht mehr als plus / minus $$$2 ^ {k + 1} -1$. Außerdem nimmt mit dem Vorrücken zu den unteren Trits der Wert dieser Unsicherheit ab. Dies ermöglicht Ihnen die Suche nach Schemata anhand aufeinanderfolgender Näherungen, Trit für Trit.

Es sei eine positive Zahl A gegeben. Wir müssen alle Schemata dafür unter n- Bit-Zahlen finden. Der absolute Wert der Differenz zwischen A und dem Wert einer bestimmten Schaltung wird als Fehler der Schaltung bezeichnet. Zunächst nehmen wir ein n + 1- Bit-Schema, das n- Bit-Nummern beschreibt, die alle unbekannt sind und anfangs auf Null gesetzt werden. Und lassen Sie uns nacheinander Trits definieren, beginnend mit dem älteren. In der k- ten Position kann die Schaltung drei neue Muster erzeugen - mit Werten des k- ten Trits 1, 0 und -1. Wir lassen in der Liste der Schemata nur diejenigen von ihnen zur Fortsetzung, deren Fehler nicht übersteigt $$$2 ^ k-1$. Fahren Sie mit der resultierenden Liste der Schaltkreise mit dem Schritt an Position k-1 fort . Somit gibt es in der resultierenden Liste (an Position 0) ALLE möglichen Schemata, deren Wert A ist . Schreiben wir eine solche Funktion calcSchemes.


Und schließlich der versprochene Verkauf von Träumen.

In diesem Projekt mussten zwei Koeffizienten multipliziert werden: 16351 und 16318. Mit calcSchemes finden wir die Schemata für diese Koeffizienten:


Wir haben Glück! Beide Faktoren haben Schwierigkeiten 3. Wir wählen die optimalen Schemata für beide:
Für 16318 + 0000000-0000-0 und für 16351 - + 00000000-0000- . Wir hatten wieder Glück! Achten Sie auf die Schwänze der Schemata. Sie unterscheiden sich für 16318 und 16351 nur durch eine Linksverschiebung um eine Position. Das mit 16318 und 16351 multiplizierte Gerät enthält also nur einen zusätzlichen Multiplexer, der den verschobenen und nicht verschobenen Operanden am Eingang des Addierers schaltet.

Lassen Sie uns das Ergebnis sehen. Wir schreiben auf sehr drei Möglichkeiten für das Gerät der Multiplikation mit 16318 und 16351:

1. Option "Schule" (nur Ergänzungen und Schichten)
2. Optimale Schaltung
3. Optimales Schema mit gemeinsam genutzten Ressourcen

Für alle drei Optionen führen wir die Synthese durch und sehen, wie viele Kristallressourcen für jede von ihnen ausgegeben werden.


Alle drei Optionen funktionieren ordnungsgemäß und werden mit 0 an den Eingängen mit 16318 und mit 1 bei 16351 multipliziert. Gleichzeitig gibt yosys 488 Zellen für die Schulversion, 206 für die optimale Version und 202 für die Variante mit gemeinsam genutzten Ressourcen an. Es optimiert, obwohl es immer noch einen Unterschied in 4 Zellen gibt. Wie Sie sehen können, ist der Unterschied zur Schuloption sehr anständig.

Na endlich. Vielleicht scheint es unnötig, dass jemand einen solchen Garten umzäunt, nur um einfach zu erkennen, dass 16318 = 16384-64-2 und 16351 = 16384-32-1. Zunächst können die Zahlen jedoch komplizierter sein. Zweitens, wenn das Gerät mehrere Zahlen multiplizieren muss, ist es nicht selbstverständlich, dass optimale Schemata gewählt werden sollten. Ich hatte einfach Glück bei diesem Projekt. Im Allgemeinen kann ein Schaltungssuchprogramm viel helfen. Ich hoffe, der Artikel ist für jemanden nützlich. Und derjenige, der es liest, wird hoffentlich nicht in Panik geraten, wenn Sie multiplizieren müssen, aber es gibt keinen Multiplikator.