Wenn eine Hardware keine Modulus- oder Divisionsoperationen unterstützt, dauert es viel mehr CPU-Zyklen, um Modulus/Division durch Software zu simulieren. Gibt es eine schnellere Möglichkeit, Division und Modul zu berechnen, wenn der Operand 10 ist?
In meinem Projekt muss ich häufig den ganzzahligen Modul 10 berechnen. Insbesondere arbeite ich an PIC16F und muss eine Zahl auf einem LCD anzeigen. Es müssen 4 Ziffern unterstützt werden, also gibt es 4 Aufrufe für die Modulus- und Divisionsfunktion (Softwareimplementierung). Das heißt, wie folgt:
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
Es gibt andere Bereiche, die ähnlichen Code verwenden.
Hier ist ein Binär-zu-BCD-Algorithmus, den ich vor einigen Jahren verwendet habe, basierend auf einem, der hier gefunden wurde . Ich habe einen externen BCD-zu-7-Sekunden-Anzeigetreiber verwendet, damit das Ergebnis direkt als gepacktes BCD zur Ausgabe an die richtigen Ports geschrieben werden kann.
Dies ist ziemlich schnell, wenn Sie einen Hardware-Multiplikator im PIC haben, ich habe einen PIC18F97J60 verwendet. Wenn Sie keinen Hardware-Multiplikator auf Ihrem PIC haben, sollten Sie die Verwendung von Shift + Add für die Multiplikation in Betracht ziehen.
Dies nimmt ein vorzeichenloses 16-Bit-Int auf und gibt gepacktes BCD mit 5 Ziffern zurück. Es könnte geändert und für 4 Ziffern schneller gemacht werden. Es verwendet Shift + Additionen, um die Division durch 10 anzunähern, aber angesichts des begrenzten Eingabebereichs ist es genau für diese Verwendung. Möglicherweise möchten Sie das Ergebnis auch anders packen, um es an die Verwendung des Ergebnisses anzupassen.
void intToPackedBCD( uint16_t n, uint8_t *digits ) {
uint8_t d4, d3, d2, d1, d0, q; //d4 MSD, d0 LSD
d1 = (n>>4) & 0xF;
d2 = (n>>8) & 0xF;
d3 = (n>>12) & 0xF;
d0 = 6*(d3 + d2 + d1) + (n & 0xF);
q = (d0 * 0xCD) >> 11;
d0 = d0 - 10*q;
d1 = q + 9*d3 + 5*d2 + d1;
q = (d1 * 0xCD) >> 11;
d1 = d1 - 10*q;
d2 = q + 2*d2;
q = (d2 * 0x1A) >> 8;
d2 = d2 - 10*q;
d3 = q + 4*d3;
d4 = (d3 * 0x1A) >> 8;
d3 = d3 - 10*d4;
digits[0] = (d4<<4) | (d3);
digits[1] = (d2<<4) | (d1);
digits[2] = (d0<<4);
}
Unter der Annahme von vorzeichenlosen ganzen Zahlen können Division und Multiplikation aus Bitverschiebungen gebildet werden. Und aus (ganzzahliger) Division und Multiplikation kann Modulo abgeleitet werden.
Mit 10 multiplizieren:
y = (x << 3) + (x << 1);
Durch 10 zu teilen ist schwieriger. Ich kenne mehrere Divisionsalgorithmen. Wenn ich mich richtig erinnere, gibt es eine Möglichkeit, mit Bitverschiebungen und Subtraktion schnell durch 10 zu dividieren, aber ich kann mich nicht an die genaue Methode erinnern. Wenn das nicht stimmt, dann ist dies ein Teilungsalgorithmus, der <130 Zyklen verwaltet . Ich bin mir nicht sicher, welches Mikro Sie verwenden, aber Sie können es irgendwie verwenden, auch wenn Sie es portieren müssen.
BEARBEITEN: Jemand sagt drüben bei Stack Overflow , wenn Sie ein bisschen Fehler tolerieren können und ein großes temporäres Register haben, wird dies funktionieren:
temp = (ms * 205) >> 11; // 205/2048 is nearly the same as /10
Angenommen, Sie haben Division und Multiplikation, ist Modulo einfach:
mod = x - ((x / z) * z)
Sie können mit dem Double-Dabble-Algorithmus ohne Division von binär zu gepacktem BCD konvertieren . Es verwendet nur shift und add 3 .
Konvertieren Sie zum Beispiel 243 10 = 11110011 2 in binär
0000 0000 0000 11110011 Initialization
0000 0000 0001 11100110 Shift
0000 0000 0011 11001100 Shift
0000 0000 0111 10011000 Shift
0000 0000 1010 10011000 Add 3 to ONES, since it was 7
0000 0001 0101 00110000 Shift
0000 0001 1000 00110000 Add 3 to ONES, since it was 5
0000 0011 0000 01100000 Shift
0000 0110 0000 11000000 Shift
0000 1001 0000 11000000 Add 3 to TENS, since it was 6
0001 0010 0001 10000000 Shift
0010 0100 0011 00000000 Shift
2 4 3
BCD
Dieser Algorithmus ist sehr effizient, wenn kein Hardware-Divisor verfügbar ist. Darüber hinaus wird nur die Linksverschiebung um 1 verwendet, so dass es schnell ist, auch wenn kein Barrel-Shifter verfügbar ist
Abhängig von der Anzahl der benötigten Ziffern können Sie möglicherweise die Brute-Force-Methode verwenden ( d- Eingabenummer, t- Ausgabe ASCII-Zeichenfolge):
t--;
if (d >= 1000) t++; *t = '0'; while (d >= 1000) { d -= 1000; *t += 1; }
if (d >= 100) t++; *t = '0'; while (d >= 100) { d -= 100; *t += 1;}
if (d >= 10) t++; *t = '0'; while (d >= 10) { d -= 10; *t += 1;}
t++; *t = '0' + d;
Sie können die mehrfachen ifs auch in eine Schleife verwandeln, wobei Zehnerpotenzen durch Multiplikation oder eine Nachschlagetabelle erhalten werden.
Dieser Anwendungshinweis beschreibt Algorithmen für die BCD-Arithmetik, einschließlich der Konvertierung von binär nach BCD und umgekehrt. Die Appnote stammt von Atmel, das ist AVR, aber die beschriebenen Algorithmen sind prozessorunabhängig.
Ich habe keine gute Antwort, aber es gibt eine großartige Diskussion auf unserer Schwesterseite Stack Overflow zum genau gleichen Thema der Division und Modulo-Optimierung.
Haben Sie genug Speicher, um eine Nachschlagetabelle zu implementieren?
Hackers Delight hat einen Artikel über optimale Divisionsalgorithmen veröffentlicht.
Haben Sie darüber nachgedacht, diesen Wert die ganze Zeit als BCD zu halten (unter Verwendung einfacher spezieller "BCD-Inkrement"- und "BCD-Add"-Subroutinen), anstatt diesen Wert in binärer Form zu halten und nach Bedarf in BCD zu konvertieren (mit einem schwieriger zu verstehenden "convert vom Binär- zum BCD"-Unterprogramm)?
Zu einer Zeit speicherten alle Computer alle Daten als Dezimalziffern (Zahnräder mit zehn Positionen, Zwei-aus-fünf-Code-Vakuumröhren, BCD usw.), und dieses Vermächtnis besteht noch heute. (siehe Warum verwenden Echtzeituhr-Chips BCD ).
Die PICList ist eine erstaunliche Ressource für Leute, die PIC-Prozessoren programmieren.
BCD-Konvertierung
Haben Sie darüber nachgedacht, eine handelsübliche, bewährte Binär-zu-BCD-Subroutine zu verwenden, die speziell für den PIC16F optimiert wurde?
Insbesondere haben Leute auf der PICList viel Zeit damit verbracht, Binär-zu-BCD-Konvertierungen auf einem PIC16F zu optimieren. Diese Routinen (jede von Hand für eine bestimmte Größe optimiert) sind unter "PIC Microcontoller Radix Conversion Math Methods" http://www.piclist.com/techref/microchip/math/radix/index.htm zusammengefasst
ganzzahlige Division und mod
Auf einer CPU wie dem PIC16F ist eine Unterroutine, die auf die Division durch eine Konstante spezialisiert ist, oft viel schneller als eine Allzweckroutine "Variable A durch Variable B dividieren". Vielleicht möchten Sie Ihre Konstante (in diesem Fall "0.1") in die "Code Generation for Constant Multiplication/Division" http://www.piclist.com/techref/piclist/codegen/constdivmul.htm einfügen oder die vorgefertigte Routinen in der Nähe von http://www.piclist.com/techref/microchip/math/basic.htm .
Bei einer 8x8-Hardware-Multiplikation kann man ein divmod-10 einer Zahl beliebiger Größe berechnen, indem man eine Routine verwendet, die es für eine 12-Bit-Zahl im Bereich 0-2559 über die Prozedur berechnet:
Ich würde vorschlagen, eine divmod-Routine zu schreiben, bei der das MSB der Zahl in W steht und das LSB, auf das FSR zeigt; Die Routine sollte den Quotienten in FSR mit Post-Dekrement speichern und den Rest in W belassen. Um eine 32-Bit-Länge durch 10 zu teilen, würde man dann etwa Folgendes verwenden:
movw 0 lfsr 0,_number + 3 ; Zeigen Sie auf MSB Rufen Sie _divmod10_step auf Rufen Sie _divmod10_step auf Rufen Sie _divmod10_step auf Rufen Sie _divmod10_step auf
Ein divmod-6-Schritt wäre sehr ähnlich, außer dass Konstanten von 85 und 6 anstelle von 51 und 10 verwendet werden. In beiden Fällen würde ich erwarten, dass der divmod10_step 20 Zyklen (plus vier für den Aufruf/Rückgabe) wäre, also würde ein kurzer divmod10 etwa 50 Zyklen sein und ein langer divmod10 wäre etwa 100 (wenn man den ersten Schritt in Spezialfällen macht, könnte man ein paar Zyklen sparen).
Dies ist vielleicht nicht der schnellste, aber ein einfacher Weg.
a = 65535;
l = 0;
m = 0;
n = 0;
o = 0;
p = 0;
while (a >= 10000)
{ a -= 10000;
l += 1;
}
while (a >= 1000)
{ a -= 1000;
m += 1;
}
while (a >= 100)
{ a -= 100;
n += 1;
}
while (a >= 10)
{ a -= 10;
o += 1;
}
while (a > 0)
{ a -= 1;
p += 1;
}
Nick T
Donotalo
Nick T
Donotalo
RBerteig
trosley
Jan Vernier