nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

О необходимости правильного округления


РЖД выпустили приказ: для повышения безопасности перевозок от всех поездов отцепить последний вагон,
т.к при авариях, когда один поезд вмазывается в зад другому, именно они страдают сильнее всего.


При работе с целыми числами, округление результата бывает весьма нетривиальной вещью, система команд наиболее ходовых процессоров для этого попросту не заточена. Например, на x86 процессорах перемножили два 32-битных числа, ответ получили в регистрах edx (старшие 32 бита) и eax (младшие 32). Теперь, если мы хотим округлить результат до 32 бит, хорошо бы к нашему 64-битному числу прибавить половинку будущего "младшего разряда", на что нужен ADD на младшие 32 бита и затем ADC, чтобы учесть перенос в старшие 32 бита. Так не хочется усложнять программу, чуть ли не удваивать её из-за этого, поэтому чаще всего на это "забивают", получая результат непосредственно из edx, а про eax забывая.

С делением тоже тяжело, особенно, со ЗНАКОВЫМ делением. Чтобы результат округлился до ближайшего целого, надо бы к делимому прибавить половинку делителя, если их знаки совпадают, или вычесть половинку делителя, если знаки разные.

Поэтому довольно быстро возникает мысль: а так ли это надо вообще? Может, просто отбрасывать дробную часть (в смысле, ненужные нам биты числа), и дело с концом? Фраза "точность снизится в два раза" звучит страшно. Но фраза "точность упадёт на 1 бит" - совсем не страшно :) Да ладно, у нас их и так 32, или вовсе 64, и вряд ли они все были значащими, и так сойдёт :) А если у нас был напряг с точностью, то тем более надо как можно скорее перейти на числа большей разрядности!

Я утверждаю: в достаточно сложных вычислениях точность из-за отсутствия правильного округления может упасть не в 2 раза, а на ПОРЯДКИ...


Идея достаточно проста: плохое округление, "отсечение" лишних бит, приводит к систематической погрешности, которая имеет обыкновение складываться "по амплитуде". 100 раз в разных местах ошиблись на 0,5 - получаем ошибку на 50 единиц.

Правильное же округление даёт исключительно случайную погрешность, которая складывается "по мощности", то бишь складываются дисперсии, а среднеквадратичное значение ошибки - это КОРЕНЬ из дисперсии. Поэтому 100 раз правильно округлили, в каждом конкретном случае получили ср. кв ошибку


но затем, если мы складываем эти 100 значений, то ошибка помножится на корень из ста, то есть мы получим ошибку 2,9 единиц. Вот она разница более чем на порядок.

Простую демонстрацию можно устроить в Excel'е:



В ячейку A1 записали формулу:
=СЛЧИС()*256

(в жуткой русскоязычной версии)

В ячейку B1 - формулу для округления вниз, т.е простого отсечения:
=ОКРУГЛВНИЗ(A1;0)


И в ячейку C1 - формулу для корректного округления:
=ОКРУГЛ(A1;0)


Затем копируем это на 100 строчек, и суммируем по каждому столбцу.

И можно нажимать F9 (полный пересчёт), чтобы получать новые выборки случайных чисел и смотреть на новые результаты.

Видно, что сумма правильно округлённых чисел действительно редко уходит от истинного значения более чем на 2-3 единицы, тогда как при отсечении мы всё время имеем существенно меньший результат.

Не говоря уже о том, что "случайные" ошибки в целом куда приятнее себя ведут, чем систематические. В следующий раз исходные данные немножко изменились - и это дало новую выборку ошибок округления. Если мы убрали систематику, то ответы от раза к разу будут крутиться вокруг правильного значения. В противном же случае мы можем с досадным постоянством получать один и тот же ответ, и всякий раз НЕПРАВИЛЬНЫЙ.

Мой практический пример. Сейчас попробовал напрочь убрать правильное округление из своей процедуры решения системы линейных уравнений 6х6 для алгоритма сопровождения. Пока оно было, всё работало в целом неплохо. К примеру, ошибка измерения дальности получалась на 23% больше, чем при использовании плавающей точки, и сопровождение шло уверенное - сколько раз не запускай - можно быть уверенным, что всю дистанцию мы будем получать данные, пусть и чуть зашумлённые.

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


Здесь виден очень нехороший выброс на 2 метра вверх и вниз, который будь чуточку выше - уже привёл бы к срыву. И в целом, шумы существенно увеличились по сравнению с исходным вариантом. Если раньше ошибки в целочисленном варианте были на 23% выше, чем в исполнении с плавающей точкой, то теперь ошибки выше на 70%.

И ведь это не такие уж громоздкие вычисления - счёт операций пока ещё на сотни, а участков, где происходит округление - и вовсе по пальцам пересчитать! Когда туда добавишь операции, ведущие к составлению матрицы (посчитать 12 частных производных помещённых в матрицу 2х6, потом помножать их на транспонированные, образуя матрицу 6х6, и сложение их всех в итоговую матрицу 6х6), к обновлению кватерниона и вектора, всё станет ещё хуже.

Не думай о младшем разряде свысока! Правильная работа с ним позволяет избежать систематического накопления ошибок в процессе вычислений, иначе ошибки доберутся до следующих разрядов, как в этом анекдоте про РЖД. Так что и округлению банкира не надо так уж удивляться - это один из единственных способов получить полностью несмещённое округление. Может, и его добавлю в итоге, если окажется, что оно обеспечивает заметную прибавку в точности.

Вот чем хорошо разрабатывать свой собственный процессор - там поддержка правильного округления "нативная", хотя всё равно, увы, требует внимания.
Tags: ЖД, ПЛИС, кватернионы-это просто (том 1), математика, программки, работа, странные девайсы
Subscribe

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 19 comments

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…