AOP_Tom2 (1021737), страница 85
Текст из файла (страница 85)
Если предположить, что К+ К' приблизительно равно (Л1+1)(ЛХ+1) и что Е приблизительно равно 1ЛХ, можно получить., что общее время выполнения программы приблизительно равно ЗОЛХК + ЗОЯХ + 89ЛХ + 111 циклов плюс дополнительно 67Л1 + 235ЛХ + 4 циклов, если и' > 1. (В этих расчетах учитывались фрагменты программ из упр. 25 и 26.) При больших ЛХ и Л1 это время только на 7% больше времени, которое потребуется программе М, чтобы перемножить частное и делитель.
Если основание системы счисления 5 сравнительно малб, так что 51 меньше, чем размер машинного слова, процесс деления может быть ускорен за счет того, что исключаются условия попадания значений отдельных разрядов промежуточного результата в интервал [О .. 6) (см.
О. М. Бш1111, ЛХасИ. Сотр. 65 (1996), 157 — 163). Дополнительные комментарии к алгоритму П включены в упражнения в конце этого раздела. При отладке программ реализации арифметических операций многократной точности для проверки результатов выполнения программы деления можно использовать программы умножения и сложения. Для тестирования иногда бывают полезны следующие числа: (д» 1)(Р» Ц 1м+» 1» Гв» + При т с п такие числа записываются по основанию 1 в виде (1 — 1) ...
(1 — 1) (1 — 2) (г — 1) ... (С вЂ” 1) 0 ... О 1, ~в-1 разрядов яз- 1 разрядов »-в» разрядов например (10~ — 1)(10э — 1) = 99899999001. Для программы П необходимо также опробовать некоторые ситуации, когда вступают в действие редко работающие фрагменты программы; некоторые из фрагментов, вероятно, остались бы непроверенными даже после миллиона случайных тестов (см. упр. 22).
Теперь, после ознакомления с принципами работы с числами, представленными в прямом коде, посмотрим, какой подход следует избрать для решении тех же задач в случае, когда используется компьютер с представлением чисел в виде дополнений. Для дополнительного и обратного кодов по основанию 2 в качестве основания 5 лучше всего брать половину размера слова. Таким образом, для 32-битового машинного слова в вышеприведенных алгоритмах использовалось бы основание 5 = 2~'. Знаковый бит всех слов, кроме наиболее значимого слова в представлении с многократной точностью, будет равен нулю, поэтому в ходе выполнения машинных операций умножения и деления аномальных коррекций знака не будет.
Фактически по самой сути представления в виде дополнения все слова, кроме наиболее значимого, рассматриваются как неотрицательные. Например, при 8-битовом слове число, имеющее в дополнительном двоичном коде вид 11011111 1111110 1101011 (в котором знаковый бит указан только для наиболее значимого слова), следует понимать как — 2г~ + (1011111)г 2ы + (1111110)г 2 + (1101011)г. С другой стороны, в некоторых двоичных компьютерах с дополнительным кодом также предусмотрена арифметика без знака. Напрямер, пусть х и у — 32-битовые операнды.
Компьютер может воспринимать их как числа в дополнительном коде в интервале — 2з' < х, у < 2" или как беззнаковые числа в интервале 0 < х, у < 2гг. Если не обращать внимания на переполнение, то 32-битовое число, равное сумме (х+ у) шоб 2зг, будет одинаковым в любом из этих представлений, но если изменить интервал, то в определенных ситуациях может произойти переполнение. Если в компьютере предусмотрена простая операция вычисления бита переноса 1(х+у)/2~~г в беззнаковой интерпретации и выдается 64-битовый результат для беззнаковых 32-битовых целых чисел, то вместо основания 6 = 2з' в алгоритмах для арифметики с высокой точностью можно использовать основание 6 = 2гг. Представление в виде дополнения позволяет проще выполнять сложение чисел со знаком, так как программа для сложения и-разрядных неотрицательных целых чисел может использоваться для сложения произвольных и-разрядных целых чисел. Знак появляется только в первом слове, поэтому менее значимые слова можно складывать независимо от действительного знака числа.
(В случае использования обратного кода для представления числа особое внимание следует обратить на перенос из крайнего слева (старшего) разряда. Он должен быть добавлен к наименее значимому слову и, возможно, передан дальше влево".) Аналогично вычитание чисел со знаком в таком представлении выполняется несколько проще. С другой стороны, кажется, умножение и деление легче всего производить над неотрицательными величинами, предварительно выполнив операции дополняющего преобразования, чтобы оба операнда были неотрицательными.
Можно также при помощи некоторых специальных приемов избежать этих преобразований н работать непосредственно с отрицательными числами в виде дополнений. Нетрудно показать, как это можно было бы осуществить в случае умножения чисел с удвоенной точностью.
Однако при этом необходимо следить, чтобы не было замедления во время выполнения операций во внутренних циклах подпрограмм, когда требуется высокая точность. Обратимся теперь к анализу величины К, появляющейся в программе А, т. е. числа переносов, происходящих при сложении двух п-разрядных чисел. Хотя величина К и не влияет на общее время выполнения программы А, от нее зависит время работы "двойников" программы А, связанных с представлением чисел в виде дополнения. К тому же ее анализ интересен сам по себе как замечательное применение метода производящих функций.
Предположим, что и и о — независимые случайные и-разрядные целые числа, равномерно распределенные в интервале 0 < и, в < Ь". Пусть реь — вероятность того, что при сложении и и и произошло ровно Й переносов и при этом один из переносов произошел в наиболее значимом разряде. Нетрудно видеть, что для всех Эта так иазываеиый "циклический иеремос". — !!риис иерее. Фин Ь+1 Ь-1 Р,ь = О, Р,„,ц„.ц = — Р„, + — Ч„ю Ь-1 Ь+1 Чоь = Аа, 2Ь 2Ь Это следует нз того, что (Ь вЂ” Ц/2Ь есть вероятность того, что и„«+ с„«> Ь, н (Ь+ ц/2Ь есть вероятность того, что и„«+ и„«+ 1 > Ь, где и„~ и 脫— независимые равномерно распределенные в интервале 0 < и„,, п„«с Ь целые числа.
Построим производящие функции Р(2, «) = арпа х «Я(х~ «) = ~Х~ Чп1 з (4) Мв ь,в (3) Отсюда следует, что среднее число переносов, т. е. математическое ожидание вели- чины К, равно (б) Из равенств (3) следуют основные соотношения /Ь+1 Ь вЂ” 1 Р(з, «) = г« ~ — Р(х, «) + — Я(г, «) 2Ь ' 2Ь УЬ вЂ” 1 Ь+1 Ц(г, «) = 1+ «) — Р(х,«) + — Я(г,«) 2Ь ' 2Ь Эти два уравнения легко разрешаются относительно Р(х, «) и Я(г, «). Если положить С(х,«) = Р(х,«)+ Я(х,«) = ~С„(х)«", ч где С„(г) — производящая функция для общего числа переносов при сложении и-разрядных чисел, то получим С(г,«) = (Ь вЂ” х«)/р(х,«), где р(г,«) = Ь вЂ” ф(1+ Ь)(1+ г)«+ г«~.
(5) Заметим, что С(1, «) = 1/(1 — «) в полном соответствии с тем фактом, что С„(ц должно равняться 1 (как сумма вероятностей всех возможных событий). Взяв частные производные от (5) по г, получаем ОС ~, „-««(Ь вЂ” х«)(Ь+ 1 — 2«) ( «) 2р( Ц дгС, „— «з(Ь+ 1 — 2«) «г(Ь х«)(Ь+ 1 2«)г 2р(з,«)з Положим теперь з = 1 и разложим Р(х, «) н Я(з, «) на элементарные дроби: % ~ и 1 1 ~ ~"(')' 2 (,(1 - «)з (Ь - Ц(1 - «) (Ь - Ц (Ь - «) 1 1 1 2 '1,(1 -«)з (Ь- Цз(1 -«) (Ь-Цз(Ь-«) (Ь-Ц(Ь-«)з/ ' а дисперсия равна а (1) + а'.(1) — а'.(1)' 1 1' 2п 2Ь+ 1 2ь+ 2 71~" 1 ~112"~ 4 ~ Ь вЂ” 1 (Ь вЂ” 1)з (Ь вЂ” 1)з ~Ь/ (Ь вЂ” 1)г ~Ь/ / (7) Таким образом, при сделанных допущениях числа переносов несколько меньше, чем -н.
1 г История и библиография. Раннюю историю описанных в этом разделе классических алгоритмов предоставляем читателю в качестве интересной темы для самостоятельного изучения. Здесь же будет прослежена лишь история их внедрения на современных компьютерах. Использование числа 10" в качестве основания системы счисления применительно к умножению больших чисел на калькуляторе обсуждалась Д, Н. Лемером (П.
К. 1еЬгпег) и Дж. Р. Баллантином (Я. Р. Ва!1апбпе) [АММ 30 (1923), 67 — 69]. Арифметика с удвоенной точностью для компьютеров впервые была рассмотрена Дж. фон Нейманом (Я. топ Ь!ешпапп) и Г. Г. Голдстайном (Н. Н. Со16з!!пе) во введении к руководству по программированию, впервые опубликованному в 1947 году [3, топ Хецшапп, Со!!ессеях Игогйз 6, 142-151]. Теоремы А и В, изложенные выше, принадлежат Д. А. Поупу (П.
А. Роре) и М. Л. Стейну (М. 1. 3ге!и) [САСМ 3 (1960), 652-654]. В их статье приведена также библиография более ранних работ, посвященных арифметике с удвоенной точностью. Другие способы выбора пробного частного 9 рассмотрены А. Г. Коксом (А. С. Сох) и Г. А. Лютером (Н. А. ЕцСЬег) в САСМ 4 (1961), 353 [деление на с„~ + 1 вместо г„~], а также М.
Л. Стейном в САСМ 7 (1964), 472 — 474 [деление на с„~ или с„~ + 1 в зависимости от величины сп в]. Е. В. Кришнамуртн (Е. У. Кг1а!шашцггЬу) [САСМ 8 (1965), 179-181] показал, что исследование остатка от деления с однократной точностью позволяет усилить теорему В. Кришнамурти и Нанди (Хаш)!) [САСМ 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}
