Как делить на простую константу

[spamsink]

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

В отличие от людских голов, в компьютерах целые числа представляются без сохранения знака как отдельного признака, а в так называемом дополнительном коде: скажем, если у нас для записи целых чисел есть 8 цифр, то записать можно числа от 00000000 до 99999999. Половина из них будут представлять неотрицательные значения (от "00000000" до "49999999"), а другая половина - отрицательные (от "99999999" — что значит -1, потому что при прибавлении единицы и сохранении только 8 младших цифр получится ровно 0 — вниз до "50000000", что значит -50000000). Определять, отрицательное ли число, довольно легко: если самая левая цифра - от 5 до 9, то отрицательное. Изменение знака числа делается вычитанием из нуля: смотря справа налево, пока мы видим только нули, они остаются нулями, первая ненулевая цифра заменяется на (10 минус эта цифра), а все цифры левее нее - на (9 минус цифра).

Рассмотрим, как происходит деление на 10 в таком представлении чисел. С положительными всё просто: справа убираем цифру, слева приписываем 0, и готово. С отрицательными этот способ, с заменой приписывания слева 9 вместо 0, работает, но лишь в 10% случаев, для чисел, кратных 10: 99999990 (т.е. -10), деленное на 10, действительно будет 99999999 (т.е. -1). Но столько же получается, если делить 99999999. Мы не хотим, чтобы -1, деленное на 10, равнялось -1, мы хотим, чтобы получался ноль. Для того, чтобы метод работал правильно для всех чисел, нужна поправка: если убранная справа цифра была не 0, то после приписывания слева девятки нужно прибавить 1. Тогда, как и положено, при делении 9999999Х (где Х - от 9 вниз до 1, т.е. чисел от -1 до -9) на 10, будет 99999999+1, т.е. 0.
Казалось бы, все прекрасно. Раз мы умеем делить и положительные, и отрицательные числа на 10, то не составляет труда делить эти же числа на -10, не правда ли? Из математики мы знаем, что a/-b = -a/b, так за чем же дело стало?

Действительно, за чем же?

Comments

[archaicos.livejournal.com]

50000000/99999999?

[ilya-dogolazky.livejournal.com]

FPE, хотя казалось бы --- откуда ж тут F

[archaicos.livejournal.com]

640КБ ведь должно было хватить?

[ilya-dogolazky.livejournal.com]

а что выбрасывается на каком-нить арме например?

[archaicos.livejournal.com]

Если бросается (но не автоматически на ARM/MIPS, насколько я помню, а при помощи явной проверки), то скорее всего то же самое исключение. Я ж про что и говорю: народу было впадлу заводить отдельный сигнал в системе, типа и так сойдёт/всем хватит (ну, почти).

[spamsink]

Это-то да. Я про деление конкретно на -10.

[archaicos.livejournal.com]

50000000/99999990 -> 50000000/00000010 -> 95000000?

[spamsink]

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

[archaicos.livejournal.com]

Я когда что-то подобное делаю, то нередко для тестирования размер слова выбираю 4-8-16 бит, делаю брутфорс и сплю спокойно.

[spamsink]

Конечно, но для младшего товарища приходится объяснять, что если тесты идут, а equivalence checking говорит, что где-то ошибка, то ошибка может быть у него, а не в equivalence checking.