Effiziente (Zyklen wise) Algorithmus zum berechnen modulo 25?

Hier ist eine andere Lösung, die ich kam mit:

int mod25(int x){
  /* 25 * (all powers of 2 <= INT_MAX), descending */
  if (x >= 1677721600) x -= 1677721600;
  if (x >=  838860800) x -=  838860800;
  if (x >=  419430400) x -=  419430400;
  if (x >=  209715200) x -=  209715200;
  if (x >=  104857600) x -=  104857600;
  if (x >=   52428800) x -=   52428800;
  if (x >=   26214400) x -=   26214400;
  if (x >=   13107200) x -=   13107200;
  if (x >=    6553600) x -=    6553600;
  if (x >=    3276800) x -=    3276800;
  if (x >=    1638400) x -=    1638400;
  if (x >=     819200) x -=     819200;
  if (x >=     409600) x -=     409600;
  if (x >=     204800) x -=     204800;
  if (x >=     102400) x -=     102400;
  if (x >=      51200) x -=      51200;
  if (x >=      25600) x -=      25600;
  if (x >=      12800) x -=      12800;
  if (x >=       6400) x -=       6400;
  if (x >=       3200) x -=       3200;
  if (x >=       1600) x -=       1600;
  if (x >=        800) x -=        800;
  if (x >=        400) x -=        400;
  if (x >=        200) x -=        200;
  if (x >=        100) x -=        100;
  if (x >=         50) x -=         50;
  if (x >=         25) x -=         25;
  return x;
}

Diese nicht teilt oder multiplys, nur 27 Vergleiche und maximal 27 Subtraktionen.

Es ist ein wenig schwer, sich davon zu überzeugen, dass das funktioniert, aber es funktioniert (zumindest für nicht-negative Werte von x).

Dem obigen code ist wirklich eine ent-version:

int mod25(int x){
  int divisor;
  for(int divisor = 1677721600; divisor >= 25; divisor >>= 1) {
    if (x >= divisor) x -= divisor;
  }
  return x;
}

Durch abrollen es wir vermeiden, das loop-Vergleich und auch die Verschiebungen auf Kosten der größeren code. Man könnte sogar teilweise Rollen Sie ihn mit Duff ' s device, wenn Sie das Gefühl so geneigt, aber mit nur 27 Iterationen insgesamt, und wie ein winziges Stück code, pro iteration, würde ich geneigt sein, nur Rollen Sie den ganzen Weg.

Hier ist, wie es funktioniert: Jede nicht-negative ganze Zahl x ausgedrückt werden kann als (n * 25) + k, wobei n eine nicht-negative ganze Zahl ist und k eine ganze Zahl von 0 bis 24. k ist übrigens auch das Ergebnis, das wir wollen, so könnten wir berechnen x - (n * 25) würden wir bekommen unsere Antwort. Wir wollen in der Lage sein, dies zu tun, ohne zu wissen, n-up-front, aber.

Denke über n binäre. Wenn wir wiederum konnten aus jeder der 1-bits würden wir bekommen 0. Ein Weg dies zu tun ist zu beginnen, bei großen Potenzen von 2 und arbeiten uns nach unten, subtrahieren jede Potenz von 2 nur wenn der aktuelle Wert von n größer als oder gleich, dass die macht der 2.

Da beschäftigen wir uns mit (n * 25) wir brauchen eigentlich absteigenden Potenzen von 2 mal 25. Da k streng weniger als 25, und der kleinste divisor, die wir jemals in Betracht ziehen, ist 25, dies funktioniert sogar, wenn wir ' re Umgang mit (n * 25) + k.

Also jeder Vergleich + Subtraktion ist das unwiderrufliche löschen ein bit von n, und wir am Ende sind Links mit k, der Rest.

InformationsquelleAutor Laurence Gonsalves

Hier ist das beste, das ich kommen konnte mit:

int mod25(int x)
{
    while((x = (x & 31) + 7 * (x >> 5)) >= 25)
        x -= 25;

    return x;
}

Es kommt x % 25 mit x % 32 + 7 * (x/32). Der Wert überschwingen durch ein Vielfaches von 25, die es ermöglicht Rekursion.

Leistung scheint ausreichend zu sein: Ein Wert von x = 2147483647 (aka INT_MAX) muss 11 Iterationen.

InformationsquelleAutor Christoph

Oh mein <Gottheit der Wahl>. Ich kann nicht glauben, dass einige dieser Antworten.

Erste Sache, wiederholte Subtraktion, auch Pax-version, wird nie, nie, niemals optimal sein. Betrachten Sie die folgenden:

20 % 25

einfach und schnell durch wiederholte Subtraktion, aber:

65535 % 25

wird schrecklich langsam, 600+ Iterationen. Das ist ein Durchschnitt von 300 Iterationen für 16-bit-zahlen. Für 32-bit-Nummer, nun, nur, gar nicht dorthin gehen.

Der Schnellste Weg, dies zu tun ist, um lange Teilung. Siehe Niki ' s Antwort.

Aber, dies ist, was der compiler erzeugen, jedenfalls, mindestens, würde man hoffen, dass es das ist, was der compiler generiert wird. Es ist immer am besten, wenn Sie mit einem compiler für eine Nische Prozessor.

Der beste Weg, um diese Fahrt ist nicht das Modul in den ersten Platz. Warum brauchen Sie, um das Modul und kann man wieder den Faktor der code /Algorithmus zu vermeiden, der E-Modul, oder zumindest, machen das E-Modul trivial.

InformationsquelleAutor Skizz

Auf viele Prozessoren, integer-Multiplikation ist schneller als division. In diesem blog-post zeigt, wie zu ersetzen, die eine Konstante Ganzzahl-division mit einer Konstanten integer-Multiplikation. Durch eine Neuanordnung der Mathematik ein bisschen können Sie den Rest statt des Quotienten. Beachten Sie jedoch, dass, wenn Sie mit einem mäßig anspruchsvollen compiler, dann ist dies bereits für Sie getan. Sie schreiben einfach x % 25 und der compiler funktioniert der rest. Sollten Sie den erzeugten Assembler-code für deinen code, überprüfen, ob der compiler hat das nicht getan bereits, bevor Sie diese Optimierung in C. Auch sollte man Messen (Profil) die Leistung vor und nach, um sicherzustellen, dass Sie wirklich sind, die Dinge zu beschleunigen.

Looping wird weit langsamer als die division mit dem native-Anleitung für die relativ großen Operanden.

Edit: siehe auch dieses Papier.

InformationsquelleAutor Doug

bitte engagieren Sie einige der gesunde Menschenverstand.

Wenn Sie schreiben könnten, C-code, berechnet x % 25-schneller als der compiler, dann würde der compiler verwenden, die schnellere Methode.

Den original-poster dieses fantastische Annahme, dass der compiler die Verwendung einer division. Keine compiler, die ich verwendet habe in den letzten zehn Jahren tun würde. Es ist die Multiplikation durch eine Konstante in der Nähe (2^32 /25) plus einige bit-twiddling, dass Sie nicht in der Lage sein zur Verbesserung von hand.

Gibt es eine Möglichkeit, dass Sie Sie produzieren können schnelleren code als der compiler, um herauszufinden, ob x % 25 == 0, da Sie nicht wirklich benötigen-code berechnet x % 25 richtig, nur code, berechnet x % 25 richtig, wenn es 0 ist, und nicht produzieren eine 0, wenn x % 25 != 0. Einsparungen werden wahrscheinlich im sub-Nanosekunden.

"Wie berechne ich x % c optimal für verschiedene Konstanten c" ist ein nettes puzzle. Compiler-Autoren wie schön Rätseln. Und Sie sind besser auf die Lösung von schönen Rätseln, wie diese, als Sie sind. Vor allem, da Sie nur brauchen eine Lösung, die funktioniert für eine Maschine, wo Sie haben, um zu produzieren, eine Allgemeine Lösung.

InformationsquelleAutor gnasher729

Wenn Sie wissen, dass b wird eine Potenz von 2 ist, könnten Sie bitweise AND anstelle der modulo-operator. Jedoch, die wikipedia-Seite für modulo scheint zu zeigen, dass C-compiler würde dies feststellen und optimieren aus der modulo jedenfalls.

InformationsquelleAutor wkf

int mod25(int x) {
  static int divisors[] = {2147483625, 244140625, 9765625, 390625, 15625, 625, 25};
  int i;
  for (i = 0; i < sizeof(divisors)/sizeof(int); i++) {
    int divisor = divisors[i];
    while (x >= divisor) {
      x -= divisor;
    }
  }
  return x;
}

Wie es funktioniert: Wir wollen, zu verringern x durch große Vielfache von 25 zu reduzieren, den Wert so schnell wie möglich. Wenn der divisor ist zu groß, wechseln wir auf ein kleineres Vielfaches von 25. Wenn der divisor ist schon runter auf 25, dann sind wir fertig.

Könnten Sie versuchen, das Experimentieren mit verschiedenen Teiler. Sie wollen einfach nur, um sicherzustellen, dass:

• Sie sind absteigend
• Sie sind alle Vielfache von 25
• der Letzte Wert ist 25

Im obigen code verwendete ich die größte signed-32-bit-Vielfaches von 25 plus die Befugnisse von 25, das scheint vernünftig, aber ich muss zugeben, dass ich nicht sicher bin, dass es optimal.

(BTW: wenn dein compiler nicht tun constant folding-was sehr überraschend-dann möchten Sie vielleicht zu ersetzen, die Obere Grenze i mit einem hart codierte Konstante.)

InformationsquelleAutor Laurence Gonsalves

Gibt es einen Grund, warum Sie nicht verwenden C die eingebaute modulo-operator?

int a = x % 25;

Folgenden edit;

Wenn Ihr rpocessor nicht eingebaute modulo-Unterstützung, dann würde ich immer noch den % - operator aus dem einfachen Grund, dass dein compiler wissen, dass der Prozessor in Frage, der nicht über eine native % - Funktion, und wird wahrscheinlich produzieren asm-code optimal zu emulieren.

Sagen wir es so - ich wäre fasziniert, wenn Sie mit oben kommen kann eine algemeine Algorithmus, der übertrifft whatevr der compiler erzeugt aus den eingebauten operator, notwithsatanding bestimmten Fällen (z.B. nur die 2 niedrigsten Ziffern modulo 100 etc)

InformationsquelleAutor PaulJWilliams

Ich finde es ziemlich merkwürdig, dass der Betrieb x % 25 dauert eine lange Zeit (wenn Sie den built-in % Betreiber ist). Die meisten modernen Prozessoren sollte diese in einer einzigen Instruktion. Ich würde nach anderen Gründen, dass dieser code so lange dauert.

BEARBEITEN:
Hier ist ein Algorithmus, der könnte zumindest geben einige Ideen:

256 = 6 (mod 25)

Dies bedeutet, dass, wenn wir eine Zahl schreiben x als bytes x3 x2 x1 x0 haben wir, dass x = 6^3*x3 + 6^2*x2 + 6*x1 + x0 (mod 25)

Dieser gibt einen Algorithmus für die Reduzierung der Größe der x:

int x0 = x & 0xFF, x1 = (x>>8) & 0xFF, x2 = (x>>16) & 0xFF, x3 = (x>>24) & 0xFF;

int y = x4;
y = (y << 2) + (y << 1) + x3;
y = (y << 2) + (y << 1) + x2;
y = (y << 2) + (y << 1) + x1;
y = (y << 2) + (y << 1) + x0;

(hier (y << 2) + (y << 1) = 4*y + 2*y = 6*y)

Nach dieser y haben den gleichen Rest wie x mod 25.
Durchlaufen diese 1, 2 oder 3 mal machen y 17, 11, oder 9-bit-Zahl, beziehungsweise. Eine dieser Größen ist zwar klein genug, um eine lookup-Tabelle.

Ich bezweifle ERNSTHAFT, dass dies schneller sein als die eingebaute % Betreiber, obwohl.

InformationsquelleAutor CAdaker

Heres eine Idee

static int table0[256];
static int table1[256];
static int table2[256];
static int table3[256];

//ran just once to initialize the tables
void initialMod25Tables() {
    for (int i = 0; i < 256; ++i) {
        table0[i] = i % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table1[i] = (i << 8) % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table2[i] = (i << 16) % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table3[i] = (i << 24) % 25;
    }
}

int mod25(int x) {
    int y = table0[x & 0xFF];
    x >>= 8;
    y += table1[x & 0xFF];
    x >>= 8;
    y += table2[x & 0xFF];
    x >>= 8;
    y += table3[x & 0xFF];
    y = table0[y];
    return y;
}

InformationsquelleAutor clinux