Ich möchte den Lesern von einem Programmiertrick erzählen, den ich in einer Art Übersetzungsbuch kennengelernt habe, das eine Auswahl solcher Tricks in jenen fernen Zeiten enthält, als es noch nicht nur das Byte, sondern auch den Stapel erfunden hat und der große Dijkstra den Operator noch nicht verflucht hat GOTO (sic, in Großbuchstaben).
Ich mochte den Trick so sehr wegen seiner Einfachheit und Anmut, dass ich bereits in diesem Jahrtausend glücklich war, den Schülern in Form der folgenden Aufgabe davon zu erzählen.
Stellen Sie sich vor, Sie haben bei Ihrer Rückkehr vom Mond im Jahr 2030 plötzlich festgestellt, dass Ihr Bordcomputer die Ganzzahlmultiplikationsoperationen nicht korrekt ausführt, und dies wird sicherlich zu einem Unfall während der Landung führen.
In dieser Geschichte gibt es nichts besonders Fantastisches. Erinnern wir uns zum Beispiel daran, welche Probleme einst mit
Pentium-Prozessoren aufgetreten sind und als Sie zum Mond geschickt wurden, hatten Sie noch keine vollständige Importsubstitution erreicht. Im Allgemeinen muss überprüft werden, ob die Prozessoren speziell gebohrt wurden.
Aber auf den Punkt. Sie müssen die Multiplikation dringend programmgesteuert implementieren, damit sie schnell in Echtzeit funktioniert und in eine verfügbare Ressource passt.
Aus dem Schulkurs der Arithmetik erinnern wir uns, dass mehrwertige Zahlen mit einer Spalte multipliziert werden können und das Ergebnis der Multiplikation einzelner Zahlen aus der Multiplikationstabelle entnommen werden kann.
Aber nur wenn die Zahlen kurz gewählt werden (z. B. 0 und 1), ist die Multiplikationstabelle kurz und die Spalten lang, und ihre Berechnung nimmt viel Zeit in Anspruch.
Wenn wir im Gegenteil lange Zahlen nehmen (zum Beispiel von 0 bis 65535), dann für 16-Bit-Arithmetik
Das Ergebnis wird direkt aus der Tabelle entnommen und die Spalten fehlen. Die Größe der klassischen pythagoreischen Tabelle beträgt jedoch ungefähr 17 GB (4 * 65536 * 65536). Wenn wir die Symmetrie in Bezug auf die Diagonale berücksichtigen, beträgt die Hälfte ungefähr 8,5 GB.
Es kann ein bisschen zu viel sein.
Ziehen Sie die Algebra fest und erinnern Sie sich daran.
(1)(2)Subtrahiere
(2) von
(1)und weiter
Wenn wir also eine Tabelle mit Quadraten im sqr-Array haben, erhalten wir
a * b = (sqr [a + b] - sqr [a - b]) / 4
(*)Die Größe der 8 * -Tabelle (65535 + 65535) beträgt ca. 8,4 MB, was möglicherweise bereits akzeptabel ist.
Die Größe des Tabellenelements von 8 Bytes ist darauf zurückzuführen, dass für das Maximum a und b das Quadrat ihrer Summe von 4 Bytes nicht passt - 2 Bits reichen nicht aus.
Als nächstes werde ich einige Verbesserungen beschreiben, die nicht im Buch enthalten waren. Ich habe es mir selbst ausgedacht, als ich diese Notiz bereits schrieb.
Es ist zu beachten, dass die zwei niedrigstwertigen Bits eines geraden Quadrats immer 00 sind und das ungerade Quadrat immer 01 ist. Andererseits haben für jedes Zahlenpaar ihre Summe und Differenz die gleiche Parität.
Daher kann in unserer Formel
(*) der Subtraktionsprozess in Klammern keine Bindestriche haben.
mit den zwei niedrigstwertigen Bits verbunden. Daher der Inhalt der Elemente der Quadrattabelle
Sie können zwei Bits nach rechts vorrücken und so die Hälfte des Speichers sparen.
Endlich haben wir
a * b = sqr4 [a + b] - sqr4 [a - b]
(**)Dabei ist sqr4 die modifizierte Tabelle der Quadrate.
In unserem Beispiel beträgt die Größe ca. 4,2 MB.
Zur Veranschaulichung dieses Ansatzes ist unten der Text des Lua-Programms enthalten.
function create_multiplier(N)
Für moderne Prozessoren erscheint es sinnvoll, eine Zifferngröße zu haben, die ein Vielfaches der Bytegröße beträgt, um leicht darauf zugreifen zu können. Bei 1-Byte-Ziffern beträgt die Größe der Tabelle nur 1022 Byte, sodass dieser Trick möglicherweise in 8-Bit-Prozessoren ohne Hardware-Multiplikation verwendet werden kann.
Ich werde allen Lesern dieser Notiz für Korrekturen und Kommentare dankbar sein.