Какой самый быстрый способ умножить 16-битное целое на двойное?

Question

На 8-битном микроконтроллере я хотел бы сделать следующее:

16bit_integer = another_16bit_integer * 0.997;

с наименьшим количеством инструкций.

Answer 1

Как насчет целочисленной арифметики в 32 битах?

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

32 бита будет достаточно для хранения (INT16_MAX × 997), сложите значения в 1000 раз больше, а затем разделите обратно на 16-битную шкалу.

Answer 2

Сдвиги битов обычно бывают очень быстрыми:

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

Это, вероятно, лучше записать как:

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

Хороший компилятор сгенерирует эквивалентный вывод.

Если ваши целые числа подписаны, константы следует изменить на 0x8000 и 15.

Answer 3

Возможно, вы имели в виду некоторое округление, а не усечение результата до целого числа, в противном случае цель операции действительно ограничена.

Но так как вы задали вопрос с этой конкретной формулой, это напомнило, что ваш набор результатов действительно грубый. Для первых 333 чисел результат будет следующим: another_16bit_integer-1. Вы можете аппроксимировать это (может быть, даже точно, когда не выполняется в моей голове) что-то вроде:

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

edit: unsigned int, и вы обрабатываете 0 самостоятельно.

Answer 4

Вот очень быстрый способ сделать эту операцию:

a = b * 0.99609375;

Это похоже на то, что вы хотите, но это намного быстрее.

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

Или даже быстрее, используя хитрость, которая работает только на системах с прямым порядком байтов, таких как PIC.

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

С макушки головы это сводится к следующему ассемблеру на 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

Answer 5

На моей платформе (8-битный микроконтроллер Atmel AVR, работает gcc)

16bit_integer = another_16bit_integer * 0.997;

Принимает около 26 инструкций.

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

Принимает около 25 инструкций.

Answer 6

На моей платформе (8-битный микроконтроллер Atmel AVR, работает gcc)

16bit_integer = another_16bit_integer * 0.997;

Принимает около 26 инструкций.

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

Принимает около 25 инструкций.

Atmel AVR - это микросхема RISC, поэтому инструкции по подсчету являются достоверным сравнением.

Answer 7

Поскольку вы используете 8-битный процессор, вы, вероятно, можете обрабатывать только 16-битные результаты, а не 32-битные. Чтобы уменьшить 16-разрядные проблемы переполнения, я бы повторил формулу следующим образом:

result16 = operand16 - (operand16 * 3)/1000

Это даст точные результаты для целых чисел без знака до 21845 или целых чисел со знаком до 10922. Я предполагаю, что процессор может делать 16-битное целочисленное деление. Если вы не можете, то вам нужно сделать сложный путь. Умножение на 3 может быть выполнено простым сдвигом и сложением, если не существует команды умножения или если умножение работает только с 8-битными операндами.

Не зная точного микропроцессора, невозможно определить, сколько времени займет такой расчет.

Answer 8

Предварительно вычисленная таблица поиска:

16bit_integer = products[another_16bit_integer];

Это не будет работать так хорошо на AVR, 16-битное адресное пространство будет исчерпано.

Answer 9

Предварительно вычисленная таблица поиска:

16bit_integer = products[another_16bit_integer];