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

Я знаю, я знаю, люди, вероятно, скажут «просто переключитесь на плавающую точку», но в настоящее время это не вариант из-за характера проекта, над которым я работаю. Я помогаю писать язык программирования на 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

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


person Richard John Catalano    schedule 08.07.2016    source источник
comment
Алгоритм. Слово «алгоритм». Это чье-то имя.   -  person user207421    schedule 08.07.2016
comment
A = num1 / halfShift //truncates the number down to 16 - как только вы уменьшите точность (разрешение, на самом деле) ввода (здесь до 16, а единица измерения (байты / цифры / биты / слова ...) имеет еще меньшее значение), нет количества точных арифметических действий можно восстановить / увеличить. Вместо этого выберите, сколько охранных мест вам потребуется (скажем, 2), и вычислите с выбранной точностью (32 + 2 = 34 в данном случае). В случае умножения это позволяет отбросить почти половину неполных произведений. Округлить до окончательной точности.   -  person greybeard    schedule 08.07.2016
comment
@greybeard, что вы имеете в виду под охранниками?   -  person Richard John Catalano    schedule 08.07.2016
comment
Вы могли бы потрудиться использовать википедию по контрольным цифрам или поисковую систему, чтобы найти Что должен знать каждый компьютерный ученый об арифметике с плавающей запятой. (Я избегаю защитных битов или цифр, чтобы не подразумевать базу. В любом случае, именование не стандартизировано: один авторский бит округления равен первый защитный бит другого автора.) (Если вы рассчитываете использовать представления с плавающей запятой для получения результатов для реальных проблем, во что бы то ни стало усвоите статью Голдберга - FP - злая магия. )   -  person greybeard    schedule 08.07.2016
comment
цените ресурсы. На самом деле я знаю.   -  person Richard John Catalano    schedule 08.07.2016
comment
(Добро пожаловать (на самом деле, на подсказки :-). Если вы хотите, чтобы кто-то, кто не опубликовал вопрос (или, в случае ответов, ответ) был уведомлен, упомяните ее имя, представленное @ (вы получите предложения) .)   -  person greybeard    schedule 09.07.2016


Ответы (2)


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

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

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

В вашем случае это будет выглядеть так:

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

РЕДАКТИРОВАТЬ:

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

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))
person maniacmic    schedule 12.07.2016
comment
Что ж, у меня есть возможность сначала умножить и где-нибудь сохранить ... хотя на самом деле не в 64-битном типе int ... на самом деле намного больше, и я работаю с 256-битным типом int по умолчанию с прямым порядком байтов. Однако я не могу хранить что-либо, кроме этих 256 бит, поэтому, если это то, что вы рекомендуете, я не уверен, что это сработает. - person Richard John Catalano; 15.07.2016
comment
Должно быть, он ошибся битами с байтами, когда я читал ваш вопрос. Если вы не можете сохранить результаты размером более 32 байтов, вам нужно придерживаться 16-байтовых значений в качестве факторов. - person maniacmic; 18.07.2016
comment
Кстати. Я забыл упомянуть, что вы также можете адаптировать коэффициент масштабирования для каждого умножения, чтобы результат не переполнялся, а затем примените оставшееся необходимое масштабирование к результату. В зависимости от числа это может значительно увеличить разрешение. Вероятно, даже больше, чем один бит, который вы получите при правильном округлении. - person maniacmic; 18.07.2016
comment
как это будет выглядеть, если применить оставшееся необходимое масштабирование к результату? - person Richard John Catalano; 19.07.2016
comment
@RichardJohnCatalano: Я обновил свой ответ, включив в него пример динамически масштабируемых факторов и продукта. - person maniacmic; 19.07.2016

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

person user207421    schedule 08.07.2016
comment
Но я думаю, что это хороший метод округления? Я новичок во всем этом, и я все еще пытаюсь понять, что делает хороший алгоритм округления. Если бы вы могли просто ответить на этот вопрос, я дам вам ответ. - person Richard John Catalano; 08.07.2016
comment
Я бы порекомендовал округлить до ближайшего. Должен работать, просто добавляя самый высокий отброшенный бит как самый низкий неотброшенный бит. - person Aconcagua; 09.07.2016