Wenn eine Hardware keine Modul- oder Divisionsoperationen unterstützt, sind viel mehr CPU-Zyklen erforderlich, um den Modul / die 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 Ganzzahlmodul 10 berechnen. Insbesondere arbeite ich an PIC16F und muss eine Zahl auf einem LCD anzeigen. Es sind 4 Ziffern zu unterstützen, daher gibt es 4 Aufrufe der Modul- und Divisionsfunktion (Software-Implementierung). 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.
Antworten:
Hier ist ein Binär-BCD-Algorithmus, den ich vor einigen Jahren verwendet habe, basierend auf einem hier gefundenen . Ich habe einen externen BCD-zu-7-Seg-Anzeigetreiber verwendet, damit das Ergebnis direkt als gepacktes BCD für die Ausgabe auf die richtigen Ports geschrieben werden kann.
Dies ist ziemlich schnell, wenn Sie einen Hardware-Multiplikator im PIC haben, ich habe einen PIC18F97J60 verwendet. Wenn Ihr PIC keinen Hardware-Multiplikator enthält, sollten Sie Shift + Add für die Multiplikation verwenden.
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 zu approximieren, aber angesichts des begrenzten Eingabebereichs ist es genau für diese Verwendung. Möglicherweise möchten Sie das Ergebnis auch anders verpacken, um festzustellen, wie Sie das Ergebnis verwenden.
quelle
Unter der Annahme von Ganzzahlen ohne Vorzeichen können Division und Multiplikation aus Bitverschiebungen gebildet werden. Und aus (ganzzahliger) Division und Multiplikation kann Modulo abgeleitet werden.
Mit 10 multiplizieren:
Durch 10 zu teilen ist schwieriger. Ich kenne mehrere Divisionsalgorithmen. Wenn ich mich richtig erinnere, gibt es eine Möglichkeit, durch Bitverschiebungen und Subtraktion schnell durch 10 zu teilen, aber ich kann mich nicht an die genaue Methode erinnern. Wenn dies nicht der Fall ist, handelt es sich um einen Divisionsalgorithmus, der <130 Zyklen verwaltet . Ich bin nicht sicher, welches Mikro Sie verwenden, aber Sie können das auf irgendeine Weise verwenden, selbst wenn Sie es portieren müssen.
EDIT: Jemand sagt bei Stack Overflow , wenn Sie ein bisschen Fehler tolerieren können und ein großes temporäres Register haben, funktioniert dies:
Angenommen, Sie haben Division und Multiplikation, ist Modulo einfach:
quelle
Mit dem Double-Dabble-Algorithmus können Sie ohne Division von binärem zu gepacktem BCD konvertieren . Es wird nur Shift und Add 3 verwendet .
Konvertieren Sie beispielsweise 243 10 = 11110011 2 in binär
Dieser Algorithmus ist sehr effizient, wenn kein Hardware-Divisor verfügbar ist. Darüber hinaus wird nur die Linksschaltung um 1 verwendet, sodass sie auch dann schnell ist, wenn kein Barrel Shifter verfügbar ist
quelle
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):Sie können die mehreren ifs auch in eine Schleife ändern, deren Zehnerpotenzen durch Multiplikation oder eine Nachschlagetabelle erhalten werden.
quelle
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, AVR, aber die beschriebenen Algorithmen sind prozessorunabhängig.
quelle
Ich habe keine gute Antwort, aber auf unserer Schwesterseite Stack Overflow gibt es eine großartige Diskussion zum exakt gleichen Thema der Division und Modulo-Optimierung.
Haben Sie genug Speicher, um eine Nachschlagetabelle zu implementieren?
Hackers Delight hat ein Papier über optimale Teilungsalgorithmen.
quelle
Haben Sie darüber nachgedacht, diesen Wert die ganze Zeit als BCD zu halten (unter Verwendung einfacher spezieller Unterroutinen "BCD-Inkrement" und "BCD-Addition"), anstatt diesen Wert in binärer Form zu halten und nach Bedarf in BCD zu konvertieren (unter Verwendung einer schwieriger zu verstehenden "Konvertierung"? von binär zu BCD "Subroutine)?
Zu einer Zeit speicherten alle Computer alle Daten als Dezimalstellen (Zahnräder mit zehn Positionen, Vakuumröhren mit zwei von fünf Codes, BCD usw.), und dieses Erbe besteht bis heute fort. (Siehe Warum verwenden Echtzeituhr-Chips BCD ).
quelle
Die PICList ist eine erstaunliche Ressource für Leute, die PIC-Prozessoren programmieren.
BCD-Konvertierung
Haben Sie darüber nachgedacht, eine bewährte Binär-zu-BCD-Subroutine von der Stange zu verwenden, die speziell für den PIC16F optimiert wurde?
Insbesondere die Benutzer der PICList haben viel Zeit damit verbracht, die Binär-BCD-Konvertierung auf einem PIC16F zu optimieren. Diese Routinen (jeweils 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
Integer Division und Mod
Auf einer CPU wie dem PIC16F ist eine Subroutine, die auf das Teilen durch eine Konstante spezialisiert ist, häufig viel schneller als eine allgemeine Routine zum Teilen von Variablen A durch Variable B. Möglicherweise möchten Sie Ihre Konstante (in diesem Fall "0.1") in die "Codegenerierung für konstante Multiplikation / Division" http://www.piclist.com/techref/piclist/codegen/constdivmul.htm einfügen oder die Dosenroutinen in der Nähe von http://www.piclist.com/techref/microchip/math/basic.htm .
quelle
Bei einer 8x8-Hardware-Multiplikation kann ein Divmod-10 einer Zahl beliebiger Größe unter Verwendung einer Routine berechnet werden, die es für eine 12-Bit-Zahl im Bereich 0-2559 über die folgende Prozedur berechnet:
Ich würde vorschlagen, eine Divmod-Routine zu schreiben, bei der das MSB der Nummer in W steht und auf das LSB von FSR hingewiesen wird. Die Routine sollte den Quotienten in FSR mit Nachdekrementierung speichern und den Rest in W belassen. Um eine 32-Bit-Länge durch 10 zu teilen, würde man dann Folgendes verwenden:
Ein divmod-6-Schritt wäre sehr ähnlich, außer dass Konstanten von 85 und 6 anstelle von 51 und 10 verwendet würden. In beiden Fällen würde ich erwarten, dass der divmod10_step 20 Zyklen (plus vier für den Aufruf / die Rückgabe) beträgt, also ein kurzer divmod10 ungefähr 50 Zyklen sein und ein langer divmod10 wäre ungefähr 100 (wenn man den ersten Schritt in Sonderfällen macht, könnte man ein paar Zyklen sparen).
quelle
Dies ist möglicherweise nicht der schnellste, aber ein einfacher Weg.
quelle