Как умножить числа с фиксированной запятой, если фиксированная и дробная части хранятся отдельно? - PullRequest
Новая
       31

Как умножить числа с фиксированной запятой, если фиксированная и дробная части хранятся отдельно?

1 голос
/ 30 октября 2019

Я хочу умножить два числа с фиксированной точкой на разную дробную длину. Часть с фиксированной точкой и дробная часть хранятся отдельно: 

123    . 4
fix    . frac
sint32 . sint32

Я использую две переменные, одну для фиксированной части и одну для дробной.

Я пытался использовать алгоритм Карацубы. Но этот работает только с фиксированной длиной дробного. Дробная часть двух чисел меняется. Они могут быть одинаковыми, но на это есть какая-то гарантия. Конечно, максимально возможное значение (2 ^ 32) - 1.

Как лучше всего умножить 123,4 на 56,789? 

// a = 123.4
signed int a_fxd = 123;
signed int a_frx = 4;
// b = 56.789
signed int b_fxd = 56
signed int b_frc = 789;

1 Ответ

2 голосов
/ 30 октября 2019

Вам необходимо решить, каков фактический коэффициент масштабирования для вашей дробной части. Для вашего конкретного примера, похоже, что подходящий коэффициент может быть 1/1000 или 0,001. Это означает, что 56,789 представляется как 56 + 789 × 0,001. Но это означает, что 123,4 будет представлено как 12 + 400 × 0,001. То есть, у вас была ошибка в вашем вопросе: a_frx будет 400, а не 4.

Я не знаю Алгоритм Карацубы , и я подозреваю, что он на самом деле не применим к этомупроблема в любом случае. Я знаю только то, что заработал в начальной школе.

Давайте представим коэффициент масштабирования на sc. Таким образом, наше умножение на самом деле 

( a_fxd + a_frx * sc ) * ( b_fxd + b_frx * sc )

Умножая это, мы получим 

a_fxd * b_fxd + a_fxd * b_frx * sc + a_frx * b_fxd * sc + a_frx * b_frx * sc * sc

Собирая термины, мы получим 

a_fxd * b_fxd + (a_fxd * b_frx + a_frx * b_fxd + a_frx * b_frx * sc) * sc

Так что, если мы представим продукт какp_fxd и p_frx, похоже, у нас будет 

p_fxd = a_fxd * b_fxd
p_frx = a_fxd * b_frx + a_frx * b_fxd + a_frx * b_frx * sc

Давайте добавим фактические значения: 

p_fxd = 123 * 56 = 6888
p_frx = 123 * 789 + 400 * 56 + 400 * 789 * 0.001 = 119762.600

Но есть дополнительная складка, потому что p_frxдействительно должно быть целым числом в диапазоне 0..999. Итак, нам нужно сбросить 0,600 и нести 119. Таким образом, наш окончательный результат равен 

p_fxd = 6888 + 119 = 7007
p_frx = 762

И это соответствует правильному результату, 123,4 × 56,789 = 7007,762.

.. Ну, на самом деле правильный правильный результат равен 7007,7626 или округлен до трех цифр, 7007,763. Строго говоря, мы не должны были выбрасывать .600, которые мы получили в p_frx, мы должны были округлить.

Могут также быть некоторые дополнительные морщины, о которых нужно позаботиться, когда мы рассматриваем возможностьотрицательные числа.

Наконец, есть выбор коэффициента масштабирования. На практике, 0,001, который я использовал здесь, на самом деле не является реалистичным значением. Для алгоритма общего назначения вы, вероятно, будете использовать что-то вроде 1/10000, или 1/1000000000, или 1/32768, или 1/65536, или что-то в этом роде. (Использование степеней двойки приводит к увеличению диапазонов и, как правило, более эффективным вычислениям, но менее очевидным дробным частям и менее эффективным преобразованиям в и из десятичных представлений. Например, если вы использовали коэффициент масштабирования 1/32768, a_frx будетбудет 13107, а b_frx будет 25853 или 25854.)

...