Умножение/деление с фиксированной точкой для чисел 15,16

Я ищу алгоритм для умножения и деления чисел с фиксированной точкой 15.16.

У меня уже есть сложение и вычитание. Это было легко — простое 32-битное сложение и вычитание. С умножением и делением я также могу добавить множество тригонометрических и экспоненциальных/логарифмических функций. И я думаю, что могу справиться с простым умножением, так как в моей библиотеке есть обратная функция, и я могу использовать ее для реализации деления: a * (1/b) = a / b. Но 32-битное умножение не работает, так как оно игнорирует точку счисления.

Я работаю над 16-битным микроконтроллером, поэтому я хотел бы избежать чего-то большего, чем 32-битное умножение, которое занимает около 4 тактов на моем процессоре. Хотя это не критично, я просто пытаюсь заменить математику с плавающей запятой.

Я слышал, что мне нужно сдвинуть или повернуть результат, но я не уверен, как это поможет или, в частности, как его сместить. Любые предложения или помощь приветствуются!


fixed-point
person Thomas O    schedule 22.01.2011    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Подумайте об этом так: ваше число a.b представлено как (a.b * 65536)

Если вы умножите a.b * c.d, вы получите значение (a.b * 65536) * (c.d * 65536), поэтому, чтобы вернуть это в правильное представление, вам нужно разделить на 65536.

Когда вы делите ab / cd, вы получаете значение (ab * 65536) / (cd * 65536), поэтому, чтобы вернуть это в правильное представление, вам нужно умножить на 65536. Вы должны умножить на 65536 перед делением, чтобы сохранить как как можно больше битов в результате.

Конечно, вы можете заменить (‹‹ 16) на (* 65536), если это быстрее на вашем процессоре. Точно так же вы можете заменить (>> 16) на (/ 65536).

Здесь a.b * c.d:

uint32_t result_low = (b * d);
uint32_t result_mid = (a * d) + (b * c);
uint32_t result_high = (a * c); 
uint32_t result = (result_high << 16) + result_mid + (result_low >> 16)
person Doug Currie    schedule 22.01.2011
comment
Конечно, это так. Мое объяснение - алгоритм, а не реализация. - person Doug Currie; 22.01.2011
comment
Microchip также предоставляет математическую библиотеку с фиксированной точкой для PIC24 и dsPIC; см. microchip.com/stellent/ - person Doug Currie; 23.01.2011

arrow_upward
2
arrow_downward

Сначала теория: если предположить, что числа со знаком, умножение Q15.16 на другое Q15.16 даст вам число Q(15+15+1).(16+16) = Q31.32. Таким образом, вам нужна 64-битная целочисленная переменная для хранения результата.

Если ваш компилятор имеет 64-битный целочисленный тип, просто используйте его и дайте компилятору понять, как выполнить 32-битное x 32-битное умножение на 16-битном процессоре (для этого и нужны компиляторы):

int32_t a_15q16, b_15q16;
int64_t res_31q32 = (int64_t)a_15q16 * (int64_t)b_15q16;

То, что вы делаете потом с результатом Q31.32, действительно зависит от вашего приложения.

Вам может быть интересно, почему в результате требуется 31 целое число вместо 30. На самом деле дополнительный бит нужен только в том случае, когда вы умножаете -2^15 на -2^15. Если гарантировано, что ваши операнды никогда не будут равны -2^15 одновременно, вы можете принять результат Q30.32.

Чтобы узнать, поддерживает ли ваш компилятор 64-битные целые числа, вам может понадобиться просмотреть руководство по компилятору. Если это компилятор C99, посмотрите, есть ли тип int64_t в заголовке stdint.h.

person geschema    schedule 23.01.2011

arrow_upward
0
arrow_downward

Умножение легко выполняется с помощью 64-битного умножения: (a * b) >> 16. Точно так же деление легко выполняется с помощью 64 бит: (a << 16) / b. В зависимости от ваших требований к округлению/ошибке вы можете немного усложнить это, чтобы получить правильный последний бит вывода.

person Peter Taylor    schedule 22.01.2011
comment
@Paul R, не большая проблема, так как 32x32 на моем процессоре, я думаю, составляет около 4 циклов. - person Thomas O; 22.01.2011
comment
@Paul R, я делал заявление об этом заранее. - person Peter Taylor; 22.01.2011