Компенсировать сложение

Рис. 7. "Длинное" деление.

Алгоритм D {Деление неотрицательных целых чисел). По данным неотрицательным целым числам и = {um+n-i UiUo)b и v = {vn-i. ..viVQ)b, представленным по основанию Ь, в предположении, что v„ i ,1 О и п > 1, находим в системе счисления по основанию Ъ частное \u/v\ = {ЯтЯт-х Чо)ь и остаток и mod v = (r„ i ... Г1Го)ь-(При п = 1 следует пользоваться более простым алгоритмом из упр. 16.)

D1. [Нормализация.] Присвоить d <- \b/{vn-\ +1)J. Затем присвоить {Um+nUm+n-i ... uiUo)b значение {Um+n-i • uiUo)b, умноженное на d. Точно так присвоить {vn-i. viVo)b значение (v„ i.. .viVQ)b, умноженное на d. (Обратите внимание на введение нового разряда и+п слева от Um+n-i, если d = 1, то все, что необходимо выполнить на этом шаге, - присвоить Um+n 0. На двоичном компьютере может оказаться, что предпочтительнее вместо предлагаемого здесь значения взять в качестве d некоторую степень 2; подойдет любое значение d, приводящее к выполнению неравенства v„-i > [b/2\. См. также упр. 37.)

D2. [Начальная установка j.] Присвоить j m. (Цикл по j, который состоит из шагов D2-D7, по существу, представляет собой процесс деления {uj+„ . ..Uj+iUj)b на {vn-i .. Vivo)b, дающий один разряд частного Qj; см. рис. 6.)

D3. [Вычислигь д.] Присвоить q <г- [{uj+„b + Uj+„-i)/v„-i\, и пусть f - остаток, {иj+nb + иj+„-i) mod v„-i. Проверить выполнение неравенства q = b или qvn-2 > bf + Uj+n-2- Если оно удовлетворяется, то уменьшить g на 1, увеличить f на Vn-i и повторить эту проверку при f < Ь. (В ходе проверки обнаруживается, и притом очень быстро, большинство случаев, когда пробное значение q на единицу больше истинного, и исключаются все случаи, когда q больше истинного на два; см. упр. 19-21.)

D4. [Умножить и вычесть.] Заменить (uj+„Uj+„ i. ..Uj)b на

{uj+„Uj+„-i ...Uj)b - q{v„-i.. .viVQ)b.

Этот шаг (аналогичный шагам МЗ-М5 алгоритма М) состоит из простой операции умножения на одноразрядное число, скомбинированной с вычитанием. Значения разрядов (uj+„,Uj+„ i,..., Uj) всегда должны быть положительными; если на этом шаге получен отрицательный результат, то в качестве истинного результата должно остаться {uj+„Uj+„-i ...Uj)b плюс 6"+, а именно -

представление истинного значения в виде дополнения до Ь, причем следует запомнить "заимствование" слева, из старшего разряда.

D5. [Проверка остатка.] Присвоить qj <- q. Если результат шага D4 был отрицательным, перейти к шагу D6; в противном случае перейти к шагу D7.

D6. [Компенсировать сложение.] (Как показано в упр. 21, вероятность того, что данный шаг понадобится, очень мала (порядка 2/Ь). Поэтому до его выполнения следует проанализировать данные.) Уменьшить qj на 1 и добавить (Ог>„ 1... г>1г)о)б к (uj+„Uj. „ i ... Uj+iUj);,. (При этом произойдет перенос в разряд, находяшийся слева от но им следует пренебречь, так как перенос

погашается "заимствованием" из того же разряда, произведенным на шаге D4.)

D7. [Цикл по j.] Уменьшить j на единицу. Если теперь j > О, то вернуться к шагу D3.

D8. [Денормализация.] Теперь {qm 919о)б есть искомое частное, а для получения искомого остатка достаточно {u„-i... щщ)), разделить на d.

При реализации алгоритма D в виде MIX-программы нужно обратить внимание на несколько интересных моментов.

Программа D {Деление неотрицательных целых чисел). Соглашения о начальном состоянии для этой программы аналогичны соглашениям для программы А; гП = г - п, г12 = j, rI3 = i + j.

Обратите внимание, как легко реализуются в машине казавшиеся довольно сложными вычисления и выбор вариантов на шаге D3. Отметим также, что программа для выполнения шага D4 аналогична программе М с той лишь оговоркой, что здесь применяются еще и идеи программы S.

Для оценки времени выполнения программы D следует рассмотреть значения параметров М, N, Е, К и К, представленных в программе. (Эти параметры не учитывают ситуации, которые могут возникнуть с очень малой вероятностью; например, можно предполагать, что команды в строках программы 048-050,063, 064