Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 83
Текст из файла (страница 83)
А1. э аиовка. 1 с- О. Сбросить индикатор переполиеииа. 6+- О, Если 1 = я, то перейти к шагу АЗ. ~а 3ы ю.ь с я+~. Если переполнения яет, присвоить А с- О. Иначе — присвоить 1с с- 1. Если 1 < я, то перейти к шагу А2. Запомнить последний перенос в ш . $ Время выполнения этой программы равно 10)У + б циклам независимо от числа переносов К. Величина К подробно анализируется в конце этого раздела. Возможны многочисленные модификации алгоритма А, во лишь некоторые из них упоминаются в упражнениях к этому разделу.
Главу, посвященную обобщениям данного алгоритма, можно было бы назвать Разработка схем сложения для цифровой вычислительной машины". Задача вычитания аналогична задаче сложения, но есть и заслуживающие внимания отличия. Алгоритм 8 (Вмчиглание неошрицаглельнмх целых чисел), По данным неотрицательным п-разрядным целым числам (и„с...
исие)ь > (е„с... есее)ы записанным по основанию Ь, этот алгоритм находит неотрицательную разность (ш с ... шсше)ь. 81. [Начальная установка.) Присвоить,г +- О, А с- О. 82. [Вычитание разрядов [ Присвоить ш +- (и1-е +6) шоб Ь и 6 +- [(и1-е +6)16). (Другими словами, 6 присваиваетсл -1 или 0 в зависимости от того, происходит ли заимствование, т.
е. оказывается ли, что и — е1 + 6 < О. Что касается вычисления шу, примем во внимание тот факт, что должно выполняться неравенство -Ь = Π— (Ь вЂ” Ц + (-1) < из — ез + 6 < (Ь вЂ” 1) — О+ 0 < Ь. Следовательно, 0 < из — е1 + й + Ь < 26 и это полагается в описываемой ниже программной реализации,) 01 ЕИМ1 00 ЗОУ 00 1Н ЕИТА О( 112 05 2Н АОО Оо АОО 07 ЯТА ОВ 1ИС1 Оо ЛИОУ 10 ЕИТА 11 11И 12 ЗН НТА И ОР1 О О ЗР О+И,1 У+И, 1 И+И, 1 1 1В 1 2В И+И 1 1 1У+1 — К 1У+ 1- К 1У 1У 1У 1У 1У К К 1 ВЗ.
(Пикл по (.) Увеличить 1 на единицу. Если теперь ь' с и, то вернуться к ьпагу Б2; в противном случае завершить выполнение алгоритма. (Когда выполнение алгоритма завершается, должно получиться А = О; условие А = -1 соответствует единственному случаю, когда (и„-ь... сьпа)ь > (и„-ь ° .. иьно)м что противоречит сделанному раньше предположению; см. упр. 12.) $ При реализации алгоритма в Н12-программе удобнее вместо значения А хранить значение 1+ А, так что на шаге 82 можно вычислить величину из -иу+ (1+ А) + (Ь-1).
(Напомним, что Ь вЂ” размер машинного слова.) Пронллюстрируем алгоритм следующей программой. Программа В (Вмчишание неогярицвтельммк целых чисел), Эта программа ана- логична программе А, но в ней гА ьд 1+А. Как и в других программах этого раздела, в ячейке МН1 хранится константа Ь-1 — максимально допусткмое значение, которое может храниться в машинном слове Н12 (см. программу 4.2.3Р, строки 38-39). Вмчислить вь — е, +А+Ь. Время выполнения этой программы равно 12М+ 3 циклов, что немного больше, чем для программы А.
Читатель, возможно, поинтересуется, не лучше ли было бы разработать одну комбинированную программу для сложения-вычитания вместо двух разных алгоритмов А и Б. Но анализ программ показывает, что в общем случае для реализации этих операций предпочтительнее использовать две разные программы, чтобы внутренний вычислительный цикл выполнялся настолько быстро, насколько это возможно. Наша следующая задача — умножение. Здесь идеи, использованные при востроенни алгоритма А, получают дальнейшее развитие. Алгоритм М (Ульноясение неогпркцательимя цаьмх чисел). По заданным неотрицательным и-разрядным целым числам (и„ь... иьио)ь и (е„ь ...оьсе)ь по основанию Ь этот алгоритм строит их произведение (ш + ь...
шьше)ь (Общепринятый метод умножения при помощи карандаша и бумаги основан на нахождении сначала частичных произведений (и ь...пьио) х е, для О ( ь' < п, а затем — суммы этих произведений, сдвинутых на соответствующее число масштабирующих разрядов. Но на компьютере предпочтительнее выполнять слсвкение параллельно умножению„как это и делытсл в данном алгоритме.) 01 ЕИИ1 ОО ЛОь ОУ 1Н 112 ~Ц НИТА Об 2Н АВВ Об ЯВВ 07 АВВ 00 ЯТА ОО 1ИС1 10 ЛО'ь" 11 ЕИТА 10 21И 10 Н1.Т И ОГВО ВОВЕ 1 В+И,1 7+И, 1 ИН1 И„1 1 1В О 2В 6 1 1 К+1 К Х Х Х Ф Ф Ж Х-К М вЂ” К . Нач ьи а.
ь' +- О. Сбросить иидииаор переполнения. Если ь' = п, завершить выполнение программы. Присвонть А ь- О. (Возможен минус нуль.) ЯО,,ЦИИд~щ 1, у ь- ь'+ 1. Если произошло переполнеияе, то присвоить А +- О. В противном случае присвоить А +- -1, Если у ( и, то вернуться к шагу Я2. (Ошибка, с > и.) $ НЛ 84. нм иа М5 М5 М5 Мб 3 3 3 б 7 6 М1. (Начальная установка.) Присвоить всем параметрам ш ы ьо т ..., ьоо значения "нуль". Присвоить ь' ь- О. (Если не обнулить все параметры в„, и..., шо„ можно получить более общий алгоритм с результатом (шн+ -ь...шо)ь ь-(и„~ ь."мо)ь х(о -ь" оо)ь+(ш ь...шо)ь.
Этот алгоритм умножения и сложения часто используется в цриложенияхе. М2. (Нулевой множитель?) Если от -- О, то присвоить шз+ ь- 0 и перейти к шагу Мб. (Эта проверка может сэкономить время, если достаточно велика вероятность того, что оь равно нулю; в противном случае проверку можно опустить без ущерба для корректности алгоритма.) МЗ. (Начальнал установка ь1) Присвонты ь- О, Й ь- О. м4. [Умножить и сложить,) присвоить сначала ь 4- гн х и + кй+ + ь, а затем— ьоь ь ь- ь пкх1 Ь и Ь +- (т/Ь). (Здесь разряд переноса Ь всегда будет принадле. жать интервалу О < Ь < Ь; см. ниже.) Мб.
(Цикл по 1.) Увеличнты на единипу. Если после этого ь' < т, то вернуться к шагу М4; в противном случае присвоить ву+ ь- Й. МВ. )Цикл по 71) Увеличить т' на единицу. Если после этого 7' < и, то вернуться к шагу М2; в противном случае завершить выполнение алгоритма. $ Работа алгоритма М для спучая, когда Ь = 10, проиллюстрирована в табл. 1, в которой показано состояние вычислительного процесса в начале шагов М5 и Мб.
Доказательство корректности алгоритма М приведено в упр. 14. Два неравенства, О < г ( Ьа 0(н(Ь являются критическими для эффективной реализации этого алгоритма, так как они накладывают ограничения на размер регистра, необходимый для вычислений. Их можно доказать по индукции, так как если в начале шага М4 справедливо неравенство Й < Ь, то иь х о + ьоь 41 + Ь < (Ь вЂ” 1) х (Ь вЂ” 1) + (Ь вЂ” 1) + (Ь вЂ” Ц = Ь вЂ” 1 < Ь Следующая й1Х-программа демонстрирует те моменты, которые нужно учитывать при реализации алгоритма М на компьютере.
Шаг М4 можно было бы Таблица 1 УМНОЖЕНИЕ И4 4 т н1 на Ь О О 4 4 16 О 1 4 05 О 8 4 36 3 0 . 4 Зб О 1 4 8 37 1 1 1 8 17 2 1 9 8 76 3 1 . 8 76 а Его часто натмеают "умноженне с нанонаеннем". — П)нан. нерее. соа ее1 соо О О 6 О 5 6 б 5 б 6 о б 6 7 6 7 7 6 6 7 7 6 запрограммировать проще, если бы на компьютере имелась команда "умножить и сложить" или если бы в нем был аккумулятор удвоенной длины для сложения.
Программа М (Умнажение неотрицапюльных целых чисел). Эта программа аналогична программе А. гП ж з — пг, г12 = 1' — и, г13 ж 1+1, СОМТЕМТБ(САНВЧ) гй й. 01 ЕМТ1 И-1 1 МХ Начальная с евка. 02 1ОЧ ОР10 1 Сбросить индикатор переполнения, 00 БТ2 И 1 М ю,п <-О. 04 РЕС1 1 М 00 31ИИ «-2 М Повторить при пз > гП > О. 00 ЕИИ2 И 1 1+- О. 07 1Н ВВХ Ч+И,2 ?Ч М2. левой множите ? 08 ЛХ2 8Р )Ч Егзги е = О и свонть ю « — О и пе йти М И,2 0 САВНЧ О+И,1 Ч+И,2 б М,З «+2 1 САМУ «+2 1 рн з+ « ре к шагу Мб. 00 ЕИИ1 Н вЂ” Е М3. На«альп тано г. 1 «- О.
10 ЕИТЗ )Ч-г (1+1) -1, 11 ЕМТХ )Ч вЂ” Я А+- О. 18 2Н БТХ ()Ч вЂ” Я)М М4. Умножить и сложить. 10 (.ВА (Ю вЂ” Е)М 11 МО(. ()Ч - Е) А1 гАХ «- к, х;. 10 БЕС (1Ч вЂ” Я)М Произвести взаимную замену содержимого регистров гА +«гХ 16 АВВ (1Ч вЂ” Я)М Прибавить иыо к нижней половине. 17 1ИОЧ (1Ч вЂ” Я)М Переполнение произошло? 10 1МСХ К Если произошло, то разряд переноса, равный 1, занести в верхнюю половину. 10 АВВ (К вЂ” Я)М Прибавить й к нижней половине. 80 ЮИОЧ ()Ч вЂ” Я)М Переполнение произошло? 81 1ИСХ К' Если произошло, то разряд переноса, равный 1, занести в верхнюю половину. йй БТА И.З (М-г)М,, -1 бЬ.
РУ ХМС1 1 (Ю вЂ” «)К «Б.Л~«ь 1 1 '~ 1. 84 1МСЗ 1 (1Ч вЂ” Я)М (1+1) +- (1+1) + 1, йб 11И 2В (А? — Я)М Возврат к шагу М4, если г < гл, гХ = (1/Ь). 06 8Н БТХ И+И+И,2 1Ч Присвоить ю,+, +- А. «исг 1 ««кзыл««~ ( 00 12И 1В ?Ч Повторять до тех пор, пока не станет 1 = н. $ Время выполнения программы М зависит от числа разрядов М множителя и, числа разрядов К множимого о, числа нулей Я в множителе„и числа переносов К и К', возникающих при выполнении сложения в нижней половине произведения в ходе вычисления 1.
Если ограничить значения К и К' разумной (хотя и несколько пессимистической) величиной Аз(?Ч- Е) М, то время выполнения программы составит примерно 28МТЧ+ 4М+ 10)Ч+ 3 — Е(28М+ 3) циклов. Если исключить шаг М2, то время выполнения программы составит 28М)Ч + 4М + 7)Ч + 3 циклов, так что включение этого шага выгодно лишь при условии, что плотность числа нулей в множителе равна Я/)Ч > 31'(28М + 3). Если множители выбираются случайным образом, то следует ожидать, что среднее значение этой плотности будет около 11'б, что очень мало, Поэтому включать шаг М2, вообще говоря, невыгодно, даже если число 6 мало. Рис. б. Цель: быстро определитыу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
