AngularInDepth уходит от Medium. Эта статья, ее обновления и более свежие статьи размещены на новой платформе inDepth.dev

Все мы знакомы с округлением чисел в десятичной системе счисления. Округление в двоичной системе аналогично, но все же может вызвать некоторую путаницу. Самая большая проблема - округление дробей. Например, может быть не сразу очевидно, почему дробь 0.11101 при округлении до 2 знаков после десятичной точки дает целое число 1. В этой статье объясняются общие правила округления двоичных дробей и объясняется, откуда они взялись. Те же правила применяются к округлению двоичных целых чисел.

В соответствии со стандартом IEEE-754 существует пять методов округления, и большинство из них довольно просты. Первые два округляют до ближайшего значения (связывают с четным и связывают от нуля); остальные называются направленными округлениями: к нулю, к положительной бесконечности и к отрицательной бесконечности. Эти правила легче понять на примере десятичной системы счисления:

Направленные округления довольно просты. В этой статье мы подробно рассмотрим округление ‘до ближайшего; связан с правилом четности. Это режим по умолчанию для двоичных чисел с плавающей запятой и рекомендуемый режим по умолчанию для десятичных. И это обычно не так просто понять, как направленные округления.

Общее правило при округлении двоичных дробей до n -го места предписывает проверять цифру, следующую за n -м местом в числе. Если это 0, то число всегда следует округлять в меньшую сторону. Если вместо этого используется цифра 1 и любая из следующих цифр также равна 1, то число следует округлить в большую сторону. Если, однако, все следующие цифры - 0, то должно применяться правило ограничения равенства, и обычно это «связано с четным». Это правило гласит, что мы должны округлить до числа, в котором 0 стоит на n -м месте.

Чтобы продемонстрировать эти правила в действии, давайте округлим некоторые числа до 2 знаков после точки счисления:

  • 0.11001 - округляется до 0.11, поскольку цифра на 3 -м месте равна 0.
  • 0.11101 - округляется до 1,00, поскольку цифра на 3 -м месте равна 1, а следующие цифры 1 (5 -е место)
  • 0,11100 - примените правило «ничьи к четным» и округлите в большую сторону, потому что цифра на 3 -м месте равна 1, а следующие цифры все 0.

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

Варианты округления

Когда мы округляем числа, мы должны выбрать один из двух возможных вариантов: либо округлить до ближайшего числа, которое меньше исходного, либо округлить до ближайшего числа, которое больше. У этих двух чисел не должно быть больше десятичных знаков, чем число, полученное после округления.

Чтобы продемонстрировать, как мы идентифицируем эти числа, округлим десятичное число 0,42385 до 2 знаков. До каких чисел можно округлять? Это легко увидеть, если мы поместим это число в числовую строку вместе с дробными числами, имеющими два знака:

На этой диаграмме показано, что исходное число находится в диапазоне от 0,42 до 0,43. Поскольку 0,42385 = 0,42 + 0,00385, а наше меньшее число - 0,42, мы можем заключить, что для нахождения меньшего числа мы можем просто усечь дробную часть. после второго места . А чтобы найти большее число, мы можем использовать уже определенное меньшее число и увеличить его на единицу ULP, добавив 1 к цифре на последнем месте. Или, если посмотреть под другим углом, это означает, что мы должны прибавить к меньшему числу 0,01, которое равно 1, умноженному на 10, чтобы получить отрицательное значение. степень 2, потому что мы округляем до 2 знаков. Если бы мы округляли до 3 разряда, мы бы взяли меньшее число для 3 разряда и добавили бы 1, умноженное на 10 в отрицательную силу 3.

Мы можем обобщить это правило поиска вариантов округления:

При округлении дробного числа до n знаков сначала найдите меньшее число, отбросив дробную часть после n -го разряда, а затем используйте его, чтобы найти большее число, добавив к это один ULP - 1, умноженный на основание числовой системы в степени n.

Теперь давайте найдем варианты округления двоичного числа 0,11011. Опять же, мы округлим до 2 мест. Если мы будем следовать той же схеме, описанной для десятичных дробей, мы получим 0,11 для меньшего числа, поскольку 0,11011 = 0,11 + 0,00011. Затем мы можем найти большее число, добавив 0,01, которое равно 1, умноженному на 2, к отрицательной степени 2 , потому что мы используем двоичную систему, поэтому основание - 2 и округляем до 2 знаков. Результат этого расчета: 0,11 + 0,01 = 1,00.

Поиск кратчайшего расстояния

Правило округления «округлить до ближайшего» гласит, что мы должны округлить до числа, которое имеет наименьшее отличие от исходного числа. В числовой строке это означает, что расстояние между оригиналом и двумя возможными округленными числами наименьшее. Итак, если мы поместим исходное число и возможные варианты в строку чисел и отметим расстояния как x, нам нужно будет найти, какой из x меньше:

Это довольно просто сделать вычитанием:

Здесь ясно, что x1 меньше, чем x2, и нам следует округлить до 0.11 тогда. Но что, если мы хотим округлить бесконечный двоичный файл? В этом случае вычитание не было бы такой простой операцией. Оказывается, есть гораздо более простой подход.

По сравнению со средним

Другой более простой подход - определить, больше или меньше исходное число, чем среднее между двумя вариантами округления. Давайте посмотрим на эту диаграмму:

Нетрудно сделать вывод, что если число больше среднего, то оно ближе к большему округленному числу, в противном случае оно ближе к меньшему округленному числу.

Так как же найти середину между двумя вариантами округления? Итак, мы знаем, что расстояние между 0.11 и 1,00 равно 0,01. Поэтому нам просто нужно найти половину 0,01 и прибавить ее к меньшему числу. Половина равна 0,001, а при добавлении к меньшему числу получается 0,111 = 0,11 + 0,001. По сути, это эквивалентно добавлению 1 в конец меньшего числа. Вот диаграмма с соответствующими числами, нанесенными на числовую строку:

Теперь осталось только сравнить исходное число со средним:

Посредством побитового сравнения лексикографического порядка становится ясно, что 0,11011 меньше среднего. Таким образом, мы должны округлить до 0.11, и это будет тот же результат, который мы получили при вычислении расстояний.

Привязка к четности

Иногда расстояние между исходным числом и каждым вариантом округления одинаково, поэтому правило «округлить до ближайшего» не может быть применено. Предположим, мы округляем число 0,11011 до 4 знаков после точки счисления. Мы знаем, что нам нужно найти два варианта округления и середину для сравнения. Итак, чтобы найти сначала меньшее число, мы просто обрезаем оставшиеся цифры после 4 -го разряда, что дает нам 0,1101. Теперь мы можем найти середину, добавив 1 в конец меньшего числа, и мы получим 0,11011. И последнее. Давайте найдем большее число, добавив 1 ULP к меньшему - 0,1101 + 0,0001 = 0,1110.

Итак, у нас есть:
- исходное число - 0,11011
- число, которое нужно округлить до - 0,1101
- число, которое нужно округлить до - 0.1110
- среднее число между вариантами округления - 0,11011.

Путем побитового сравнения мы видим, что исходное число и середина равны, что показывает, что исходное число находится прямо между двумя вариантами округления. Это как раз та ситуация, когда нам нужно применить вторую часть правила «привязки к четным». Двоичное число считается четным, даже если оно заканчивается на 0, поэтому с учетом наших параметров округления это четное большее число, и правило предписывает округлять до 0.1110.

Вывод общих правил округления

Неужели нам действительно нужно сравнивать цифры во всех местах? Как вы уже догадались из правил, изложенных в начале статьи, в этом нет необходимости. В предыдущем абзаце я показал, что среднее число всегда будет оканчиваться на 1 в позиции n + 1, где n - это количество разрядов, до которых округляется число. Исходное число и середина всегда будут равны до позиции n + 1 - это означает, что с этого места мы должны начинать сравнение чисел и далее.

Итак, общие правила округления, представленные в начале статьи, основаны на сравнении исходного числа и среднего числа между двумя вариантами округления. Я повторю эти правила здесь еще раз:

Общее правило при округлении до n -го места предписывает проверять цифру, следующую за n -м местом в числе. Если это 0, то число всегда следует округлять в меньшую сторону. Если вместо этого используется цифра 1 и любая из следующих цифр также равна 1, то число следует округлить в большую сторону. Если, однако, все последующие цифры - 0, то должно применяться правило ограничения равенства, и обычно это «равенство с четным». Это правило гласит, что мы должны округлить до числа, в котором 0 стоит на n -м месте.

Спасибо за прочтение! Если вам понравилась эта статья, нажмите кнопку хлопка ниже 👏. Это очень много значит для меня и помогает другим людям увидеть историю. Чтобы узнать больше, подпишитесь на меня в Twitter и Medium.