Schnelle Division auf GCC/ARM

Question

Soweit ich weiß, werden die meisten Compiler schnelle Division durch Multiplizieren und dann Bitverschiebung nach rechts tun. Zum Beispiel, wenn Sie this SO thread überprüfen, heißt es, dass, wenn Sie den Microsoft-Compiler bitten, Division durch 10 zu tun, wird der Dividend mit 0x1999999A multipliziert (was 2^32/10 ist) und dann das Ergebnis durch 2^32 dividieren (mit 32 Verschiebungen auf der rechten Seite).

So weit so gut.

Sobald ich die gleiche Abteilung von 10 auf ARM mit GCC getestet, obwohl, der Compiler tat etwas anderes. Zuerst multiplizierte es die Dividende mit 0x66666667 (2^34/10), dann teilte es das Ergebnis mit 2^34. Bisher ist es dasselbe wie Microsoft, außer dass ein höherer Multiplikator verwendet wird. Danach subtrahierte es jedoch (Dividend/2^31) vom Ergebnis.

Meine Frage: Warum auf der ARM-Version gibt es diese zusätzliche Subtraktion? Können Sie mir ein numerisches Beispiel geben, wo ohne diese Subtraktion das Ergebnis falsch sein wird?

Wenn Sie den erzeugten Code überprüfen möchten, ist es unten (mit meinen Kommentaren):

 ldr  r2, [r7, #4] @--this loads the dividend from memory into r2 
     movw r3, #:lower16:1717986919 @--moves the lower 16 bits of the constant 
     movt r3, #:upper16:1717986919 @--moves the upper 16 bits of the constant 
     smull r1, r3, r3, r2 @--multiply long, put lower 32 bits in r1, higher 32 in r3 
     asr  r1, r3, #2 @--r3>>2, then store in r1 (effectively >>34, since r3 was higher 32 bits of multiplication) 
     asr  r3, r2, #31 @--dividend>>31, then store in r3 
     rsb  r3, r3, r1 @--r1 - r3, store in r3 
     str  r3, [r7, #0] @--this stores the result in memory (from r3) 

Answer 1

Danach wurde jedoch vom Ergebnis abgezogen (Dividend/2^31).

Eigentlich ist es dividend >> 31 subtrahiert, die für negative -1dividend, und 0 für die nicht-negative Dividenden ist, wenn Rechtsverschieben negative ganze Zahlen arithmetische Verschiebung nach rechts (und int ist 32 Bit breit).

0x6666667 = (2^34 + 6)/10 

Also für x < 0, die wir haben, schreiben x = 10*k + r mit -10 < r <= 0,

0x66666667 * (10*k+r) = (2^34+6)*k + (2^34 + 6)*r/10 = 2^34*k + 6*k + (2^34+6)*r/10 

nun arithmetische Verschiebung nach rechts von negativen ganzen Zahlen ergibt den Boden von v/2^n, so

(0x66666667 * x) >> 34 

Ergebnisse in

k + floor((6*k + (2^34+6)*r/10)/2^34) 

Also brauchen wir, um zu sehen, dass

-2^34 < 6*k + (2^34+6)*r/10 < 0 

Die rechte Ungleichung einfach ist, sowohl k und r sind kraft- und nicht beide 0 sind

Für die linke Ungleichheit, ein bisschen mehr Analyse ist erforderlich.

r >= -9 

so dass der absolute Wert von (2^34+6)*r/10 ist höchstens 2^34+6 - (2^34+6)/10.

|k| <= 2^31/10, 

so |6*k| <= 3*2^31/5.

Und es bleibt, dass

6 + 3*2^31/5 < (2^34+6)/10 
1288490194 < 1717986919 

Yup, um wahr zu überprüfen.

Answer 2

x SAR 31 ist 0xffffffff (-1) für negative Werte von x und 0x00000000 für positive Werte.

So zieht die rsb -1 aus dem Ergebnis (das ist das gleiche wie das Hinzufügen von 1), wenn der Dividenden negativ war.

Angenommen, Ihre Dividende ist -60. Mit nur der Multiplikation und der Verschiebung erhalten Sie das Ergebnis -7, also subtrahiert -1, um das erwartete Ergebnis von -6 zu erhalten.