Wie teilt man eine ganze Zahl am schnellsten durch 3?

Question

int x = n / 3;  // <-- make this faster

// for instance

int a = n * 3; // <-- normal integer multiplication

int b = (n << 1) + n; // <-- potentially faster multiplication

Answer 1

Dies ist am schnellsten, da der Compiler es optimiert, wenn es je nach Ausgangsprozessor kann.

int a;
int b;

a = some value;
b = a / 3;

Answer 2

Der Typ, der sagte, "überlasse es dem Compiler", hatte Recht, aber ich habe nicht den "Ruf", ihn zu modifizieren oder zu kommentieren. Ich habe GCC gebeten, den Int -Test (int a) {return a / 3; } Für einen IX86 und dann die Ausgabe zerlegt. Nur für akademisches Interesse, was es tut, ist grob Multiplizieren Sie mit 0x55555556 und nehmen Sie dann die Top 32 Bit des 64 -Bit -Ergebniss davon. Sie können sich dies mit z. B. demonstrieren:

$ ruby -e 'puts(60000 * 0x55555556 >> 32)'
20000
$ ruby -e 'puts(72 * 0x55555556 >> 32)'
24
$ 

Die Wikipedia -Seite auf Montgomery Division ist schwer zu lesen, aber zum Glück haben die Compiler es getan, damit Sie es nicht müssen.

Answer 3

Es geht schneller, wenn Sie die Wertebereiche kennen. Wenn Sie beispielsweise eine ganze Zahl mit Vorzeichen durch 3 dividieren und wissen, dass der Bereich des zu dividierenden Werts zwischen 0 und 768 liegt, können Sie ihn multiplizieren um einen Faktor und verschieben Sie ihn um eine Potenz von 2 nach links zu diesem Faktor dividiert durch 3.

z.B.

Bereich 0 -> 768

Sie könnten eine Verschiebung von 10 Bits verwenden, die Sie mit 1024 multiplizieren und durch 3 dividieren möchten, sodass Ihr Multiplikator 1024 / 3 = 341 sein sollte.

Sie können also jetzt (x * 341) >> 10 verwenden
(Stellen Sie sicher, dass es sich bei der Verschiebung um eine vorzeichenbehaftete Verschiebung handelt, wenn Sie vorzeichenbehaftete Ganzzahlen verwenden.) Stellen Sie außerdem sicher, dass es sich um eine tatsächliche Verschiebung und nicht um eine Bit-ROLL-Verschiebung handelt

Dadurch wird der Wert effektiv durch 3 geteilt und die Geschwindigkeit beträgt etwa das 1,6-fache einer natürlichen Division durch 3 auf einer Standard-x86-/x64-CPU.

Der einzige Grund, warum Sie diese Optimierung durchführen können, wenn der Compiler dies nicht kann, ist natürlich, dass der Compiler den maximalen Bereich von X nicht kennt und daher diese Bestimmung nicht treffen kann, Sie als Programmierer jedoch schon.

Manchmal kann es sogar vorteilhafter sein, den Wert auf einen größeren Wert zu verschieben und dann das Gleiche zu tun, d. h.Wenn Sie einen Ganzzahlwert mit vollem Bereich haben, können Sie daraus einen 64-Bit-Wert machen und dann die Multiplikation und Verschiebung durchführen, anstatt durch 3 zu dividieren.

Ich musste dies kürzlich tun, um die Bildverarbeitung zu beschleunigen. Ich musste den Durchschnitt von 3 Farbkanälen ermitteln, wobei jeder Farbkanal einen Bytebereich (0 - 255) hatte.rot grün und blau.

Zuerst habe ich einfach Folgendes verwendet:

avg = (r + g + b) / 3;

(R + g + b hat also ein Maximum von 768 und ein Minimum von 0, da jeder Kanal ein Byte von 0 bis 255 ist.)

Nach Millionen von Iterationen dauerte der gesamte Vorgang 36 Millisekunden.

Ich habe die Zeile geändert in:

avg = (r + g + b) * 341 >> 10;

Und das hat die Zeit auf 22 Millisekunden verkürzt. Es ist erstaunlich, was mit ein wenig Einfallsreichtum erreicht werden kann.

Diese Beschleunigung trat in C# auf, obwohl ich Optimierungen aktiviert hatte und das Programm nativ ohne Debugging-Informationen und nicht über die IDE ausführte.

Answer 4

Sehen Wie man sich um 3 teilt Für eine erweiterte Diskussion über effizientes Teilen durch 3, der sich auf die FPGA -arithmetischen Operationen konzentriert.

Auch relevant:

• Optimierung der Ganzzahl -Abteilungen mit mehrfacher Verschiebung in C#

Answer 5

Abhängig von Ihrer Plattform und abhängig von Ihrem C -Compiler eine native Lösung wie nur die Verwendung

y = x / 3

Kann schnell oder furchtbar langsam sein (auch wenn die Teilung vollständig in Hardware durchgeführt wird, wenn sie mit einem DIV -Anweisungen durchgeführt wird, ist diese Anweisung etwa 3- bis 4 -mal langsamer als eine Multiplikation für moderne CPUs). Sehr gute C -Compiler mit Optimierungsflags, die eingeschaltet sind, können diesen Vorgang optimieren. Wenn Sie jedoch sicher sein möchten, sind Sie es besser, sie selbst zu optimieren.

Für die Optimierung ist es wichtig, eine ganzzahlige Zahlen einer bekannten Größe zu haben. In C int hat es keine bekannte Größe (es kann je nach Plattform und Compiler variieren!), Sodass Sie C99-Ganzzahlen mit fester Größe besser verwenden. Der folgende Code geht davon ausHINWEIS: Selbst bei einer 32 -Bit -CPU -Architektur können die meisten C -Compiler mit 64 Bit -Gaunern einwandfrei handhaben):

static inline uint32_t divby3 (
    uint32_t divideMe
) {
    return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}

So verrückt das auch klingen mag, aber die obige Methode teilt sich in der Tat um 3. nur um 3, was dafür erforderlich ist, ist eine einzelne 64 -Bit -Multiplikation und eine Verschiebung (wie ich sagte, könnten Multiplikationen möglicherweise drei- bis viermal schneller sein als Abteilungen auf Ihrer CPU ). In einer 64 -Bit -Anwendung ist dieser Code viel schneller als in einer 32 -Bit -Anwendung (in einer 32 -Bit -Anwendung, die zwei 64 -Bit -Nummern multipliziert, 3 Multiplikationen und 3 Ergänzungen für 32 Bitwerte). Es ist jedoch möglicherweise immer noch schneller als a Division auf einer 32 -Bit -Maschine.

Wenn Ihr Compiler andererseits sehr gut ist und den Trick weiß, wie Sie die Integer -Division durch eine Konstante optimieren können (das neueste GCC, habe ich gerade nachgeprüft), generiert er den obigen Code ohnehin (GCC erstellt genau diesen Code für genau für diesen Code "/3", wenn Sie mindestens Optimierungsstufe 1 aktivieren). Für andere Compiler ... Sie können sich nicht verlassen oder erwarten, dass sie solche Tricks verwenden, obwohl diese Methode überall im Internet sehr gut dokumentiert und erwähnt wird.

Das Problem ist, dass es nur für konstante Zahlen funktioniert, nicht für variable. Sie müssen immer die magische Zahl (hier 0xaaaaaaab) und die richtigen Operationen nach der Multiplikation (Verschiebungen und/oder Ergänzungen in den meisten Fällen) kennen. Beide unterscheiden Berechnen Sie sie im Fliegen (das wäre langsamer als Hardware -Abteilung). Für einen Compiler ist es jedoch einfach, diese während der Kompilierungszeit zu berechnen (wo eine Sekunde mehr oder weniger Kompilierzeit kaum eine Rolle spielt).

Answer 6

Was wenn du Ja wirklich Willst du dich nicht multiplizieren oder dividieren? Hier ist eine Annäherung, die ich gerade erfunden habe. Es funktioniert, weil (x/3) = (x/4) + (x/12). Aber da (x/12) = (x/4)/3 wir den Vorgang nur wiederholen müssen, bis es gut genug ist.

#include <stdio.h>

void main()
{
    int n = 1000;
    int a,b;
    a = n >> 2;
    b = (a >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    printf("a=%d\n", a);
}

Das Ergebnis ist 330. Es könnte genauer unter Verwendung von B = ((b+2) >> 2) gemacht werden; Runden zu berücksichtigen.

Wenn du sind Mit einem Multiplizieren einer Multiplizierung einer geeigneten Annäherung für (1/3) mit einem Divisor von 2 auswählen. Zum Beispiel n * (1/3) ~ = n * 43 /128 = (n * 43) >> 7.

Diese Technik ist am nützlichsten in Indiana.

Answer 7

Ich weiß nicht, ob es schneller ist, aber wenn Sie einen bitgewiehenen Operator verwenden möchten, um eine binäre Abteilung auszuführen diese Seite:

• Setzen Sie den Quotienten auf 0
• Richten Sie links in Dividenden und Divisor links aus
• Wiederholen:
  • Wenn dieser Teil der Dividende über dem Divisor größer oder gleich dem Divisor ist:
    • Dann den Divisor von diesem Teil der Dividende subtrahieren und
    • Concatentate 1 zum rechten Ende des Quotienten
    • Sonst Concatentate 0 zum rechten Ende des Quotienten
  • Verschieben Sie den Divisor einen Ort rechts
• Bis die Dividende weniger als der Divisor ist:
• Quotient ist korrekt, Dividende ist Rest
• PAUSE

Answer 8

Für 64 -Bit -Zahlen:

uint64_t divBy3(uint64_t x)
{
    return x*12297829382473034411ULL;
}

Dies ist jedoch nicht die abgeschnittene Ganzzahl -Division, die Sie möglicherweise erwarten. Es funktioniert richtig, wenn die Zahl bereits um 3 teilbar ist, aber es gibt eine große Zahl zurück, wenn dies nicht der Fall ist.

Wenn Sie es beispielsweise für 11 ausführen, gibt es 6148914691236517209 zurück. Dies sieht aus wie ein Müll, aber es ist tatsächlich die richtige Antwort: Multiplizieren Sie es mit 3 und Sie erhalten die 11 zurück!

Wenn Sie nach der abgeschnittenen Abteilung suchen, verwenden Sie einfach den / Operator. Ich bezweifle sehr, dass Sie viel schneller werden können.

Theorie:

64 Bit unsigniertes Arithmetik ist ein Modulo 2^64 Arithmetik. Dies bedeutet für jede Ganzzahl, die mit dem 2^64 -Modul (im Wesentlichen alle ungeraden Zahlen) ein multiplikatives Inverse vorhanden ist, mit dem Sie sich anstelle von Teilung multiplizieren können. Diese magische Zahl kann durch Lösen der Lösung erhalten werden 3*x + 2^64*y = 1 Gleichung unter Verwendung des erweiterten euklidischen Algorithmus.

Answer 9

Wenn Sie diesen Artikel wirklich sehen möchten Ganzzahlabteilung, aber es hat nur akademisches Verdienst ... es wäre eine interessante Anwendung, die tatsächlich von dieser Art von Trick profitieren musste.

Answer 10

Für eine wirklich große Ganzzahl -Division (z. B. Zahlen größer als 64bit) können Sie Ihre Nummer als INT [] darstellen und Abteilung ziemlich schnell durchführen, indem Sie zwei Ziffern gleichzeitig nehmen und sie um 3 teilen. Der Rest wird Teil der nächsten zwei Ziffern sein und so weiter.

z.B. 11004 /3 sagst du

11/3 = 3, blieb = 2 (von 11-3*3)

20/3 = 6, Rest = 2 (von 20-6*3)

20/3 = 6, Rest = 2 (von 20-6*3)

24/3 = 8, Rest = 0

Daher das Ergebnis 3668

internal static List<int> Div3(int[] a)
{
  int remainder = 0;
  var res = new List<int>();
  for (int i = 0; i < a.Length; i++)
  {
    var val = remainder + a[i];
    var div = val/3;

    remainder = 10*(val%3);
    if (div > 9)
    {
      res.Add(div/10);
      res.Add(div%10);
    }
    else
      res.Add(div);
  }
  if (res[0] == 0) res.RemoveAt(0);
  return res;
}

Answer 11

Einfache Berechnung ... höchstens n Iterationen, bei denen n Ihre Anzahl von Bits ist:

uint8_t divideby3(uint8_t x)
{
  uint8_t answer =0;
  do
  {
    x>>=1;
    answer+=x;
    x=-x;
  }while(x);
  return answer;
}

Answer 12

Ein Nachschlagstabischansatz wäre auch in einigen Architekturen schneller.

uint8_t DivBy3LU(uint8_t u8Operand)
{
   uint8_t ai8Div3 = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ....];

   return ai8Div3[u8Operand];
}