и фрагмент, соответствующий шагу D6, никогда не выполняются.) Здесь М + 1 - количество слов в частном, 7V - количество слов в делителе, Е - число, показывающее, сколько раз q уменьшается на шаге D3, К и К - число установок "разрядов переноса" в ходе выполнения цикла "умножение-вычитание". Если предположить, что К + К приблизительно равно {N + l)(M+l) и что Е приблизительно равно М, можно получить, что общее время выполнения программы приблизительно равно 30M7V + 30N + 89М + 111 циклов плюс дополнительно 67N + 235М + 4 циклов, если d > 1. (В этих расчетах учитывались фрагменты программ из упр. 25 и 26.) При больших М и N это время только на 7% больше времени, которое потребуется программе М, чтобы перемножить частное и делитель.

Если основание системы счисления Ь сравнительно мало, так что меньше, чем размер машинного слова, процесс деления может быть ускорен за счет того, что исключаются условия попадания значений отдельных разрядов промежуточного результата в интервал [О..Ь) (см. D. М. Smith, Math. Сотр. 65 (1996), 157-163).

Дополнительные комментарии к алгоритму D включены в упражнения в конце этого раздела.

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

{t"" - 1)(Г - 1) = -t-t + l.

При т, <п такие числа записываются по основанию t в виде

it-l) ... it-l) (t-2) {t-l) ... (t-1) 0 ... 0 1,

m-1 разрядов n-m разрядов m-1 разрядов

например (10 - 1)(10* - 1) = 99899999001. Для программы D необходимо также опробовать некоторые ситуации, когда вступают в действие редко работающие фрагменты программы; некоторые из фрагментов, вероятно, остались бы непроверенными даже после миллиона случайных тестов (см. упр. 22).

Теперь, после ознакомления с принципами работы с числами, представленными в прямом коде, посмотрим, какой подход следует избрать для решения тех же задач в случае, когда используется компьютер с представлением чисел в виде дополнений. Для дополнительного и обратного кодов по основанию 2 в качестве основания b лучше всего брать половину размера слова. Таким образом, для 32-битового машинного слова в вышеприведенных алгоритмах использовалось бы основание b = 2. Знаковый бит всех слов, кроме наиболее значимого слова в представлении с многократной точностью, будет равен нулю, поэтому в ходе выполнения машинных операций умножения и деления аномальных коррекций знака не будет. Фактически по самой сути представления в виде дополнения все слова, кроме наиболее значимого, рассматриваются как неотрицательные. Например, при 8-битовом слове число, имеющее в дополнительном двоичном коде вид

11011111 1111110 1101011

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

-21 + (1011111)2 • 2* + (1111110)2 2 + (1101011)2.

С другой стороны, в некоторых двоичных компьютерах с дополнительным кодом также предусмотрена арифметика без знака. Например, пусть х и у - 32-битовые операнды. Компьютер может воспринимать их как числа в дополнительном коде в интервале -2 <х,у< 2 или как беззнаковые числа в интервале О <х,у < 2. Если не обращать внимания на переполнение, то 32-битовое число, равное сумме {х + у) mod 2, будет одинаковым в любом из этих представлений, но если изменить интервал, то в определенных ситуациях может произойти переполнение. Если в компьютере предусмотрена простая операция вычисления бита переноса [{х+у)/2\ в беззнаковой интерпретации и выдается 64-битовый результат для беззнаковых 32-битовых целых чисел, то вместо основания Ь = 2 в алгоритмах для арифметики с высокой точностью можно использовать основание Ь= 2.

Представление в виде дополнения позволяет проще выполнять сложение чисел со знаком, так как программа для сложения п-разрядных неотрицательных целых чисел может использоваться для сложения произвольных п-разрядных целых чисел. Знак появляется только в первом слове, поэтому менее значимые слова можно складывать независимо от действительного знака числа. (В случае использования обратного кода для представления числа особое внимание следует обратить на перенос из крайнего слева (старшего) разряда. Он должен быть добавлен к наименее значимому слову и, возможно, передан дальше влево*.) Аналогично вычитание чисел со знаком в таком представлении вьшолняется несколько проще. С другой стороны, кажется, умножение и деление легче всего производить над неотрицательными величинами, предварительно выполнив операции дополняющего преобразования, чтобы оба операнда были неотрицательными. Можно также при помощи некоторых специальных приемов избежать этих преобразований и работать непосредственно с отрицательными числами в виде дополнений. Нетрудно показать, как это можно было бы осуществить в случае умножения чисел с удвоенной точностью. Однако при этом необходимо следить, чтобы не было замедления во время выполнения операций во внутренних циклах подпрограмм, когда требуется высокая точность.

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

Предположим, что и и v - независимые случайные п-разрядные целые числа, равномерно распределенные в интервале О < u,v < b". Пусть рпк - вероятность того, что при сложении и и v произошло ровно к переносов и при этом один из переносов произошел в наиболее значимом разряде. Нетрудно видеть, что для всех

* Это так называемый "циклический перенос". - Прим. перев.

b+1 b-1 Рок = О, p(„+i)(t+i) = -:rr-PnA + -;;г-Чпк,

lb 20

6-16+1 qok = ook, 4(n+i)k =-Pnk +-2д~Япк-

Это следует из того, что (6 - 1)/26 есть вероятность того, что u„ i + Vn-i > b, и (6 + 1)/26 есть вероятность того, что u„-i + v„-i + 1 > 6, где u„ i и v„-i - независимые равномерно распределенные в интервале О < u„ i, v„-i < b целые числа.

Построим производящие функции

Piz,t)=£p„kzt", Q{z,t) = J24nkZ>t". (4)

к,п к,п

Из равенств (3) следуют основные соотношения

P{z,t) = zt Цlpz,t)+-Q{z,t) ,

Q{z,t) = l + t (Piz,t) + Q{z,t)j .

Эти два уравнения легко разрешаются относительно P{z, t) и <5(г, t). Если положить G{z, t) = P{z, t) + Q{z, t) = Y, Gn{z)t",

где G„{z) -производящая функция для общего числа переносов при сложении п-разрядных чисел, то получим

Giz,t) = {b-zt)/p{z,t), rAep{z,t) = b-{l + b){l + z)t + zt\ (5)

Заметим, что G{l,t) = 1/(1 - t) в полном соответствии с тем фактом, что Gn(l) должно равняться 1 (как сумма вероятностей всех возможных событий). Взяв частные производные от (5) по z, получаем

90 , . .„ t{b-zt){b + l-2t)

9, -20„(z)t -()+ 2piz,ty

\-r"f.un -t4b+l-2t) tHb-zt){b+l-2tr

dz~z" p{z,tY 2p{z,tY

Положим теперь г = 1 и разложим P{z,t) и Q{z,t) на элементарные дроби:

е п(1)<" = 2 ((1 ~ {b-m-t) + (б-1)(б-о)

yG"il)t- = -(--- + + "1

2 V(l-0 (6-1)2(1-0 (6-1)2(6-0 (b-l)(b-Ov

Отсюда следует, что среднее число переносов, т. е. математическое ожидание величины К, равно