Whats the fastest way to multiply a 16-bit integer by a double?

Question

I want to to do this, on an 8-bit micro controller

16bit_integer = another_16bit_integer * 0.997;

with the least possible number of instructions.

Answer 1

How about integer arithmetic in 32 bits?

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

32 bits will be enough to store (INT16_MAX × 997), do the sum on values 1000 times larger then divide back to your 16 bit scale.

Answer 2

On my platform ( Atmel AVR 8-bit micro-controller, running gcc )

16bit_integer = another_16bit_integer * 0.997;

Takes about 26 instructions.

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

Takes about 25 instructions.

Answer 3

Precomputed lookup table:

16bit_integer = products[another_16bit_integer];

Answer 4

Precomputed lookup table:

16bit_integer = products[another_16bit_integer];

That's not going to work so good on the AVR, the 16bit address space is going to be exhausted.

Answer 5

Since you are using an 8 bit processor, you can probably only handle 16 bit results, not 32 bit results. To reduce 16 bit overflow issues I would restate the formula like this:

result16 = operand16 - (operand16 * 3)/1000

This would give accurate results for unsigned integers up to 21845, or signed integers up to 10922. I am assuming the the processor can do 16 bit integer division. If you cannot then you need to do the division the hard way. Multiplying by 3 can be done by simple shifts & adds, if no multiply instruction exists or if multiplication only works with 8 bit operands.

Without knowing the exact microprocessor it is impossible to determine how long such a calculation would take.

Answer 6

On my platform ( Atmel AVR 8-bit micro-controller, running gcc )

16bit_integer = another_16bit_integer * 0.997;

Takes about 26 instructions.

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

Takes about 25 instructions.

The Atmel AVR is a RISC chip, so counting instructions is a valid comparison.

Answer 7

You probably meant to have some rounding in there, rather than truncating the result to an integer, otherwise the purpose of the operation is really limited.

But since you asked the question with that specific formula, it brought to mind that your result set is really coarse. For the first 333 numbers, the result is: another_16bit_integer-1. You can approximate it (maybe even exactly, when not performed in my head) with something like:

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

edit: unsigned int, and you handle 0 on your own.

Answer 8

Bit shifts are usually very fast:

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

This is probably better written as:

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

A good compiler will generate equivalent output.

If your integers are signed, the constants should be changed to 0x8000 and 15.