Frage

Ich schreibe Code für einen Mikroprozessor mit schnellen Integer-Arithmetik und nicht so schnell float Arithmetik. Ich brauche eine ganze Zahl und eine Zahl von 1 bis 9 und konvertiert Ergebnis zurück an integer zu unterteilen.

I machte eine Schwimmeranordnung mit Mitgliedern wie 0, 1, 0,5, 0.3333 usw. Aber ich denke, es ist MAGIC Konstanten (wie 0x55555556) für eine Zahl mit Ausnahme von (1/3).

Was sind diese Zahlen?

War es hilfreich?

Lösung

Wenn der Teilungsbefehl auf dem Mikrocontroller schnell genug ist, verwenden Sie das. Wenn Sie den Bruchteil des Ergebnisses benötigen, können Sie in der Lage sein, den Rest zu verwenden; auf den meisten Architekturen, stellt der Teilungsbefehl die Quotienten in einem Register und der Rest in einem anderen.

Wenn Ihre Abteilung Anweisung nicht schnell genug ist, aber der Multiplikationsbefehl ist, können Sie die folgende Technik verwenden (und es klingt, als ob dies die Technik Sie nach). Auf den meisten Architekturen, eine 32-Bit-Zahl durch eine andere 32-Bit-Zahl ergibt ein 64-Bit-Ergebnis multipliziert wird; die signifikantere Hälfte wird in einem Register und die weniger signifikante Hälfte in der anderen gespeichert wird. Sie können dieses ausnutzen, der durch die Teilung durch eine Anzahl n Realisierung ist das gleiche wie die Multiplikation von (2 ^ 32) / n, dann die höherwertigen 32 Bits des Ergebnisses nehmen. Mit anderen Worten, wenn Sie mit dem 3 teilen möchten, können Sie stattdessen durch 0x100000000 / 3 = 0x55555555 multiplizieren, dann nehmen Sie die höherwertigen 32 Bits des Ergebnisses.

Was Sie tun, hier ist wirklich eine Form von Festkommaarithmetik. Werfen Sie einen Blick auf die Wikipedia-Artikel für weitere Informationen.

Andere Tipps

Eine Division einer ganzen Zahl durch eine ganzzahlige Konstante kann mit einer Kombination aus einer Verschiebung und einer Multiplikation ersetzt werden. Siehe dieser Optimierung Leitfaden . Cource ist dies sinnvoll, wenn es actully schneller auf dem Chip von Interesse ist.

Ich gehe davon aus, basierend auf dem Mikro-Controller-Tag, Sie nicht über eine schnelle Integer divide haben. Meine Antwort ist auch für Werte ohne Vorzeichen -. Es wird für signierte Werte arbeitet, müssen Sie nur die Zahlen in der schwierigen Bit unten verwendet wird, beschränken müssen

Ein guter Start ist durch 2, 4 und 8. Diese kann jeweils mit Rechtsverschiebungen von 1, 2 und 3 Bits durchgeführt werden, die CPU unter der Annahme hat eine logische Verschiebung nach rechts Anweisung.

Zum anderen um 1 Teilung nur die Zahl hält, wie sie ist. Das nur Blätter, 3, 5, 6, 7 und 9.

Tricky Bit beginnt hier:

Für die anderen Zahlen, können Sie die Tatsache nutzen, dass eine Kluft kann durch eine Multiply-and-Verschiebung ersetzt werden.

Angenommen, Sie haben einen 16-Bit-Prozessor. So teilen Sie durch N, Sie durch 256 / N multiplizieren und rechts verschieben 8 Bits: 

N = 3, multiply by 85
N = 5, multiply by 51
N = 6, multiply by 43
N = 7, multiply by 37
N = 9, multiply by 28

Nehmen Sie die Zufalls Beispiel 72 / 5. Multiplizieren 72 von 51 3672 erhalten dann rechts 8 Bits verschieben 14 zu erhalten.

Damit dies funktioniert, Ihre Zahlen, die Sie verwenden müssen die 16 Bit nicht überlaufen. Da Ihr schlimmster Fall ist Multiplikation mit 85, können Sie Zahlen verarbeiten bis zu 771.

Der Grund, dies funktioniert, ist, weil eine Verschiebung rechts von 8 Bits gleich ist mit 256 als Dividieren und: 

  m * (256 /  n) / 256
= m / (n /  256) / 256
= m /  n *  256  / 256
= m /  n * (256  / 256)
= m /  n

Wenn Sie eine 32-Bit-Prozessor haben, ändern sich die Werte und Bereiche etwas, da es 65536 ist / N: 

N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600.
N = 5, multiply by 13,108.
N = 6, multiply by 10,923.
N = 7, multiply by  9,363.
N = 9, multiply by  7,282.

Auch hier lassen Sie uns wählen, die zufällige 20.000 / 7: 20.000 von 9363 multipliziert 187.260.000 ist, und wenn Sie richtig, dass 16 Bits verschieben, Sie 2857 erhalten - das eigentliche Ergebnis ist 2857

.

Das folgende Testprogramm in C zeigt die Genauigkeitswert für die angegebenen Werte. Es verwendet signierte Werte so ist nur gut, bis etwa 98.000, aber man kann sehen, dass der größte Fehler 1 ist und dass es tritt am Tiefpunkt von 13.110 (nur 0,008% Fehlern). 

#include <stdio.h>
int res[5] = {0};
int low[5] = {-1,-1,-1,-1,-1};
int da[] = {3,5,6,7,9};
int ma[] = {21846,13108,10923,9363,7282};
int main (void) {
    int n, i;
    for (n = 0; n < 98000; n++) {
        for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) {
            int r1 = n / da[i];
            int r2 = (n * ma[i])>>16;
            int dif = abs (r1-r2);
            if (dif >= 5) {
                printf ("%d / %d gives %d and %d\n", n, da[i], r1, r2);
                return 1;
            }
            res[dif]++;
            if (low[dif] == -1) {
                low[dif] = n;
            }
        }
    }
    for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) {
        printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]);
    }
    return 0;
}

Diese Ausgänge: 

Difference of 0: 335874, lowest value was      0
Difference of 1: 154126, lowest value was  13110
Difference of 2:      0, lowest value was     -1
Difference of 3:      0, lowest value was     -1
Difference of 4:      0, lowest value was     -1
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top