Einfache Frage, ist es möglich zu vereinfachen (oder ersetzen Division oder Modulo durch weniger teure Operation)
%Vor%wobei Variablen Ganzzahlen und Operatoren C-Stil-Division und Modulo-Operatoren sind.
Lassen Sie mich die Frage etwas anders formulieren, außer für den Fall, dass Variablen basis2 sind, unter welchen Bedingungen (zB kann eine Variable konstant sein) kann der Ausdruck vereinfacht (oder partiell mit base2-Operationen umformuliert werden), um die Division oder modulo zu entfernen?
Das ist für mich Weg Nummertheorie zu lernen, besonders Base2 Tricks, anstatt Übung in der Leistungsoptimierung
Danke
Für die Division mit kleinen Konstanten Nenner, können Sie so etwas verwenden.
%Vor%Die Antwort ist abhängig von den Eingaben möglicherweise nicht präzise.
Für die Division mit kleinem ungeraden konstanten Nenner können Sie das multiplikative Inverse
Die % 2^32 ist natürlich frei für 32-Bit-Integer. Um dies auf gerade Zahlen anzuwenden, faktorisieren Sie die Zweien und wenden Sie sie später an.
Hackers Delight hat ein Kapitel über die Division durch ganze Zahlen.
Das einfache Modul und die Division für Potenzen von zwei.
%Vor%Offensichtliche Optimierungen:
k % m . 0 . (k >> 2) % n ; (k / m) & (n - 1) ; Die Überprüfung auf # 1 und # 2 ist trivial.
Die Überprüfung von Zweierpotenzen erfolgt mit:
%Vor%Hinzufügen zu Peter Alexanders Antwort
0) Natürlich m! = 0 & amp; & amp; n! = 0 sind Voraussetzungen ...
1) k & lt; m: Die Antwort ist immer 0
2) k == m: Die Antwort ist immer 1 (außer n ist auch 1, siehe 5.)
3) k / m & lt; n: Die Antwort lautet k / m
4) k & lt; (m * n): Die Antwort ist immer k / m. Diese spezielle Bedingung ist für die Optimierung nicht sehr förderlich, da m * n würde nicht wiederverwendet werden und es sollte nicht viel schneller als modulo sein es sei denn, m und / oder n sind Potenzen von 2, in diesem Fall würden Sie immer noch besser verwenden 7. und / oder 8.
Zur Referenz hinzufügen Peter Alexanders:
5) m == 1: Die Antwort ist nur k% n.
6) n == 1: Die Antwort ist immer 0.
7) m ist eine Potenz von 2: z.B. Wenn m 4 ist, können Sie (k & gt; & gt; 2)% n;
verwenden8) n ist eine Potenz von 2: Ausdruck wird (k / m) & amp; (n - 1);
Ich nehme an, dass es abhängt. Eine rechte arithmetische Verschiebung würde eine Division durch 2 ergeben, und mit etwas zusätzlicher Arithmetik könnte man dies durch irgendeine Zahl in eine Division bringen. Ähnlich würde ich denken, dass Sie das gleiche mit dem Modulo-Operator tun könnten. In der Realität hätte ich, wenn es Ihrem Prozessor nicht an Hardware fehlt, nicht gedacht, dass Sie etwas gewinnen würden.
Bearbeiten Wenn man genau darüber nachdenkt, ist hier genaueres Nachdenken notwendig, denn bei einer negativen Zahl würde eine unterzeichnete Schicht nicht als eine Teilung durch 2 funktionieren.
Wenn ich mich recht erinnere, ist das Verhalten eines Rechens mit rechnerischer Verschiebung im C-Standard für negative Zahlen (es spricht von Zweierpotenzen) und somit vom Compiler abhängig.
Wenn wir nur über die Logik der Zahlentheorie nachdenken, dann ist das eine andere Sache. Lass mich darüber nachdenken.
Tags und Links algorithm language-agnostic math