Gibt es eine alternative zur Verwendung von % (modulus) in C/C++?

https://stackoverflow.com/questions/48053

09-06-2019
|

Frage

Ich habe irgendwo gelesen, einmal, dass der modulo-operator ist ineffizient auf kleine embedded-Geräte wie die 8-bit-micro-Controller, die nicht mit integer-division-Anweisung.Vielleicht kann jemand dies bestätigen, aber ich dachte, der Unterschied ist 5-10 mal langsamer als bei einer integer-division operation.

Gibt es einen anderen Weg, dies zu tun, andere als halten Sie eine counter-variable und manuell überlaufen zu 0 an die mod-Punkt?

const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
    if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}

vs:

Die Art, wie ich momentan bin, es zu tun:

const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
    if(fizzcount >= FIZZ) 
    {
        print("Fizz\n");
        fizzcount = 0;
    }
}

Lösung

Ah, die Freuden der bitweisen Arithmetik.Ein Nebeneffekt der vielen division Routinen ist der modulus - so in einigen Fällen sollte die division tatsächlich schneller sein als der Elastizitätsmodul.Ich bin interessiert zu sehen, die Quelle, die Sie habe diese Informationen aus.Prozessoren mit Multiplikatoren haben interessante division Routinen mittels Multiplikator, aber man kann sich aus der division Ergebnis-Modul mit nur zwei weitere Schritte (multiplizieren und zu subtrahieren), so ist es immer noch vergleichbar.Wenn der Prozessor hat eine integrierte Abteilung der routine, die Sie wahrscheinlich sehen, es bietet auch den Rest.

Dennoch gibt es einen kleinen Zweig der Zahlentheorie gewidmet Modulare Arithmetik die Studie erfordert, wenn Sie wirklich wollen, zu verstehen, wie die Optimierung einer modulo-operation.Modulare arithmatic, zum Beispiel, ist sehr praktisch für die Erzeugung von Magische Quadrate.

Also, in diesem Sinne, hier ist eine sehr niedrigen Niveau suchen in der Mathematik der E-Modul für ein Beispiel von x, das sollte Ihnen zeigen, wie einfach es sein kann im Vergleich zu der division:

Vielleicht einer besseren Art und Weise zu denken über das problem in Bezug auf die Anzahl Basen-und modulo-Arithmetik.Für Beispiel, Ihre Ziel ist zu berechnen DOW mod 7, wo ist DOW die 16-bit-Darstellung der Tag der Woche.Sie können schreiben dies als:

 DOW = DOW_HI*256 + DOW_LO

 DOW%7 = (DOW_HI*256 + DOW_LO) % 7
       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

Ausgedrückt in diese Weise, Sie können separat berechnen Sie den modulo 7 Ergebnis für die high-und low-Byte.Multiplizieren Sie das Ergebnis für die hoch 4 und fügen Sie es in den unteren und dann schließlich compute Ergebnis modulo 7.

Berechnung der mod 7, die das Ergebnis einer 8-bit-Zahl kann durchgeführt werden in eine ähnlich wie Mode.Sie können schreiben, eine 8-bit-Zahl in eine oktale Zahl in etwa so:

  X = a*64 + b*8 + c

Wo a, b, und c sind 3-bit-zahlen.

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
      = (a%7 + b%7 + c%7) % 7
      = (a + b + c) % 7

da 64%7 = 8%7 = 1

Natürlich, a, b, und c sind

  c = X & 7
  b = (X>>3) & 7
  a = (X>>6) & 7  // (actually, a is only 2-bits).

Der größte mögliche Wert für a+b+c ist 7+7+3 = 17.Also, müssen Sie eine weitere oktal Schritt.Die komplette (ungetestet) C-version werden könnte geschrieben wie:

unsigned char Mod7Byte(unsigned char X)
{
    X = (X&7) + ((X>>3)&7) + (X>>6);
    X = (X&7) + (X>>3);

    return X==7 ? 0 : X;
}

Ich verbrachte ein paar Momente schreiben eines PIC-version.Die tatsächliche Umsetzung ist etwas anders als oben beschrieben,

Mod7Byte:
       movwf        temp1        ;
       andlw        7        ;W=c
       movwf        temp2        ;temp2=c
       rlncf   temp1,F        ;
       swapf        temp1,W ;W= a*8+b
       andlw   0x1F
       addwf        temp2,W ;W= a*8+b+c
       movwf        temp2   ;temp2 is now a 6-bit number
       andlw   0x38    ;get the high 3 bits == a'
       xorwf        temp2,F ;temp2 now has the 3 low bits == b'
       rlncf   WREG,F  ;shift the high bits right 4
       swapf   WREG,F  ;
       addwf        temp2,W ;W = a' + b'

 ; at this point, W is between 0 and 10


       addlw        -7
       bc      Mod7Byte_L2
Mod7Byte_L1:
       addlw        7
Mod7Byte_L2:
       return

Hier ist ein vielleicht kurz routine zum testen des Algorithmus

       clrf    x
       clrf    count

TestLoop:
       movf        x,W
       RCALL   Mod7Byte
       cpfseq count
        bra    fail

       incf        count,W
       xorlw   7
       skpz
        xorlw        7
       movwf   count

       incfsz        x,F
       bra        TestLoop
passed:

Schließlich, für die 16-bit-Ergebnis (was ich nicht getestet habe), Sie könnten schreiben:

uint16 Mod7Word(uint16 X)
{
 return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}

Scott

Andere Tipps

Wenn Sie sind Berechnung einer Reihe mod einige Potenz von zwei, die Sie verwenden können, die bitweise und-operator.Nur subtrahieren einer aus der zweiten Reihe.Zum Beispiel:

x % 8 == x & 7
x % 256 == x & 255

Ein paar Vorsichtsmaßnahmen:

Diese funktioniert nur, wenn die zweite Zahl ist eine Potenz von zwei.
Es ist nur gleichwertig, wenn die modulus ist immer positiv.Die C-und C++ - standards nicht geben Sie die Zeichen für den E-Modul, wenn die erste Zahl ist negativ (bis C++11, die tut garantieren, es wird negativ sein, was die meisten Compiler wurden bereits tun).Eine bit-Weise und entledigt sich das Vorzeichen-bit, wird also immer positiv (d.h.es ist eine wahre E-Modul, nicht ein Rest).Es klingt wie das, was Sie sowieso wollen, obwohl.
Ihr compiler wahrscheinlich tut dies bereits, wenn Sie es können, so dass in den meisten Fällen ist es nicht Wert, es manuell zu tun.

Es ist ein Aufwand den größten Teil der Zeit mit modulo, die keine Potenz von 2.Dies ist unabhängig von der Prozessor-als (AFAIK) auch Prozessoren mit modulo-Operatoren sind ein paar Zyklen langsamer teilen als Gegensatz zu Maske Operationen.

Für die meisten Fällen ist dies nicht eine Optimierung, die ist eine überlegung Wert, und sicherlich nicht Wert, Berechnung Ihrer eigenen shortcut-Bedienung (vor allem, wenn Sie derzeit mit teilen oder multiplizieren).

Aber eine Faustregel ist, zu wählen Sie array-Größen, etc.auf Potenzen von 2.

also, wenn die Berechnung von der Tag der Woche, auch %7 unabhängig wenn Sie einen kreisförmigen Puffer von rund 100 Einträge...warum nicht machen es 128.Sie können dann schreiben % 128 und die meisten (alle) Compiler machen dies & 0x7F

Wenn Sie wirklich brauchen hohe Leistung auf mehrere embedded-Plattformen, nicht ändern, wie Sie den code aus performance-Gründen bis Sie Profil!

Code, der geschrieben ungeschickt, um die Leistung optimieren, ist schwer zu Debuggen und schwer zu pflegen.Schreiben Sie einen Testfall, und Profil Sie es auf Ihr Ziel.Sobald Sie wissen, die eigentlichen Kosten von E-Modul, dann entscheiden, wenn die Alternative Lösung ist Wert-Kodierung.

@Matthäus Recht.Versuchen Sie dies:

int main() {
  int i;
  for(i = 0; i<=1024; i++) {
    if (!(i & 0xFF)) printf("& i = %d\n", i);
    if (!(i % 0x100)) printf("mod i = %d\n", i);
  }
}

x%y == (x-(x/y)*y)

Hoffe, das hilft.

In der embedded-Welt, die "modulus" Operationen, die Sie tun müssen, sind oft diejenigen, die brechen sich schön in bit-Operationen, die Sie tun können, mit '&' und '|' und manchmal '>>'.

Sie haben Zugang zu allen programmierbaren hardware für die embedded-Gerät?Wie Leistungsindikatoren und wie?Wenn ja, könnten Sie in der Lage sein zu schreiben Sie einen hardware-basierten mod Einheit, anstelle der Verwendung der simulierten %.(Ich habe das einmal in VHDL.Nicht sicher, ob ich immer noch der code, though.)

Wohlgemerkt, du hast gesagt, dass die division wurde 5-10 mal schneller.Haben Sie daran gedacht, eine division, Multiplikation und Subtraktion simuliert die mod?(Bearbeiten:Falsch verstanden, die original post.Ich dachte, dass es seltsam war, dass die division war schneller als mod, Sie sind die gleichen Betrieb.)

In Ihrem speziellen Fall, wenn Sie sind Prüfung für eine mod 6.6 = 2*3.So könnten Sie VIELLEICHT bekommen einige kleine Gewinne, wenn Sie zuerst prüfen, ob die least significant bit war eine 0.Etwas wie:

if((!(x & 1)) && (x % 3))
{
    print("Fizz\n");
}

Wenn Sie das aber tun, würde ich empfehlen, die bestätigt, dass Sie jegliche Gewinne, yay für Profiler.Und mache ein paar Kommentare.Hätte ich das Gefühl, schlecht für den nächsten Kerl, der hat um die code, sonst.

Sollten Sie wirklich überprüfen Sie die embedded-Gerät, das Sie brauchen.Alle assembly-Sprache, die ich gesehen habe (x86, 68000) implementieren Sie das Modul mit Hilfe einer division.

Eigentlich ist die Montage-Betriebs-Abteilung gibt das Ergebnis der division und die übrigen in zwei verschiedenen Registern.

Nicht dass das unbedingt besser ist, aber Sie könnte haben eine innere Schleife, die immer geht bis zu SPRUDELN, und eine äußere Schleife, die wiederholt es alle paar bestimmte Anzahl von Zeiten.Sie haben dann vielleicht bekam speziellen Fall die letzten Schritte, wenn MAXCOUNT ist nicht teilbar durch FIZZ.

Das heißt, ich würde vorschlagen, tun Sie etwas Forschung und performance-profiling auf Ihrer beabsichtigten Plattformen um eine klare Vorstellung von der Leistung Zwänge du bist unter.Es kann viel produktiver Orten zu verbringen Sie Ihre optimierungsarbeit.

@Jeff V:Ich sehe ein problem mit ihm!(Darüber, dass Ihr ursprünglicher code war auf der Suche nach einem mod 6 und jetzt sind Sie im wesentlichen der Suche nach einem mod 8).Halten Sie tun, ein zusätzliches +1!Hoffentlich ist Ihr compiler optimiert, dass Weg, aber warum nicht einfach testen, beginnen bei 2 und gehen Sie zu MAXCOUNT inclusive?Schließlich sind Sie wieder wahr, jedes mal, dass (x+1) ist NICHT durch 8 teilbar.Ist es das, was Sie wollen?(Ich nehme an, es ist, aber wollen einfach nur, um zu bestätigen.)

Modulo 6 Sie können ändern Sie den Python-code in C/C++:

def mod6(number):
    while number > 7:
        number = (number >> 3 << 1) + (number & 0x7)
    if number > 5:
        number -= 6
    return number

Die print-Anweisung wird nehmen um Größenordnungen mehr, als selbst die langsamste Durchführung der modulo-operator.Also im Grunde die Bemerkung: "auf einigen Systemen langsam" sollte "langsam auf " alle Systeme".

Auch die zwei code-snippets, sofern nicht die gleiche Sache zu tun.In die zweite Zeile

if(fizzcount >= FIZZ)

immer false, also "FIZZ " wird nie gedruckt.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow