Was ist der schnellste Weg, um eine 16-Bit-Integer mit einem Doppel zu multiplizieren?

Question

Auf einem 8-Bit-Mikrocontroller würde Ich mag folgend tun:

16bit_integer = another_16bit_integer * 0.997;

mit einer möglichst geringen Anzahl von Instruktionen.

Answer 1

Wie wäre es mit Ganzzahlarithmetik in 32 Bits?

16bit_integer = (int16_t) (another_16bit_integer * (int32_t) 997/1000); 

32 Bits ausreichen werden, um die Summe auf Werte 1000mal größer zu speichern (INT16_MAX × 997), tun dann zu Ihrem 16-Bit-Skala teilen zurück.

Answer 2

Auf meiner Plattform (Atmel AVR 8-Bit-Mikrocontroller, laufen gcc)

16bit_integer = another_16bit_integer * 0.997;

nimmt etwa 26 Anweisungen.

16bit_integer = (int16_t) (another_16bit_integer * (int32_t) 997/1000);

dauert etwa 25 Anweisungen.

Answer 3

Precomputed Lookup-Tabelle:

16bit_integer = products[another_16bit_integer]; 

Answer 4

Precomputed Lookup-Tabelle:

16bit_integer = products[another_16bit_integer]; 

Das ist nicht so gut auf den AVR zur Arbeit zu gehen, die 16-Bit-Adressraum erschöpft sein wird .

Answer 5

Da Sie einen 8-Bit-Prozessor verwenden, können Sie wahrscheinlich behandeln nur 16-Bit-Ergebnisse, nicht 32-Bit-Ergebnisse. Zur Reduzierung der 16-Bit-Überlauf Probleme würde ich die Formel wie folgt neu formulieren:

result16 = operand16 - (operand16 * 3)/1000 

Dies würde für genaue Ergebnisse geben ganze Zahlen ohne Vorzeichen bis zu 21845 oder signierte ganze Zahlen bis zu 10922. ich den Prozessor gehe davon können 16-Bit-tun ganzzahlige Division. Wenn Sie nicht können, dann müssen Sie die Trennung auf die harte Tour machen. Die Multiplikation mit 3 kann durch einfache Verschiebungen erfolgen, indem & addiert wird, wenn keine Multiplikationsanweisung existiert oder wenn die Multiplikation nur mit 8-Bit-Operanden funktioniert.

Ohne den genauen Mikroprozessor zu wissen, ist es unmöglich zu bestimmen, wie lange eine solche Berechnung nehmen würde.

Answer 6

Auf meiner Plattform (Atmel AVR 8-Bit-Mikrocontroller, laufen gcc)

16bit_integer = another_16bit_integer * 0.997; 

nimmt etwa 26 Anweisungen.

16bit_integer = (int16_t) (another_16bit_integer * (int32_t) 997/1000); 

dauert etwa 25 Anweisungen.

Der Atmel AVR ist ein RISC-Chip, daher ist das Zählen der Anweisungen ein gültiger Vergleich.

Answer 7

Sie wollten wahrscheinlich etwas Rundung darin haben, anstatt das Ergebnis auf eine ganze Zahl abzuschneiden, sonst ist der Zweck der Operation wirklich begrenzt.

Aber da Sie die Frage mit dieser spezifischen Formel stellten, erinnerte es daran, dass Ihr Resultset wirklich grob ist. Für die ersten 333-Nummern lautet das Ergebnis: another_16bit_integer-1. Sie können es nähern (vielleicht sogar genau, wenn sie nicht in meinem Kopf durchgeführt) mit so etwas wie:

16bit_integer = another_16bit_integer - 1 - (another_16bit_integer/334); 

edit: unsigned int, und Sie behandeln 0 auf eigene Faust.

Answer 8

Bit-Verschiebungen sind in der Regel sehr schnell:

y = 0xFF3B * (int32_t) x >> 16; 

Dieses besser ist wahrscheinlich geschrieben als:

y = (0.997 * 0x10000) * (int32_t)x >> 16; 

Ein guter Compiler äquivalente Ausgabe generieren.

Wenn Ihre ganze Zahlen unterzeichnet werden, sollten die Konstanten 0x8000 verändert und 15.

Answer 9

Hier ist ein sehr schneller Weg, um diese Operation zu tun:

a = b * 0.99609375; 

Es ist ähnlich zu dem, was Sie wollen, aber es ist viel schneller.

a = b; 
a -= b>>8; 

Oder noch schneller einen Trick verwenden, die auf Little-Endian-Systemen funktioniert nur, wie die PIC.

a = b; 
a -= *((int8*)((&b)+1)); 

Aus der Spitze von meinem Kopf, das kommt auf die folgenden Assembler auf einem PIC18:

; a = b 
MOVFF 0xc4, 0xc2 
NOP 
MOVFF 0xc5, 0xc3 
NOP 

; a -= *((int8*)((&b)+1)); 
MOVF 0xc5, w 
SUBWF 0xc2, f 
BTFSC STATUS, C 
DECF 0xc