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

Question

Я знаю, я знаю, люди, вероятно, скажут «просто переключиться на плавучую точку», но в настоящее время это не вариант из-за характера проекта, который Я работаю. Я помогаю писать язык программирования на C++, и в настоящее время у меня возникают трудности с попыткой получить очень точный алгоритм умножения, в результате которого у меня есть виртуальная машина, и в основном операции для mod/smod, div/sdiv (т.е. подписанные числа не являются проблемой здесь), mul, число в два раза для полных дробных чисел и число сдвинутого сдвига, которое я умножаю и разделяю, чтобы создать свое смещение. Для простоты, скажем, я работаю с 32-байтным пространством. Мои алгоритмы отлично работают для всего, что связано с целыми числами, просто когда моя дробная часть получает более 16 байтов, которые я сталкиваюсь с проблемами с точностью, и если бы я был вокруг нее, число было бы довольно точным, но я хочу, чтобы это как насколько это возможно, даже готовы пожертвовать небольшим успехом для него, если он остается неподвижным и не переходит в землю с плавающей точкой. Алгоритмы, с которыми я связан, я опишу в виде псевдокода. Было бы интересно узнать, как я могу сделать это лучше, или какие-либо соображения относительно того, почему по законам вычислительной науки то, о чем я прошу, является бесплодным делом.

для полных дробных чисел (все байты являются дробно):

A = num1/halfShift //truncates the number down to 16 so that when multiplied, we get a full 32 byte num 
B = num2/halfShift 
finalNum = A * B 

Для остальной части моих чисел, которые больше, чем 16 байт Я использую этот алгоритм:

this algorithm can essentially be broken down into the int.frac form 
essentially A.B * C.D taking the mathematic form of 
D*B/shift + C*A*shift + D*A + C*B 
if the fractional numbers are larger than the integer, I halve them, then multiply them together in my D*B/shift 
just like in the fully fractional example above 

Есть ли какое-то метода «магического» округления, о котором я должен знать? Пожалуйста, дайте мне знать.

Answer 1

Вы получаете наиболее точный результат, если сначала выполняете умножение и масштабируете. Конечно, это означает, что вам нужно сохранить результат умножения в 64-битном типе типа. Если это не вариант, ваш подход с переходом вперед имеет смысл. Но вы, безусловно, теряете точность.

В любом случае, вы можете увеличить точность немного, если вы округлите, а не обрезаете.

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

В вашем случае будет выглядеть следующим образом:

A = (num1 + 1<<(halfshift-1)) >> halfshift 
B = (num2 + 1<<(halfshift-1)) >> halfshift 
finalNum = A * B 

EDIT:

Пример того, как динамически масштабировать факторы и результат в зависимости от значений факторов (это улучшает разрешение и поэтому точность результата):

shiftA и shiftB должны быть установлены таким образом, чтобы A и B составляли 16 байтовых дробей, и поэтому результат 32 байта не может переполняться. Если shiftA и shiftB не известны заранее, его можно определить, считая начальные нули num1 и num2.

A = (num1 + 1<<(shiftA-1)) >> shiftA 
B = (num2 + 1<<(shiftB-1)) >> shiftB 
finalNum = (A * B) >> (fullshift - (shiftA + shiftB)) 

Answer 2

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