Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 84
Текст из файла (страница 84)
Алгоритм М вЂ” не самый быстрый способ умножения, если множители пь и и велики, хотя он имеет преимущество (он прост). Более быстрые, но более сложные методы рассматриваются в разделе 4,3.3; уже при ти = л = 4 можно перемножать числа быстрее, чем при помощи алгоритма М. Последний из алгоритмов, которые рассматриваются в этом разделе, — деление в столбик (пь + и)-разрядного целого числа на и-разрядное целое число. При обычном делении в столбик вручную в процессе вычисления необходимо строить догадки, что требует от вычисляющего определенного искусства. Поэтому необходимо либо совсем исключить этот "творческий процесс" из алгоритма, либо развить некую теорию, позволяющую строго его формализовать. Самый беглый анализ обычного процесса деления в столбик показывает, что вся задача разбивается на более простые шаги, каждый из которых состоит в делении (и+ 1)-разрядного числа и на п-разрядное число и, где О < и/и < Ь.
Остаток г после выполнения каждого шага меньше е, поэтому величину гЬ+(следующий разряд делителя) можно использовать как новое число и на следующем шаге. Например, если ставится задача разделить 3142 на 53, то сначала разделим 314 на 53 и получим 5 в качестве частного и 49 в остатке; затем разделим 492 на 53 и получим 9 и 15 в остатке. Таким образом, окончательно получаем в качестве частного 59 и в остатке 15.
Ясно, что эта идея подходит и для общего случая, так что поиски подходящего алгоритма деления сводятся к следующей задаче (рис. 6). Пусть и = (и„и„,... иьио)ь и е = (и„ь ... иьио)ь — представленные по основанию Ь неотрицательные целые числа, такие, что и/е < Ь. Найти алгоритм для определения числа д = (и/е) .
Можно заметить, что условие и/е < Ь равносильно условию н/Ь < е, так что (н/Ь) < е. Это просто условие (и„и„-ь...иь)ь < (е„ье„-з .ее)ь Далее, если записать г и — йи„искомое число д будет единственным целым числом, таким, что О < г < е. Наиболее простой подход к решению поставленной задачи состоит в том, чтобы высказать какую-нибудь догадку относительно величины д, основываясь на наиболее значимых разрядах и и е. Не ясно, достаточно ли надежен такой подход, но он заслуживает исследования. Итак, положим Согласно этой формуле 9 получается делением двух первых значащих разрядов числа и на первый значащий разряд числа и. Если результат равен Ь или больше Ь, заменяем его на Ь вЂ” 1, Примечательно, что 4 всегда оказывается очень хорошим приближением к искомому ответу д, если только п„~ относительно велико. Прежде чем анализировать степень близости в к я, докажем, что в не может быть слишком малб.
Теорема А. в > о (в принятьгх выше обозначениях). Доказательсгпви. Так как о < 6 — 1, теорема, безусловно, верна при д = 6 — 1. В противном случае имеем д = ~(и„Ь+ и„г)/с„г), поэтому ос„г > и„6+ в„-~— с„~ + 1. Отсюда следует, что и — Ф~ < н — чсь-~6 Ьь+ + ( Ьп+ у-г Ьи-1 ч Ьн-1) = и„зЬ" з+ .. +по — 6" '+с„гЬ" г < иа гЬ" ' < с. Поскольку и — дс < с, мы должны получнты) > о. Ь Докажем теперь, что на практике 4 не может быть намного больше, чем д.
Предположим, что д > й + 3. Тогда и„Ь+и„г и„Ь" +и„гЬ" ' « св-~ с„гЬ"-' с„г6"-' о — 6"-' ' (Случай, когда и = 6" ', невозможен из-за того, что еа~и с = (100... 0)ь, то ч = 1.) Далее, так как й > (н/с) — 1, то н и и / Ь 1 3< д-о < — -+1= — ~ — 1) + 1. -6.— ~ -6-- у и l с — 6"-'1 — >2~ ~, ) >2(с„г — 1). Таким образом, поскольку 6 — 4 > о — 3 > в = (п/и) > 2(е„~ — 1) то с„-г < 16/2) . Это доказывает следующую теорему.
Теорема В. Еслибы„г > 16/2), то4 — 2<о < 4. ! Наиболее важным моментом этой теоремы является то, что постулируемое в теореме выражение не зависят от Ь. Не важно, насколько велико 6: пробное частное ф никогда не отличается от истинного более чем на 2, Условие с„~ > 16/2) очень похоже на условие нормализации; действительно, оно в точности совпадает с условием нормализации для двоичных компьютеров. Один из простых способов обеспечения достаточно большого значения с„г — умножить оба числа и и с на (6/(ся г + 1)). Это не язменит значения п~о, не увеличит количество разрядов в с и, как доказывается в упр.
23, всегда приведет к достаточно большому новому значению е„м (Другой путь нормализации делимого рассматривается в упр, 23.) Вооружившись теперь всеми этими сведениями, можно разработать требуемый алгоритм деления в столбик (рис. 7). В нем на шаге ВЗ используется несколько усовершенствованный способ выбора числа 4, гарантирующий, что д = д или б — 1.
На практике этот улучшенный метод выбора числа 4 почти всегда дает точное решение. Рис. 7. "Длинное" деление. Алгоритм О (Деление неотприцательнмх целых чисел). По данным неотрицательным целым числам и = (е,„+„ь ... иьео)ь и е = (е„ь... еьео)ь, представленным по основанию Ь, в предположении, что е„ь ф 0 и п > 1, находим в системе счисления по основанию Ь частное [и/е) = (о о,„ь... оо)ь и остаток и шоп е = («~ ь °, «ь «о)ь(При и = 1 следует пользоваться более простым алгоритмом из упр.
16.) 111. [Нормализация.[ Присвоить Ы ь- [Ь/(е„1+1Ц. Затем присвоить (и„,+„и,„.»„-ь ° ° . еьео)ь значение (и +„-ь... иьио)ь, умноженное на И. Точно так присвоить (ео-ь ...еьео)ь значение (е„-ь... еьео)ь, умноженное на ьь. (Обратите внимание на введение нового разряда е + слева от и +„ ь; если ь( = 1, то все„ что необходимо выполнить на атом шаге,— присвоить и +„+- О. На двоичном компьютере может оказаться, что предпочтительнее вместо предлагаемого здесь значения взять в качестве И некоторую степень 2; подойдет любое значение И, приводящее к выполнению неравенства е„1 > [Ь/2), См. также упр. ЗУ.) Т»2.
[Начальная установками Присвоить у ь- т. (Цикл по ь', который состоит из шагов 02-П7, по существу, представляет собой процесс деления (е +„... н +ье )» на (е„ь... е, ео)ь, дающий один разряд частного о-; см. рис. 6.) 116. [Вычислить о.] ПРисвоить Д +- [(иьч.оЬ + иу+„-ь)/е„-ь [, и пУсть « — остаток, (из+„Ь+ из+„ь) шобе„ь.
Проверить выполнение неравенства 4 = Ь или де„з > Ь«+ и +„т. Если оно удовлетворяется„то уменьшить ф на 1, увеличить «на е„ь и повторить зту проверку при «< Ь. (В ходе проверки обнаруживается, и притом очень быстро, большинство случаев, когда пробное значение д на единицу больше истинного, и исключаются осе случаи, когда») больше истинного на два; см. Упр, 19-21,) П4.
[Умножить и вычесть.! Заменить (из+низ+„ь ...и,) ь на (от+„ну+ -ь" вз)ь — Ч(е ь ...еьео)ь. Этот шаг (аналогичный шагам МЗ-Мб алгоритма М) состоит из простой операции умножения на одноразрядное число, скомбинированной с вычитанием. Значения разрядов (и„+„,и +„„... „и ) всегда должны быть положительнымн; если на этом шаге получен отрицательный результат, то в качестве истинного резучьтата должно остаться (из+„из+„ь... еу)ь плюс Ь"+~, а именно— представление истинного значения в виде дополнения до Ь, причем следует запомнить изаимствование" слева, из старшего разряда. РБ. (Проверка остатка.) Присвоить Ч ~- Ч Если результат шага Р4 был отрицательным, перейти к шагу Рб; в противном случае перейти к шагу Р7.
Рб. (Компенсировать сложение.) (Как показано в упр. 21, вероятность того, что данный шаг понадобится, очень мала (порядка 2/Ь). Поэтому до его выполнения следует проанализировать данные.) Уменьшить Чу на 1 и добавить (Ои„~...и~ив)э к (п~+„н1+„~...иу+гиэ)м (ПРи этом пРоизойдет пеРенос в разряд, находящийся слева от н +„, но им следует пренебречь, так как перенос погашается "заимствованием" из того же разряда„произведенным на шаге Р4.) РЧ. (Цикл по 7.) Уменьшить у на единицу. Если теперь у > О, то вернуться к шагу РЗ. РН. (Деиормализация.] Теперь (Ч ...Ч~Че)э есть искомое частное, а для получения искомого остатка достаточно (ни э...
игне)э разделить на И. ! При реализации алгоритма П в виде Н11-программы нужно обратить внимание на несколько интересных моментов. Программа Р (Деление исотрицащсльимл цслмк чисел). Соглашения о начальном состоянии для этой программы аналогичны соглашениям для программы А; гП ш 1 — и, г)2 ьз у, г13 гн 1+ у. 001 О1 Л)Ч ОР1.0 ОЯУ О2 ЕМТ2 Н 040 ЗТХ Ч+М М+1 М+1 М+1 М+1 М+1 М+1 М+1 041 ОЗ Ы)А 043 ЬОХ 040 017 044 ЛОЧ Обб ЗТА Обб ЗТХ (Ц7 Л1Р 040 1Н АРХ 040 ЫА ООО ЛП дбу ЗН ЫХ дбй ВЕС Х Обу ЫА 004 4Н ЗТХ Обб аю Обб ЛОЧ 007 ЗТА Обб ЫА ООУ 2Н НШ.
000 СИРА Об1 Л. Обй ЛО О+И,2(1: З) О+М" 1,2 Ч+М-1 1Р ЦНАТ ВНАТ 2Р НН1 О+М-1,2 4Р ОНАТ 1 ННАТ ЯНАТ Ч+М-1 04 ВНАТ ОНАТ Ч+М"2 ВНАТ Р4 ЗВ 111. Лцймалщш1ия. (См. упр. 25.) Р2. Начальная тано кв '. у+- тл. Присвоить и„<- О для удобства выполнения шага 174. И аи ~ли~~ гАХ <- и1+иЬ+ изэ -ь гА < — (гАХ/и -~). Переход, если частное = Ь. ф+- гА. т ь и~+иЬ+ из+и-м Ои -1 (и~+иЬ+ иэ+и- ~ ) шеи ии-! ° гХ+-Ь-1.
гА т- и,+а-~ (Здесь иэ+и = ии-ь) Уменыиить 4 иа 1. Соответственно установить т. Ч с- гХ. гА <- У+ и„-~. (Если У окажется > Ь, то Ои„-т будет < УЬ.) Р+- гА. Проверить фи э < тЬ+ ш.т„ 0,3 Ч+И,1 0,3 1 1 1В 1 2В 1 03 ОУ1 2Н АОВ 098 АОР 098 ЯТА 091 1ИС1 095 ?ИСЗ ОУ6 1ИОЧ ОУ7 ВИТА ОУ8 11ИР ОУУ 07 ОЕС2 100 12ИИ 101 ОЗ М+1 М+1 068 СИРХ 066 10 065 04 ЕМТХ 066 ЕИИХ 067 еитз 068 гн ятх 069 СВАИ 070 ИШ. 071 ЯЫ 078 АРВ 078 1ИОЧ о75 Оесх 075 йЮ 076 А00 077 1ИОЧ 078 ХИСХ 079 зтА ОВО ХИС1 ОМ ХМС3 088 11МР 088 Об (.ЬА 086 Я ТА 085 1ХР 086 Вб ВЕСА ов7 зтА 088 ЕМИ1 ово еитз ово 1н еитА О+И-г,г ЗВ 1 И 0,2 САЯВЧ Ч+М,1 цнйт б саач я+2 1 0,3 МИ1 я+2 1 0,3 1 1 2В ВНАТ Я,г 07 1 й,г И О,г О М+1 М+1 М+1 (м+ ц()ч+ ц (М + Ц(1Ч+ Ц (М+ Ц(Ф+ Ц (М+ Ц()Ч+ Ц (м+ ц()ч+ ц (М+ Ц(1Ч+ Ц (М+ 1)(1Ч+ Ц (М+ Ц(Ф+ Ц (М+ Ц(Ф+ Ц К' (М+ Ц()Ч+ Ц (М + Ц(1Ч + Ц (М+ Ц(Ф+ Ц (М+ Ц(1Ч+ Ц М+1 М+1 М+1 Если иет, то д слишком велика 04.
Умяож гь н сложить. 1 <- О. (1+1) +- 1'. (Здесь 1 — Ь < гХ <+1.) гАХ ь- -фц. Взаимный обмен гА е+ гХ Добавить вклад от разрядов справа плюс 1. Если сумма < -Ь, то перенос -1. Прибавить и,ьз, Прибавить Ь вЂ” 1, чтобы получить знак "+"'. Если оереполнення нет, то перенос -1. гХ ее перенос+1, ац.т +- гА (возможен минус нуль). Повторить для О < 1 < о. 05, П ве ка остатка. Присвоить 91 +- ф (Здесь гХ = О илк 1, так как е О.) 6. омлел ю ее жение. Присвоить 41 +- 4 — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
