Умножение с фиксированной точкой - «решение», сумасшедшее или жизнеспособное? - PullRequest
Новая
       19

Умножение с фиксированной точкой - «решение», сумасшедшее или жизнеспособное?

2 голосов
/ 26 мая 2010

Предположим, это много:
Я использую систему с фиксированной точкой 16.16.
Система 32-битная.
CPU не имеет процессора с плавающей запятой.
Переполнение довольно неизбежно для умножения на все, что больше, чем 1,0 * 0,4999

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

//assume that in practical application
//this assignment wouldn't be here as 2 fixed values would already exist...
fixed1 = (int)(1.2341 * 65536);
fixed2 = (int)(0.7854 * 65536);

mask1 = fixed1 & 0xFF; //mask off lower 8 bits

fixed1 >>= 8; //keep upper 24 bits... assume value here isn't too large...

answer = (((fixed2 * fixed1) >> 8) + ((fixed2 * mask1) >> 16));

Итак, вопрос в том ... это гениальный удар (не говоря уже о том, что об этом уже не думали или что-то в этом роде) или полная трата времени?

1 Ответ

1 голос
/ 26 мая 2010

Повторно отредактируйте - потому что я был не прав:)

Похоже, вы пытаетесь получить более высокую точность, используя дополнительный var?

Если вы действительно пытаетесь повысить точность, тогда это сработает, но почему бы не использовать целое число вместо 8-битного?

Хорошо, из ваших комментариев вы хотели знать, как делать муль 64-битной точности на 32-битном процессоре. Самый простой способ, если процессор под вами имеет длинную операцию умножения. Если это ARM, вам повезло, и вы можете использовать long long, чтобы сделать свой мул, а затем убрать свои младшие биты за пределы и все будет готово.

Если этого не произойдет, вы все равно можете сделать длинное умножение и позволить автору компилятора сделать тяжелую работу по обработке переполнения за вас. Это самые простые методы.

В противном случае вы получаете 4 16-битных умножения и кучу добавлений и сдвигов: 


// The idea is to break the 32-bit multiply into 4 16-bit 
parts to prevent any overflow.  You can break any 
multiply into factors and additions (all math here is unsigned):
      (ahi16)(alo16)
X     (bhi16)(blo16)
--------------------
      (blo16)(alo16)  - First  32-bit product var
  (blo16)(ahi16)&lt&lt16  - Second 32-bit product var (Don't shift here)
  (bhi16)(alo16)&lt&lt16  - Third  32-bit product var (Don't shift here)
+ (bhi16)(ahi16)&lt&lt32  - Forth  32-bit product var (Don't shift here)
--------------------
Final Value.  Here we add using add and add 
with carry techniques to allow overflow.

По сути, у нас низкий продукт и высокий продукт. Низкому продукту присваивается первый частичный продукт. Затем вы добавляете 2 средних продукта, сдвинутых на 16. Для каждого переполнения вы добавляете 1 к старшему продукту и продолжаете. Затем добавьте верхние 16 бит каждого среднего продукта в старший продукт. Наконец, добавьте последний продукт как есть в верхний продукт.

Большая боль в заднице, но она работает для любой неожиданной точности значений.

...