Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 85
Текст из файла (страница 85)
1~- О. (1+1) + (Этот фрагмент, по существу,— программа А.) Рьян>' Повторять для гл > 1 > О. (С . Р.гб,) $ Обратите внимание, как легко реализуются в машине казавшиеся довольно сложными вычисления и выбор вариантон на шаге 03. Отметим также, что программа для выполнения шага 04 аналогична программе М с той лишь оговоркой, что здесь применяются еше и идеи программы Я. Для опенки времени выполнения программы 0 следует рассмотреть значения параметров Ав, )Ч, Е, К и К', представленных в программе. (Эти параметры не учитывают ситуапни, которые могут возникнуть с очень малой вероятностьв; например, можно предполагать, что команды в строках программы 046-050, 063„064 и фрагмент, соответствующий шагу Вб, никогда не выполняются.) Здесь М + 1— количество слов в частном, Ю вЂ” количество слов в делителе, Š— число, показывающее, сколько раз д уменьшается иа шаге ВЗ, К и К' — число установок "разрядов переноса" в ходе выполнения цикла "умножение-вычитание".
Если предположить, что К+К' приблизительно равно (%+1)(М+1) и что Е приблизительно равно -'М, можно получить, что общее время выполнения программы приблизительно равно ЗОМБИ + ЗОЖ + 89М + 111 циклов плюс дополнительно 67Ж + 235М + 4 циклов, если И ) 1. (В этих расчетах учитывались фрагменты программ из упр. 25 н 26.) При больших М и Ю это время только на 7% больше времени, которое потребуется программе М, чтобы перемножить частное и делитель. Если основание системы счисления Ь сравнительно малб, так что Ьз меньше, чем размер машинного слова, процесс деления может быть ускорен за счет того, что исключаются условия попадания значений отдельных разрядов промежуточного результата в интервал (О,. Ь) (см.
В. М. Бписп, Май. Сошр. 65 (1996), 157-163). Дополнительные комментарии к алгоритму В включены в упражнения в конце этого раздела. При отладке программ реализации арифметических операций многократной точности для проверки результатов выполнения программы деления можно использовать программы умножения и сложения. Для тестирования иногда бывают полезны следующие числа: (1~в Ц(1и Ц 1т+н 1ь 1т + 1 При т с и такие числа записываются по основанию 1 в виде (à — 1) ...
(1 — 1) (1 — 2) (1 — 1) ... (1 — 1) 0 ... О 1„ юь-1 разрядов т-1 рвзрвдьв например (10з — 1)(10а — 1) = 99899999001. Для программы В необходимо также опробовать некоторые ситуации, когда вступают в действие редко работающие фрагменты программьц некоторые из фрагментов, вероятно, остались бы непроверенныци даже после миллиона случайных тестов (см. упр. 22). Теперь, после ознакомления с принципами работы с числами, представленными в прямом коде, посмотрим, какой подход следует избрать для решения тех же задач в случае, когда используется компьютер с представлением чисел в виде дополнений.
Для дополнительного и обратного кодов по основанию 2 в качестве основания Ь лучше всего брать половину размера слова. Таким образом, для 32-битового машинного слова в вышеприведенных алгоритмах использовалось бы основание Ь = 2з'. Знаковый бит всех слов, кроме наиболее значимого слова в представлении с многократной точностью, будет равен нулю, поэтому в ходе выполнения машинных операций умножения н деления аномальных коррекций знака не будет. Фактически по самой сути представления в виде дополнения все слова, кроме наиболее значимого, рассматриваются как неотрицательные. Например, при 8-битовом слове число, имеющее в дополнительном двоичном коде внд 11011111 111ШО 1101011 (в котором знаковый бит указан только для наиболее значимого слова), следует понимать как -2" + (1б1Ш1), 2" + (1П111б),. 2" + (11б1б13),.
С другой стороны, в некоторых двоичных компьютерах с дополнительным кодом также предусмотрена арифметика без знака. Например, пусть х и у — 32-битовые операнды. Компьютер может воспринимать их как числа в дополнительном коде в интервале -2з' < х, у < 2з' или как беззнаковые числа в интервале 0 < х, у < 2~а. Если не обращать внимания на переполнение, то 32-битовое число, равное сумме (х+ у) щи 2зз, будет одинаковым в любом из этих представлений. но если изменить интервал, то в определенных ситуациях может произойти переполнение. Если в компьютере предусмотрена простая операция вычисления бита переноса ((х+р)/2зз) в беззнаковой интерпретации и выдается 64-бктовый результат для беззнаковых 32-битовых целых чисел, то вместо основания Ь = 2з1 в алгоритмах для арифметики с высокой точностью можно использовать основание Ь = 2ет.
Представление в виде дополнения позволяет проще выполнять сложение чисел со знаком, так как программа для сложения п-разрядных неотрицательных целых чисел может использоваться для сложения произвольных и-разрядных целых чисел. Знак появляется только в первом слове, поэтому менее значимые слова можно складывать независимо от действительного знака числа. (В случае использования обратного кода для представления числа особое внимание следует обратить на перенос из крайнего слева (старшего) разряда. Он должен быть добавлен к наименее значимому слову и, возможно, передан дальше влево*.) Аналогично вычитание чисел со знаком в таком представлении выполняется несколько проще.
С другой стороны, кажется., умножение и деление легче всего производить над неотрицательными величинами, предварительно выполнив операции дополняющего преобразования, чтобы оба операнда были неотрицательными. Можно также при помощи некоторых специальных приемов избежать этих преобразований и работать непосредственно с отрицательными числами в виде дополнений. Нетрудно показать, квк это можно было бы осуществить в случае умнонсения чисел с удвоенной точностью. Однако при этом необходимо следить, чтобы не было замедления во время выполнения операций во внутренних циклах подпрограмм„когда требуетгя высокая точность.
Обратимся теперь к анализу величины К, появляющейся в программе А, т. е. числа переносоа, происходящих при сложении двух п-разрядных чиеел. Хотя велкчина К и не влияет на общее время выполнения программы А, от нее зависит время работы "двойников" программы А, связанных с представлением чисел в виде дополнения. К тому же ее анализ интересен сам по себе как замечательное применение метода производящих функций.
Предположим, что и и в — независимые случайные и-разрядные целые числа, РавномеРно РаспРеделенные в интеРвале 0 < и,в < Ьк. ПУсть Рка — веРоЯтность того, что при сложении и и в произошло ровно )с переносов и при этом один нз переносов произошел в наиболее значимом разряде. Нетрудно видеть, что для всех " Это так иазыеаеимй "циклический перенос". — Прим.
иерее. Ь+1 ров — О, р~„ч.гць~ц - — рве + — д„ы (з) Ь-1 Ь+1 йвэ = бн„ Ч(э+цэ = рМ + Чаю 2Ь" 2Ь"' это следует из того, что (ь — 1)/2ь есть вероятность того, что и„с + е„с > ь, и (Ь + 1)С'2Ь есть вероятность того, что и„~ + о„~ + 1 > Ь, где нэ с и е„с— независимые равномерно распределенные в интервале 0 < и„м в„~ < Ь целые числа. Построим производящие функции Р(С,С) = Ч~~ р„ьз С, ®(С,С) — ~~~ о„ьг С . (4) Й„» ив Из равенств (3) следуют основные соотношения УЬ+1 Ь-1 Р(С,С) = вг (( — Р(з,С)+ — Я(С,С) 1, 2Ь * 2Ь /Ь вЂ” 1 Ь+1 Ю(з,с) =1+с ~ — Р(с,с)+ — Щз,с)1) . 2Ь ' 2Ь Эти два уравнения легко разрешаются относительно Р(з, С) и 9(з, С). Если положить О(з,с) = Р(с,с) + Фс,с) = ') „О.(з)с", где С„(з) — производящая функция для общего числа переносов прн сложении и-разрядных чисел, то получим С(с, С) = (Ь - сС)/р(х, С), где р(х, С) = Ь вЂ” $(1+ Ь)(1+ з)С+ згт.
(Ь) Заметим, что С(1,С) = 1/(1- С) в полном соответствии с тем фактом, что 0„(1) должно равняться 1 (как сумма вероятностей всех возможных событий). Взяв частные производные от (б) по з, получаем Д6' ~ , „ -С С(Ь вЂ” зС)(Ь + 1 — 2С) д,ф с-' " р(з, С) 2р(з, С) з д'а „„-С'(Ь+1-21) Сз(Ь- зС)(Ь+1-2С)' + 2р(з С)з Положим теперь з = 1 и разложим Р(з, С) н СС(з„С) на элементарные дроби: п 1 1 2 т(1 — С)т (Ь-1)(1-С) (Ь-1)(Ь-С) % 'О~ (1)Сп С2 ~' 1 1 2 1, (1 — С)з (Ь вЂ” 1)т(1 — С) (Ь вЂ” 1)з(Ь вЂ” С) (Ь вЂ” 1)(Ь вЂ” С)т ~~ С"„'(1) С" — — + + Отсюда следует, что среднее число переносов, т.
е. математическое ожидание величины К, равно а дисперсия равна С'„'(1) + С'„(1) — С'„(1) (7) Таким образом, при сделанных допущениях число переносов несколько меньше, чем -и. 1 История н библиография. Раннюю историю описанных в этом разделе классических алгоритмов предоставляем читателю в качестве интересной темы для самостоятельного изучения. Здесь же будет прослежена лишь история их внедрения на современных компьютерах. Использование числа 10" в качестве основания системы счисления применительно к умножению больших чисел на калькуляторе обсуждалась Д. Н. Лемером (О.
Х. 1еЬпег) и Дж. Р. Баллантином (1. Р. Вайалйпе) (АММ 30 (1923)„67-69]. Арифметика с удвоенной точностью для компьютеров впервые была рассмотрена Дж. фон Неймалом (Л. тов Хешпапп) и Г. Г. Голдстайном (Н, Н. СоЫятше) во введении к руководству по программированию, впервые опубликованному в 1947 году (3. топ Хецшапп, Со))есгеб Иог)сэ 5, 142-15Ц.
Теоремы А и В, изложенные выше, принадлежат Д. А. Поупу (О. А. Роре) и М. Л. Стейну (М. Ь. Все(п) ]САСМ 3 (1960), 652-654]. В их статье приведена также библиография более ранних работ, посвященных арифметике с удвоенной точностью. Другие способы выбора пробного частного 9 рассмотрены А. Г.
Коксом (А. С. Сох) и Г. А. Лютером (Н. А. Ьцгпег) в САСМ 4 (1961), 353 (деление на е„г + 1 вместо е„д], а также М. Л. Стейном в САСМ 7 (1964), 472-474 (деление на е„~ нли и„~ + 1 в зависимости от величины еь в]. Е. В. Кришнамурти (Е. Ч. Кг)вЬпашштйу) (САСМ 8 (1965), 179-18Ц показал, что исследование остатка от деления с однократной точностью позволяет усилить теорему В.
Кришнамурти и Нанди (Келий) (САСМ 10 (1967), 809-813] предложили способ замены нормализации и денормализации в алгоритме П вычислением 9, которое базируется па анализе нескольких ведущих разрядов операндов. Интересный анализ оригинального алгоритма Поупа и Стейна выполнили Г. Э. Коллинз (С. Е. Со)!ше) и Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
