AOP_Tom2 (1021737), страница 84
Текст из файла (страница 84)
Например, если ставится задача разделить 3 142 на 53, то сначала разделим 314 на 53 и получим 5 в качестве частного и 49 в остатке; затем разделим 492 на 53 и получим 9 и 15 в остатке. Таким образом, окончательно получаем в качестве частного 59 и в остатке 15. Ясно, что эта идея подходит и для общего случая, так что поиски подходящего алгоритма деления сводятся к следующей задаче (рис. 6). Пусть и = (и„в„— 1...и1по)е н и = (и» 1 ... испо)ь — представленные по основанию Ь неотрицательные целые числа, такие, что и/и < Ь.
Найтя алгоритм для определения числа д = (и/и) . Можно заметить, что условие и/и < Ь равносильно условию и/Ь < и, так что (и/Ь) < п. Это просто условие (и„и„1...и,)ь < (п„еи„е ..па)ь. Далее, если записать г = н — дп, искомое число д будет единственным целым числом, таким, что О < г < и. Наиболее простой подход к решению поставленной задачи состоит в том, чтобы высказать какую-нибудь догадку относительно величины 9, основываясь на наиболее значимых разрядах и и и. Не ясно, достаточно ли надежен такой подход, но он заслуживает исследования.
Итак, положим (2) Согласно этой формуле д получается делением двух первых значащих разрядов числа и на первый значащий разрид числа и. Если результат равен Ь или больше Ь, заменяем его на Ь вЂ” 1. Примечательно, что д всегда оказывается очень хорошим приближением к искомому ответу д, если только е„! относительно велико. Прежде чем анализировать степень близости д к д, докажем, что д не может быть слишком малб. Теорема А. д > д (в принятых выше обозначениях). Деказательсп!ве, Так как д < Ь вЂ” 1, теорема, безусловно, верна прн д = 6 — 1. В противном случае имеем д = ((и„Ь+ и„!)/е„!), поэтому де„! > и„Ь+ и„!— е„! + 1.
Отсюда следует, что и — де < и — де„!6" < и„6" + + ив — (и„Ь" + и„!Ь" ! — е„! Ь" ! + Ь" !) = и»-зЬ + ''+ив — Ь +е -!Ь < е -!Ь < "'. Поскольку и — де < е, мы должны получить д > д. 1 Докажем теперь, что на практике д не может быть намного больше, чем д. Предположим, что д > д + 3. Тогда и„Ь+ и„! и„Ь" + и„!6» и и е» е» !6» 1 е ~6» ! е — 6» ! (Случай, когда е = Ь" ', невозможен из-за того, что если е = (100... 0)ы то д = д.) Далее, так как д > (и/е) — 1, то и и и/ 3<д-д< — -+1= — ~, +1, -Ь-- ~ -6-- Поэтому и /е 6» — ! — >2~ „, ) >2(е„! — 1). Таким образом, поскольку Ь вЂ” 4 > д — 3 > д = (и/е) > 2(е„! — 1), то е„! < ~ 6/2).
Это доказывает следующую теорему. Теорема В. Если е„! > )6/2), то д — 2 < д < д. 1 Наиболее важным моментом этой теоремы является то, что постулируемое в теореме выражение не зависит от Ь. Не важно, насколько велико 6! пробное частное д никогда не отличается от истинного более чем на 2. Условие е„! > 16/2) очень похоже на условие нормализации; действительна, оно в точности совпадает с условием нормализации для двоичных компьютеров. Один из простых способов обеспечения достаточно большого значения е„! — умножить оба числа и и е на (Ь/(е„! + 1)). Это не изменит значении и/е, не увеличит количество разрядов в е и, как доказывается в упр.
23, всегда приведет к достаточно большому новому значению е„!. (Другой путь нормализации делимого рассматривается в упр. 28.) Вооружившись теперь всеми этими сведениями, можно разработать требуемый алгоритм деления в столбик (рис. 7). В нем на шаге РЗ используется несколько усовершенствованный способ выбора числа д, гарантирующий, что д = д нли д — 1. На практике этот улучшенный метод выбора числа д почти всегда дает точное решение.
Рнс. т. "длинное" деление. Алгоритм 11 (Деление неотрицательных целых чисел). По данным неотрицательным целым числам и = (и +„ь... иьио)ь и о = (о„ь ... огио)ь, представленным по основанию Ь, в предположении, что о„, ф 0 и н > 1, находим в системе счисления по основанию 6 частное [и/о) = (9 д ь ... до)ь и остаток и шо4 о = (г„ь ... гьго)ь. (Прн и = 1 следует пользоваться более простым алгоритмом из упр.
1б.) 01. [Нормализация.[ Присвоить д ь- [Ь/(о„1+1)). Затем присвоить (и |.„и, + -ь ...иьио)ь значение (и ь„ь ...иьио)ь, умноженное на д. Точно так присвоить (о — ь ... оь но)ь значение (о„ь... оьно)ь, умноженное на ьь'. (Обратите внимание на введение нового разряда и +„слева от и +„ы если И = 1. то все, что необходимо выполнить на этом шаге, — присвоить и +„+- О. На двоичном компьютере может оказаться, что предпочтительнее вместо предлагаемого здесь значения взять в качестве И некоторую степень 2; пцдойдет любое значение Н, приводящее к выполнению неравенства о„ь > [6/2).
См, также упр. 37.) П2. [Начальная установка ь'.[ Присвоить / ь- т. (Цикл по /, который состоит из шагов 02-07, по существу, представлнет собой процесс деления (иьь„... иэ ыи.)ь на (о„ь... оьсо) ь, дающий один разряд частного дэ; см. рис. б.) РЗ. [Вычислить д.) Присвоить д +- [(и .ь„Ь + и +„ь)/о„ь), и пусть г — остаток, (и,+ 6+ иээ„ь) гпобо„ь. Проверить выполнение неравенства 9 = 6 нли дон в > Ьг+ и ь з. Если оно удовлетворяется, то уменьшить д на 1, увеличить г на о ь и повторить эту проверку при г ( 6.
(В ходе проверки обнаруживается, и притом очень быстро, большинство случаев, когда пробное значение д на единицу больше истинного, и исключаются все случаи, когда д больше истинного на два; см. упр. 19 — 21.) Р4. [Умножить и вычесть.) Заменить (иьэниээн-1 иэ)ь на (иь+„иь<ь„ь... иу)ь — Ч(о„ь .
оьно)ь. Этот шаг (аналогичный шагам МЗ вЂ” Мб алгоритма М) состоит из простой операции умножения на одноразрядное число, скомбинированной с вычитанием. Значения разрядов (иуэ„, и;+„ы ..,,и ) всегда дачжны быть положительными; если на этом шаге получен отрицательный результат, то в качестве истинного результата должно остаться (и э„и +„ь... и )ь плюс 6"+, а именно— нэь представление истинного значения в виде дополнения до Ь, причем следует запомнить "заимствование" слева,из старшего разряда. Пб. [Проверка остатка.[ Присвоить ут ь — д. Если результат шага П4 был отрицательным, перейти к шагу П6; в противном случае перейти к шагу 07.
Х16. [Компенсировать сложение.[ (Как показано в упр. 21, ве1юятность того, что данный шаг понадобится, очень мала (порядка 21'Ь). Поэтому до его выполнения следует проанализировать данные.) Уменьшить д на 1 и добавить (Ои„т...етое)ь к (иу+„иуэ„т ...иу+ти1)ь (ПРи этом пРоизойдет пеРенос в разряд, находящийся слева от итч.„, но им следует пренебречь, так как перенос погашается "заимствованием" из того же разряда, произведенным на шаге П4.) ьЬ7. [Цикл по 1.[ Уменьшить 1 на единицу. Если теперь 1 > О, то вернуться к шагу ПЗ. Х18.
[Денормализация.[ Теперь (д ...Отуе)ь есть искомое частное, а для получения искомого остатка достаточно (и„т ... итие)ь разделить на ть. 1 При реализации алгоритма П в виде И1Х-программы нужно обратить внимание на несколько интересных моментов. Программа Р (Деление иеотрицатнельиых целых чисел). Соглашения о начальном состоянии для этой программы аналогичны соглашениям для программы А; г11: — т — и, г12 = 1', г13 ь— э т + 1.
001 01 ЛОЧ ОГРО 099 Р2 ЕИТ2 И 04 О Б7 2 Ч+И М+1 М+1 М+1 М+1 М+1 М+1 М+1 041 РЗ 1РА 049 1РХ 049 РТЧ 044 ТРУ 046 БТА 046 БТХ 047 ЛИР 046 1Н ЫХ 049 1.РА 050 ЛИР 061 ЗН 1РХ 069 РЕСХ 069 1РА 054 4Н БТХ Обб АРР 066 ЛОЧ 067 БТА Обб 1.РА 069 2Н ИО1 060 СИРА 061 Л. 069 За О+И,2(1:Б) О+И-1,2 У+И-1 1Г ОНАТ ИНАТ 2Г ЫИ1 О+И-1,2 4Г ОНАТ 1 ИНАТ ОНАТ Ч+И-1 Р4 ИНАТ ОНАТ Ч+И-2 ИНАТ Р4 ЗВ Е Е Е Е Е Е Е Е М+Е+1 М+Е+1 М+Е+1 Е ят. и ~д, (См. упр.
25.) ТЬ2. Начальная ставенка ', 1 т — нт. Присвоить е,| т — О для удобства выполнения шага 04. ВЗ. ВычиСлить д. тАХ т- ите Ь+ и,+„т. гА +- [гАХ1е Переход, если частное = Ь. д т — гА. Р ь- ит+„Ь 4 и,+„тт — Зия-т = (и +„Ь+и|+ т) шот1тт -т. гХ Ф- Ь вЂ” 1. гА+- и,+ т. (Здесь и л„= ия т.) Уменьшить д на 1. Соответственно установить г. 4 т- гХ. гА т — с+е (Если г окажется > Ь, те Чтм т будет < РЬ,) г т — гА.
Проверитыуе -т < РЬ+ и е -т. Если нет, то 6 слишком велико. Р4. Умножить я сложить. 1 ь — О. (1+1) < — 1'. (Здесь 1 — Ь < гХ < +1.) гАХ ь- — Вс,. Взаимный обмен гА ь+ гХ Добавить вклад от разрядов справа плюс 1. Если сумма < — Ь, то перенос — 1. Прибавить к,+1. Прибавить Ь вЂ” 1, чтобы получить знак "+". Если переполнения нет, то перенос -1. гХ ге перенос + 1. и,+ ь- гА (возможен минус нуль). Повторить для О < 1 < и. Рб. 1? ове «а остатка. Присвоить 93 +- 4. (Здесь гХ = О или 1, так как ь„ж О.) Рб.
Компеися ю ее сложение. Присвоить д„ь- д — 1. 1+- О. (1 81) < — 1. (Этот фрагмент, по существу,— программа А,) 091 2Н АРР а,з 099 АРР У+М,1 098 БТА а,з 094 1ИС1 1 096 1МСЗ 1 096 лиау 18 097 БИТА 1 098 01ИР 2В 099 Р7 РЕС2 1 100 12ММ РЗ 101 Р8 е~кльььз Повторять для т > 1 > О. (См. упр. 26.) ) М+1 М+1 Обратите внимание, как легко реализуются в машине казавшиеся довольно сложными вычисления и выбор вариантов на шаге РЗ.
Отметим также, что программа для выполнения шага 04 аналогична программе М с той лишь оговоркой, что здесь применяются еще и идеи программы 3. Для оценки времени выполнения программы Р следует рассмотреть значения параметров М, Л, Е, К и К', представленных в программе. (Эти параметры не учитывают ситуации, которые могут возникнуть с очень малой вероятностью; например, можно предполагать, что команды в строках программы 048 — аба, 663, 664 068 064 Обб Р4 066 067 Обб 2Н 069 070 071 072 078 074 076 076 077 078 О79 ово Оп 089 ОВВ РБ 084 овб ОВб Рб 087 пвв 089 090 1Н смРх а+М-2,2 За зв ЕИТХ 1 ЕИИ1 И китз а,г Бтх сАВВу 1РАИ У+И,1 ма1 цнйт 31С 6 АРР САВВУ лау *+2 РКСХ 1 АРР Р,З АРР ММ1 лау ь+г ХМСХ 1 БТА а,з ХМС1 1 1ИСЗ 1 01ИР 28 1РА ОНАТ БТА Ц,2 ЛХР РУ РЕСА 1 Бтй ц,г ЕММ1 И китз а,г китА а М+1 М+1 И+1 (М+ 1)(1У+ 1) (М+1)(1У+1) (М+ 1)(Ж+ 1) (М+ 1)(Ж+ 1) (М + 1) (Ю -~- 1) (М + 1) (Ю + 1) К (М + 1)(1У + 1) (М+ 1)(1У+ 1) (М+ 1)(Ж+ 1) К' (М + 1)(Ю + 1) (М + 1)(1У + 1) (М + 1) (1У + 1) (М+ 1)()У+ 1) М+1 М+1 М+1 и фрагмент, соответствующий шагу 06, никогда не выполняются.) Эдесь ЛХ + 1— количество слов в частном, % — количество слов в делителе, Š— число, показывающее, сколько раз д уменьшается на шаге РЗ, К и К' — число установок »разрядов переноса" в ходе выполнения цикла»умножение-вычитание".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
