Guten Abend zusammen,
ich will auf dem ARM Cortex M3/M4 eine Division durch eine effizientere
Multiplikation ersetzen. Bei dem erwarteten Wertebereich habe ich so
keine Genauigkeitsverluste zu verzeichnen. Momentan bin ich mir jedoch
unsicher, ob mir die Integer-Promotion bei negativem Zähler keinen
Strick drehen kann.
Gegeben ist ein Bruch a/b. b ändert sich selten. b ist positiv. Der
Übersicht halber habe ich alles in eine Funktion geschrieben:
1
int32_tdivideByB(int32_ta)
2
{
3
// Vorbereitung
4
constuint32_tb=12345L;
5
assert(b!=0);
6
uint32_toneDividedByB_q32;
7
if(b==1)
8
oneDividedByB_q32=UINT32_MAX;// Naeherung
9
else
10
oneDividedByB_q32=(1ULL<<32)/b;// Exakt
11
12
// Berechnung
13
int64_tresult=(int64_t)a*oneDividedByB_q32;// Kann nicht ueberlaufen, da 31 Bit * 32 Bit
14
returnresult/(1LL<<32);// Nur vorderes Register zurueckgeben
15
}
Die Hilfsvariable wurde q32 gewählt, damit das fertige Ergebnis direkt
in einem Register steht und der Bitshift erst gar nicht ausgeführt
werden muß. Bei der Berechnung der Hilfsvariablen wird der Nenner zu
UINT64 befördert und die Division ausgeführt (was lange dauert - hier
aber nicht weiter stört).
a ist Int64. oneDividedByB_q32 passt in ein Int64, wird also zu einem
Int64 befördert und die Multiplikation ausgeführt. Wenn b!=1, ist das
Ergebnis immer identisch mit der direkten Division.
Habe ich das richtig zusammengepuzzlet, oder habe ich irgendeinen
möglichen Überlauf übersehen?
Viele Grüße
W.T.
Macht natürlich nur Sinn, wenn dein Divisor immer gleich ist, und
"Vorbereitung" nicht jedesmal berechnet werden muss.
Statt
return result/(1LL<<32);
würde ich eher
return (result >> 32);
hinschreiben sonst baut dir der Compiler u.U. hier noch eine Division
ein.
Joe F. schrieb:> return (result >> 32);>> hinschreiben sonst baut dir der Compiler u.U. hier noch eine Division> ein.
Blöd nur das Bitshifts auf negativen Integers undefiniertes Verhalten in
C sind. Ich verstehe den OP so, dass er das nicht komplett ausschließen
kann.
Dr. Sommer schrieb:> Und das ist wirklich schneller als die 12 Takte, die Cortex-M3/4 für> eine Integer-Division braucht?
Wenn der Compiler das entsprechend umsetzt, braucht das vier Takte.
Mein
Joe F. schrieb:> würde ich eher>> return (result >> 32);>> hinschreiben
Hmneee, das Ergebnis wäre implementation defined. Ich will das
Vorzeichenbit durchaus mit Sicherheit behalten.
Dr. Sommer schrieb:> Und das ist wirklich schneller als die 12 Takte, die Cortex-M3/4 für> eine Integer-Division braucht?
Unmittelbar: Kaum. Mittelbar kann ich im Faktor oneDividedByX_q32
allerdings das Ergebnis einer längeren Rechnung zwischenspeichern, und
dann will ich den Teil mit der Multiplikation auch "noch eben"
mitnehmen, weil ich mir dann in der "schnellen" Funktion die
Fallunterscheidung mit O sparen kann.
Bitte noch einmal zurück zu meiner Frage:
1. Ich bin mir bei der Multiplikation Uint32_t/Int32 unsicher, ob ich
die Integer-Promotion-Regeln richtig ausgelegt habe - kann ich hier
immer sicher sein, daß nichts überlaufen kann?
2. Läßt sich das Vorgehen auf einen Divisor mit Vorzeichen erweitern?
Walter T. schrieb:> Und das Schlimme: Ich verstehe nicht warum.
Ist doch klar, bei der ersten Division wird abgerundet, weil (1<<32)
nicht glatt durch 5 teilbar ist. Somit ist das Ergebnis der
Multiplikation etwas zu klein und wird wieder abgerundet. Man könnte die
beiden Divisionen korrekt rundend ausführen aber auch dann müssten sich
Werte finden lassen bei denen es nicht passt.
Wenn du weniger als 22 signifikante Binär-Stellen hast, könntest du
float verwenden, da dauert die Multiplikation 1 Takt.
Du musst vor dem Shift, oder vor der Multiplikation runden durch
Addition eines Offsets. Der shift rundet nämlich ab. Hab mir jetzt aber
keine Gedanken über den negativen Bereich gemacht. Ich hab die Methode
früher für vorzeichenlose Divisionen auf avrs benutzt.
Tja, ein typischer Rundungsfehler.
4294967296 * 2 = 8589934592 ...
d.h., dein Ergebnis ist 1,9999999995343387126922607421875 und
für Integer wird einfach alles nach dem Komma entfernt --> 1
Ahoi, Martin
avr schrieb:> oder vor der Multiplikation runden durch Addition eines Offsets.
Mit dem Offset riskiere ich natürlich wieder einen Überlauf, wenn ich a
nicht begrenze. Für den einfachen Fall mit x/b mit int32_t x, b ist die
Multiplikation mit dem Kehrwert dann einfach zu kompliziert, weil
Fallunterscheidungen nötig sind.
Schade - aber nicht schlimm. Wie ja schon oben richtig geschrieben
wurde, kostet mich die nackte Division zweier 32-Bit-Zahlen gerade mal
maximal 12 Takte.
Generell suche ich auch noch immer nach einer sinnvollen allgemeinen
Lösung zum allgemeineren Problem
Walter T. schrieb:> Generell suche ich auch noch immer nach einer sinnvollen allgemeinen> Lösung zum allgemeineren Problem
Ist nicht so ganz trivial, zumindest wenn man sich den Code im GCC dazu
anschaut.
Und einfach mit dem "Kehrwert" zu multiplizieren ist auch nicht die
Lösung, zumindest wenn das Ergebnis das gleiche wie bei einer Division
sein soll. Eine unsigned Division durch 7 übersetzt gcc zum Beispiel
so:
1
div_7:
2
ldr r3, .L3
3
umull r2, r1, r0, r3
4
sub r0, r0, r1
5
add r0, r1, r0, lsr #1
6
lsr r0, r0, #2
7
bx lr
8
.align 2
9
.L3:
10
.word 613566757
Es gibt also noch zusätzliche Arithmetik, um das Ergebnis anzupassen.
Ohne diese Anpassung wird dein Ergebnis i.d.R. nicht mit dem Quotienten
einer entsprechenden Division übereinstimmen, und deine Hausaufgabe ist
dann, den (maximalen) Fehler abzuschätzen und zu entscheiden ob dieser
in der Anwendung tolerierbar ist.
Was du momentan versuchst ist eine Art JIT Ansatz, jedoch ohne über den
eigentlichen Algorithmus zu verfügen. Und selbst mit dessen Kenntnis
müsste immer noch eine Verzweigung anhand des Divisors geschehen, der
zusätzliche Laufzeit kostet. Oder der Algorithmus wied so allgemein
gehelten, dass er für alle Divisoren gültig ist, was u.U. einen
deitlich größeren Overhead bedeutet.
Überhaupt scheint das nur sinnvoll, wenn alle Divisoren bekannt sind,
und dann ein switch-case eine schnelle Verzweigung zum Code hinbekommt.
Oder wenn alle Divisoren eine gemeinsame Struktur haben, welche sich
dann in einem einheitlichen Algorithmus niederschlägt.
Walter T. schrieb:> Mit dem Offset riskiere ich natürlich wieder einen Überlauf, wenn ich a> nicht begrenze.
Der M4 hat doch auch saturierende Arithmetik. Auf dem AVR hab ich damals
übrigens meine Algorithmen für jede Eingabe auf dem PC getestet, um
sicher zu gehen, dass sie funktionieren.
Mit 8 Stunden Abstand fällt mir auf: Eigentlich ist das Ergebnis gar
nicht so schlecht. Über den kompletten Wertebereich liegt der Fehler im
Vergleich zur Rechnung mit double-Genauigkeit zwischen -1.5 und +0.5. Im
16-Bit-Bereich sogar zwischen -1 und 0.
Bei 10 und 5 sieht es nur drastisch falsch aus. Und exakt ist es
natürlich wirklich nicht.