Konvertieren von Gleichungen in Bit-Shifting-Operationen

Question

Gibt es eine Standardmethode zum Konvertieren einer (beliebigen) Gleichung in Bit-Shift-Operationen?

Damit ich irgend etwas bedeuten Umwandlung, die nicht a + oder - in Bit-Verschiebungen, so dass die End-Gleichung enthält nur die Operanden < <, >>, + und -. Dies liegt im Interesse, Formeln weniger prozessorintensiv zu machen.

Offensichtlich sind diese resultierenden Gleichungen nur Näherungen, was eine bessere Genauigkeit mit den mehr berücksichtigten Ordnungen (erster Ordnung, zweiter Ordnung e.t.c) ergibt.

Ich habe das Web nach irgendwelchen Informationen darüber durchforstet, aber kann keine finden, außer für Sachen auf bestimmten Formeln (sin, cos, inv e.t.c).

Ich stellte mir so etwas wie ein Polynom oder Taylors Expansionsprozedur vor und wandelte diese in Bit-Shift-Operationen um.

Answer 1

Nur weil Sie etwas auf einfachere Anweisungen reduzieren, bedeutet das nicht, dass sie schneller ausgeführt werden oder in irgendeiner Weise weniger intensiv sind. Während Sie möglicherweise viele Dinge auf eine reduzierte Teilmenge von Operationen reduzieren können, werden Sie wahrscheinlich viel mehr Operationen benötigen, um die gleiche Aufgabe zu erfüllen. Ein Prozessor kann nur so viele Operationen pro Sekunde ausführen, und Sie werden zuerst darauf stoßen.

Wenn Sie versuchen, etwas auf niedrigem Niveau zu optimieren, versuchen Sie, die weitaus komplexeren Opcodes zu verwenden, so dass Sie weniger davon benötigen. Als ein Beispiel können Sie eine Multiplikation durchführen, indem Sie viele ADD-Anweisungen ausführen. Aber für alles andere als die trivialsten Beispiele wird es wesentlich mehr ADDs benötigen als der einzelne MUL-Opcode, der benötigt wird, und es dauert viel länger, es auszuführen.

Zurück zu Ihrer eigentlichen Frage obwohl ... Völlig ignorieren Effizienz, können Sie alles berechnen, solange die Anweisung, die Sie haben, ist Turing Complete. Sie können tatsächlich alles mit a single instruction berechnen, wenn Sie vorsichtig sind, wie Sie diese Anweisung wählen. Ich glaube nicht, dass es eine allgemeine Möglichkeit gibt zu sagen "Konvertiere irgendeinen beliebigen Algorithmus in die Verwendung nur dieser Anweisungen", das ist normalerweise die Aufgabe eines Compiler-Schreibers.

Answer 2

Nicht im Allgemeinen.

Bei den meisten CPUs ist die Multiplikation nicht wesentlich langsamer als bei anderen arithmetischen Operationen, so dass es wenig Sinn macht, Multiplikation in Bitverschiebungsoperationen zu konvertieren, außer Multiplikation mit konstanten Zweierpotenzen.

Soweit es Division geht, gibt es einige bekannte Methoden zur Umwandlung Division durch eine Konstante zu Multiplikation mit der Umkehrung, und diese Methoden sind sehr produktiv. Eine Erläuterung dazu finden Sie unter http://www.flounder.com/multiplicative_inverse.htm. Division durch nicht konstante Werte kann jedoch nicht wirklich optimiert werden.

Das Erhöhen von 2 auf eine Leistung (oder Teilen einer Zahl durch eine Potenz von 2) wird natürlich leicht in Bit-Verschiebung umgewandelt. Andere Exponentiationen werden jedoch nicht leicht umgesetzt.

Die meisten transzendentalen Funktionen können auf einer bitweisen Ebene nicht sinnvoll dargestellt werden. Es hilft nicht, dass die meisten sowieso nicht für ganze Zahlen definiert sind.

Answer 3

Die Software-Multiplikation mit bitweisen Operationen wird die Hardware-Multiplikation auf modernen CPUs wahrscheinlich nicht übertreffen.

Normalerweise kann eine bitweise Manipulation zu besseren Ergebnissen führen, wenn 1) Schleifen vermieden werden können; und 2) Verzweigung.

A good online cookbook für Bit-Hacking. Ansonsten gibt es A Hacker's delight.