?

Log in

No account? Create an account

Как делить на простую константу - Общество дровосеков Бердичева по изучению Мишны

Apr. 23rd, 2016

12:39 am - Как делить на простую константу

Previous Entry Share Next Entry

Каждый ребенок, знакомящийся с арифметической операцией деления, рано или поздно соображает: для того, чтобы получить частное от целочисленного деления числа на 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, так за чем же дело стало?

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

Tags:

Comments:

[User Picture]
From:archaicos
Date:April 23rd, 2016 09:49 am (UTC)
(Link)
50000000/99999999?
(Reply) (Thread)
[User Picture]
From:ilya_dogolazky
Date:April 23rd, 2016 10:05 am (UTC)
(Link)
FPE, хотя казалось бы --- откуда ж тут F
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:April 23rd, 2016 10:19 am (UTC)
(Link)
640КБ ведь должно было хватить?
(Reply) (Parent) (Thread)
[User Picture]
From:ilya_dogolazky
Date:April 23rd, 2016 10:27 am (UTC)
(Link)
а что выбрасывается на каком-нить арме например?
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:April 23rd, 2016 10:56 am (UTC)
(Link)
Если бросается (но не автоматически на ARM/MIPS, насколько я помню, а при помощи явной проверки), то скорее всего то же самое исключение. Я ж про что и говорю: народу было впадлу заводить отдельный сигнал в системе, типа и так сойдёт/всем хватит (ну, почти).
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:April 23rd, 2016 03:12 pm (UTC)
(Link)
Это-то да. Я про деление конкретно на -10.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:April 24th, 2016 04:43 am (UTC)
(Link)
50000000/99999990 -> 50000000/00000010 -> 95000000?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:April 24th, 2016 04:52 am (UTC)
(Link)
Именно. А все остальные значения делимого дают правильный результат. Впрочем, варьируя размер слова, это можно поймать не только формальными методами, но и случайными тестами.

(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:April 24th, 2016 05:00 am (UTC)
(Link)
Я когда что-то подобное делаю, то нередко для тестирования размер слова выбираю 4-8-16 бит, делаю брутфорс и сплю спокойно.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:April 24th, 2016 05:03 am (UTC)
(Link)
Конечно, но для младшего товарища приходится объяснять, что если тесты идут, а equivalence checking говорит, что где-то ошибка, то ошибка может быть у него, а не в equivalence checking.
(Reply) (Parent) (Thread)