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

Question

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

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

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

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

Answer 1

Подумайте так: ваш номер 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)

Answer 2

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

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

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.

Answer 3

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