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