Das Erhalten des Betrags einer Zahl kann leicht ohne den Modulusoperator oder die Divisionen durchgeführt werden, wenn Ihr Operand eine Potenz von 2 ist. In diesem Fall gilt die folgende Formel: x % y = (x & (y − 1)) . Dies ist oft in vielen Architekturen performant. Kann das auch für mod 31 gemacht werden?
Hier sind zwei Möglichkeiten, dieses Problem anzugehen. Die erste, die eine gewöhnliche Bit-Twiddling-Technik verwendet, kann, wenn sie sorgfältig optimiert wird, die Hardware-Aufteilung übertreffen. Der andere ersetzt die Teilung durch Multiplikation, ähnlich der Optimierung von gcc , und ist mit Abstand die schnellste. Die Quintessenz ist, dass es nicht viel Sinn macht, den % operator zu vermeiden, wenn das zweite Argument konstant ist , weil gcc es abgedeckt hat. (Und wahrscheinlich auch andere Compiler.)
Die folgende Funktion basiert auf der Tatsache, dass x die gleiche ist (mod 31) wie die Summe der base-32 Ziffern von x . Das stimmt, denn 32 ist 1 mod 31 und folglich ist jede Potenz von 32 1 mod 31 . Also trägt jede "Ziffern" -Position in einer Basis-32-Nummer die Ziffer * 1 zu der Summe von Mod 31 bei. Und es ist leicht, die Basis-32-Darstellung zu erhalten: Wir nehmen nur die Bits auf einmal.
(Wie alle anderen Funktionen in dieser Antwort funktioniert es nur für nicht-negative x ).
Bei einer bestimmten Integer-Größe könnten Sie die Schleife ausrollen und möglicherweise die Division übertreffen. (Und siehe @ chuxs Antwort , um die Schleife in O(log bits) -Operationen anstelle von O(bits) zu konvertieren. Es ist schwieriger um gcc zu schlagen, was eine Division vermeidet, wenn der Dividend zur Kompilierzeit eine Konstante ist.
In einem sehr schnellen Benchmark mit unsignierten 32-Bit-Integern dauerte die naive entrollte Schleife 19 Sekunden und eine auf @ chux's Antwort basierende Version dauerte nur 13 Sekunden, aber gcc's x%31 benötigte 9,7 Sekunden. Das Erzwingen einer Hardwareteilung (indem die Division nicht konstant gemacht wird) dauerte 23,4 Sekunden, und der Code, wie oben gezeigt, benötigte 25,6 Sekunden. Diese Zahlen sollten mit mehreren Körnern Salz genommen werden. Die Zeiten sind für die Berechnung von i%31 für alle möglichen Werte von i , auf meinem Laptop mit -O3 -march=native .
gcc vermeidet die 32-Bit-Division durch eine Konstante, indem es durch eine im Wesentlichen 64-Bit-Multiplikation durch die Umkehrung der Konstanten, gefolgt von einer Rechtsverschiebung, ersetzt wird. (Der eigentliche Algorithmus arbeitet etwas mehr, um Überläufe zu vermeiden.) Die Prozedur wurde vor mehr als 20 Jahren in gcc v2.6 implementiert, und das Papier, das den Algorithmus beschreibt, ist auf der Website von gmp . (GMP verwendet auch diesen Trick.)
Hier ist eine vereinfachte Version: Angenommen, wir wollen n // 31 für eine vorzeichenlose 32-Bit-Ganzzahl n berechnen (mit dem Python // , um eine abgeschnittene Ganzzahl-Division anzuzeigen). Wir verwenden die "magische Konstante" m = 232 // 31 , die 138547332 ist. Jetzt ist klar, dass für jedes n :
m * n <= 232 * n/31 < m * n + n
⇒ m * n // 232 <= n//31 <= (m * n + n) // 232
(Hier nutzen wir die Tatsache, dass wenn a < b dann floor(a) <= floor(b) .)
Außerdem, da n < 232 , m * n // 232 und (m * n + n) // 232 entweder die gleiche ganze Zahl oder zwei aufeinanderfolgende ganze Zahlen sind. Folglich ist einer (oder beide) dieser beiden der tatsächliche Wert von n//31 .
Nun wollen wir wirklich n%31 berechnen. Also müssen wir den (vermuteten) Quotienten mit 31 multiplizieren und den von n subtrahieren. Wenn wir den kleineren der beiden möglichen Quotienten verwenden, kann sich herausstellen, dass der berechnete Modulo-Wert zu groß ist, aber er kann nur um 31 zu groß sein.
Oder, um es in Code zu schreiben:
%Vor% Der tatsächliche Algorithmus, der von gcc verwendet wird, vermeidet den Test am Ende, indem er eine etwas genauere Berechnung verwendet, die auf der Multiplikation mit 237//31 + 1 basiert. Dies erzeugt immer den richtigen Quotienten, jedoch auf Kosten einiger zusätzlicher Verschiebungen und Additionen, um einen Integer-Überlauf zu vermeiden. Wie sich herausstellt, ist die obige Version etwas schneller - im selben Benchmark wie oben, dauerte es nur 6,3 Sekunden.
Weitere benchmarked Funktionen, für die Vollständigkeit:
Naive entrollte Schleife
%Vor%@ chux's Verbesserung, leicht optimiert
%Vor%[Edit2] unten für Leistungshinweise
Ein Versuch mit nur 1 if Bedingung.
Dieser Ansatz ist O (log2 (sizeof unsigned)). Laufzeit würde um 1 Satz von ands / shifts / add eher als zweimal die Zeit mit einer Schleife Ansatz sollte Code uint64_t zu erhöhen.
[Bearbeiten]
Die erste Additionsmethode summiert die einzelnen 7 Gruppen von fünf Bits parallel. Nachfolgende Additionen bringen die Gruppe 7 in 4, dann 2, dann 1. Diese letzte 7-Bit-Summe fährt dann fort, ihre obere Hälfte (2 Bits) zu ihrer unteren Hälfte (5 Bits) hinzuzufügen. Code verwendet dann einen Test, um den letzten "Mod" durchzuführen.
Diese Methode skaliert für breitere unsigned bis mindestens uint165_t log2 (31 + 1) * (31 + 2). Übergeben Sie das, ein wenig mehr Code ist erforderlich.
Siehe @rici für einige gute Optimierungen. Wir empfehlen weiterhin, uint32_t vs. unsigned und 31UL in Schichten wie 31U << 15 zu verwenden, da unsigned 31U möglicherweise nur 16 Bit lang ist. (16 Bit int beliebt in Embedded-Welt in 2014).
[Bearbeiten2]
Neben der Möglichkeit, dass der Compiler seinen Optimierer verwendet, beschleunigen zwei zusätzliche Techniken die Leistung. Dies sind kleinere Salon Tricks, die eine bescheidene Verbesserung ergaben. Denken Sie daran YMMV und dies ist für eine 32-Bit unsigned .
Die Suche nach einer Tabelle für die letzte modulo wurde um 10-20% verbessert. Die Verwendung von unsigned t table anstatt unsigned char t half auch ein bisschen. Es stellte sich heraus, dass die Tabellenlänge, wie zuerst erwartet, 2 * 31 sein musste, nur 31 + 5 benötigte.
Die Verwendung einer lokalen Variablen anstelle des Aufrufs des Funktionsparameters hat überraschend geholfen. Wahrscheinlich eine Schwäche in meinem GCC-Compiler.
Gefunden nicht verzweigende Lösungen, nicht gezeigt, um x >= 31 ? x-31 : x zu ersetzen. aber ihre Codierungskomplexität war größer und die Leistung war langsamer.
Alles in allem eine lustige Übung.
%Vor% Wenn Sie das Modul der Division durch einen Nenner d so erhalten möchten, dass d = (1 << e) - 1 wo e ein Exponent ist, können Sie die Tatsache verwenden, dass die binäre Erweiterung von 1/d ein sich wiederholender Bruch mit Bits ist setze alle e Ziffern. Zum Beispiel für e = 5 , d = 31 und 1/d = 0.0000100001... .
Ähnlich wie ricis Antwort berechnet dieser Algorithmus effektiv die Summe der Basis- (1 << e) Ziffern von a :
Sie können diese Schleife auflösen, weil der Nenner und die Anzahl der Bits im Zähler beide konstant sind, aber es ist wahrscheinlich besser, den Compiler das tun zu lassen. Und natürlich können Sie 5 in einen Eingabeparameter und 31 in eine daraus berechnete Variable ändern.
Sie könnten sukzessive Addition / Subtraktion verwenden. Es gibt keinen anderen Trick, da 31 eine Primzahl ist, um zu sehen, wie der Modul einer Zahl N mod 31 ist, müssen Sie teilen und den Rest finden.
Tags und Links c modulus bit-manipulation bitwise-operators