запрограммировать проще, если бы на компьютере имелась команда "умножить и сложить" или если бы в нем был аккумулятор удвоенной длины для сложения.

Программа М {Умножение неотрицательных целых чисел). Эта программа аналогична программе А. гИ =г-т, г12 = j - п, г13 = г" + j, CONTENTS (CARRY) = к.

Ml. Начальная усталовка. Сбросить индикатор переполнения, urii <- 0.

Повторить при m > гП > 0. j <-0.

М2. Нулевой множитель? Если Vj = О, присвоить Wj+m <г-0 и перейти

к шагу Мб. МЗ. Начальная установка г. i <- 0.

{i + j) <- j-k<-0.

M4. Умножить и сложить. г АХ +-u,xvj.

Произвести взаимную замену содержимого

регистров гА гХ Прибавить w,+j к нижней половине. Переполнение произошло? Если произошло, то разряд переноса, равный 1,

занести в верхнюю половину. Прибавить к к нижней половине. Переполнение произошло? Если произошло, то разряд переноса, равный 1,

занести в верхнюю половину. Wt+j <- t mod 6. М5. Цикл по i. г <- г + 1. {i+j){i + j) + l.

Возврат к шагу М4, если г < т, гХ = [t/bj.

Присвоить Wj+m <- к.

Мб. Цикл по j. j j + 1. Повторять до тех пор, пока не станет j = п.

Время выполнения программы М зависит от числа разрядов М множителя и, числа разрядов N множимого v, числа нулей Z в множителе, и числа переносов К и К, возникающих при выполнении сложения в нижней половине произведения в ходе вычисления t. Если ограничить значения К и К разумной (хотя и несколько пессимистической) величиной i(iV-Z)M, то время выполнения программы составит примерно 28MN + 4М + 10N + 3 - Z(28M + 3) циклов. Если исключить шаг М2, то время выполнения программы составит 28MN + 4М + 7N + 3 циклов, так что включение этого шага выгодно лишь при условии, что плотность числа нулей в множителе равна Z/N > 3/(28М + 3). Если множители выбираются случайным образом, то следует ожидать, что среднее значение этой плотности будет около 1/6, что очень мало. Поэтому включать шаг М2, вообще говоря, невыгодно, даже если число 6 мало.

Рис. 6. Цель: быстро определить q.

Vn-l . .ViVo)UnUn-l ...UiUo

<-qv-¥

Алгоритм М - не самый быстрый способ умножения, если множители тип велики, хотя он имеет преимущество (он прост). Более быстрые, но более сложные методы рассматриваются в разделе 4.3.3; уже при т = п = 4 можно перемножать числа быстрее, чем при помощи алгоритма М.

Последний из алгоритмов, которые рассматриваются в этом разделе,-деление в столбик (т + п)-разрядного целого числа на п-разрядное целое число. При обычном делении в столбик вручную в процессе вычисления необходимо строить догадки, что требует от вычисляющего определенного искусства. Поэтому необходимо либо совсем исключить этот "творческий процесс" из алгоритма, либо развить некую теорию, позволяющую строго его формализовать.

Самый беглый анализ обычного процесса деления в столбик показывает, что вся задача разбивается на более простые шаги, каждый из которых состоит в делении (п -I- 1)-разрядного числа и на п-разрядное число v, где О <u/v < Ь. Остаток г после выполнения каждого шага меньше v, поэтому величину гЬ-1-(следующий разряд делителя) можно использовать как новое число и на следующем шаге. Например, если ставится задача разделить 3142 на 53, то сначала разделим 314 на 53 и получим 5 в качестве частного и 49 в остатке; затем разделим 492 на 53 и получим 9 и 15 в остатке. Таким образом, окончательно получаем в качестве частного 59 и в остатке 15. Ясно, что эта идея подходит и для общего случая, так что поиски подходящего алгоритма деления сводятся к следующей задаче (рис. 6).

Пусть и = (unUn-i UiUo)b и V = {vn-i viVo)b -представленные по основанию b неотрицательные целые числа, такие, что u/v < b. Найти алгоритм для определения числа q = [u/v\.

Можно заметить, что условие u/v < b равносильно условию и/Ь < v, так что [и/Ь\ < V. Это просто условие (u„«„ i.. .ui)6 < {vn-iVn-2 vo)b- Далее, если записать г = u - qv, искомое число q будет единственным целым числом, таким, что 0<г <v.

Наиболее простой подход к решению поставленной задачи состоит в том, чтобы высказать какую-нибудь догадку относительно величины q, основываясь на наиболее значимых разрядах и и v. Не ясно, достаточно ли надежен такой подход, но он заслуживает исследования. Итак, положим

. / U„b + Un-1 , Л а = mm I - , о - 1 I .

Согласно этой формуле q получается делением двух первых значащих разрядов числа и на первый значащий разряд числа v. Если результат равен b или больше Ь, заменяем его на 6 - 1.

Примечательно, что q всегда оказывается очень хорошим приближением к искомому ответу q, если только Vn-i относительно велико. Прежде чем анализировать степень близости q к q, докажем, что q не может быть слишком мало.

Теорема А. q>q (в принятых выше обозначениях).

Доказательство. Так как q < Ь - 1, теорема, безусловно, верна при q = b - 1. В противном случае имеем q = [(и„Ь-Ь u„ i)/j;„ ij, поэтому qvn-i > u„b + Un-i - v„-i + 1. Отсюда следует, что

u-qv <и- qv„-ib"~

< u„b" + + (u„b" + Un-ib"- - v„ ib"- +

= u„ 2b"-2 + • • • -Ь Uo - Ь"" + vn-ib"- < v„ ib"-i < V.

Поскольку и - qv <v, мы должны получить q>q.

Докажем теперь, что на практике q не может быть намного больше, чем q. Предположим, что q>q + 3. Тогда

и„Ь -Ь u„ i и„Ь" + Un-ib"- " "

9<-7.-=----<

(Случай, когда v = b"~, невозможен из-за того, что если v = (100... 0)ь, то q = q.) Далее, так как q > (u/v) - 1, то

3<-,< - + i = !f-) + i.

Поэтому

Таким образом, поскольку b-4>q-3>q = [u/vj > 2(v„ i - 1), то v„ i < [b/2J-Это доказывает следующую теорему.

Теорема В. Если v„-i > [Ь/2\, то q - 2 < q < q.

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

Условие Vn-i > [b/-2\ очень похоже на условие нормализации; действительно, оно в точности совпадает с условием нормализации для двоичных компьютеров. Один из простых способов обеспечения достаточно большого значения v„ i -умножить оба числа и и и на [b/{vn-i + 1)J. Это не изменит значения u/v, не увеличит количество разрядов в и и, как доказывается в упр. 23, всегда приведет к достаточно большому новому значению Vn-i- (Другой путь нормализации делимого рассматривается в упр. 28.)

Вооружившись теперь всеми этими сведениями, можно разработать требуемый алгоритм деления в столбик (рис. 7). В нем на шаге D3 используется несколько усовершенствованный способ выбора числа q, гарантирующий, что q = q или q - I. На практике этот улучшенный метод выбора числа q почти всегда дает точное решение.