Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 87
Текст из файла (страница 87)
иь ив) ь на е, где ив произволъное число, представляемое с однократной точностью (т. е, О < е < Ь), и получает в результате (ш, ... ич же)ь, Каково время ее выполненияу ь 14. [М22] Приведите формальное доказательство корректности алгоритма М, основываясь на методе индуктивных утверждений, который описан в разделе 1.2.1 (см. упр. 4). 16. [М20] Если необходимо сформировать произведение двух и-разрядных дробных частей чисел (.иь из... и„) ь х (хи ее... в„) ь, а в качестве результата получить только и-разрядное приближение (.мыть... ш )ь, можно при помаши алгоритма М вычислить 2н-разрядный результат, который затем округлить до требуемого приближения. Но на это потребуется вдвое больше вычислительных затрат, чем необходимо для достижения приемлемой точности, так как учет произведения и,еь при с+у' > и+ 2 оказывает лишь незначителъное влияние на резулътат.
Оцените максимальную ошибку, которая может возникнуть, если произведения и,ег при 1+ у' > п + 2 в холе умножения будут полагаться равными нулю вместо того, чтобы вычисляться. ° 16. [20] (Короткое деление.) Постройте алгоритм деления неотрицательного и-разрядного целого числа (и ь... иьио)ь на е, где е — целое число, заданное с однократной точностью (т. е. 0 < е < Ь), получив частное (ш ь ... ичко)ь и остаток г. 1г. [М20] В обозначениях рис. 6 предположим, что е„ь > [Ь/2].
Покажите, что если и„= о Е то должно выполняться либо равенство 9 = Ь вЂ” 1, либо равенство а = Ь вЂ” 2. 16. [М20] В обозначениях рис. 6 покажите, что если д' = [(и„Ь+ и ь)/(е ь + 1)], то д' < д. ь 19. [М21] В обозначениях рис, 6 пусть 9 — некоторое приближение к д и 2 = и Ь + и -ь — 9е -ь Предгюложим, что е,-ь > О. Покажите, что если Ое ь > Ьг+ и„м то д < ф [Указание. Усовервгенствуйте доказательство теоремы А, исследован влияние величины е -ь ] 20. [М22] Используя обозначения и предположения из упр.
19, покажите, что если Ое -э < Ьг+ ие-т то Я = 9 нли 9 9 1. ь 21. [М28] В обозначениях из упр. 19 и 20 покажите, что если еь-ь > [Ь/2] и йи, т < Ьг+и ь, но о ~ 9, то и глод е > (1-2/Ь)е. (Последнее событие происходит с вероятностью, приблизителъно равной 2/Ь, так что «слн Ь есть размер машинного слова, то в алгоритме Р (за крайне редкими исключениями) должно выполняться равенство 9; = ф) ь 22. Щ Приведите прнмер деления четырехразрялного числа на трехразрядное, для которого необходимо включение в алгоритм Р шага Рб, если основание системы счиыения — 10. 23.
[Мйу[ Докажите, что дэя заданных целых чисел и и и, таких, чта 1 < а < Ь, всегда выполняются неравенства [Ь/2) < а«Ь/(и+ 1Ц < (и+ 1) [Ь/(и+ 1Ц < Ь, 24. [М20[ Используя закон распределения нанболее значимых разрядов, описанный в разделе 4.2,4, получите приближенную формулу вероятности того, что б ж 1 в алгоритме Р. (Прн з( ш 1 можно, разумеется, опустить большую часть вычислений на азатах Р1 и Р8.) 25.
«йб«Ншзишите программу для Н12, реалнзующую шаг Р1 алгоритма Р, что необходимо для завершения программы Р. 26. «31[ Напишите программу для Н12, реализующую шаг Р8 алгоритма Р, что необходимо для завершения программы Р. 27. [МЯО[ Докажите, что в начале шага Р8 алгоритма Р ненормализованный остаток (и з... изио)ь всегда является точным кратным б. 23. [Муб«(Л. ЯтоВоба, Язга/е па Яргэсотйк' Елйзгшасз' 9 (1983), 2$-32.) Обозначим а = (а -ь...
иьее)ь для любого целого основания Ь при е з и О. Выполним следующие действия. Х1. Если и з < Ь/2, умножнм э па [(Ь+ 1)/(а з + 1Ц. Обозначим результат этого шага через (а„а„-ь...езео)ь. Х2. Если и = О, присвоим э з- в+ (1/Ь) [Ь(Ь вЂ” е з)/(и„з+ 1Ци, и пусть результатом этога нзага будет (в„и„ь ... эз.е ... )ь. Будем повторять шаг Х2 до тех пор, пока не получим э„~ О. Докажите, что шаг Х2 выполиится не более трех раз и что в конце вычислений всегда будет е„= 1 и э„з ж О.
[Замечание. Если оба числа и и а умножить на указанные выше константы, значение частного и/е не изменится, а делитель примет внд (10а„з... ео.с зэ зе з)ь, Такой вил делитшзя очень удобен, так как в обозначениях алгоритма Р в начале шага РЗ, если (изч„зы из.ь~) = (1, О), в качестве пробного делителя берется д = и1з„или а = 6 — Ц 29. [10[ Докажите или опровергнитеслелующееутверждение: вначале шага Р?алгоритма Р равенство иуз„ш О выполняется всегда.
э 30. [33«В случае ограниченного объема памяти при вмполнении некоторых алгоритмов, аписанпых в этом разделе, для ввода и вывода информации желательна отводить одни и те же ячейки памяти. Можно ли при выполнении алгоритма А или Я хранить числа шиь шы ..., ш„з и из, ..., и„ь или ае, ..., е ь в одних и тех же ячейках памяти? Можно ли допустить, чтобы прн выполнении алгоритма Р значения чэстнага де,..., д„занимали те же ячейки памяти, что и и, ..., и + ? Допустима ли перекрытие ячеек памяти, используемых при выполнении алгоритма М для хранения входных и выходных данных? 31. [33[ Пусть основание системы счисления Ь м 3 н и = (и ьэ-з ...изие)з, а = (и»-з ° эьэе)з — целые числа, заданные в уравновешенней троичной системе счисления (см.
раздел 4.1), причем и„з ф О. Напишите алгоритм деления и на е, вычисляя остаток, абсолютное значение которого ие должна превышать зз[а[. Попробуйте найти алгоритм, достаточно эффективный для аппаратной реализации на компъютере со встроенной уравновешенной троичной арифметикой. 32. [М40[ Предположим, что основание системы Ь = 2з, а числа и и е — комплексные числа, представленные в мнимочетверичиой системе счисления. Постройте несколько алгоритмов деления и на е с возможным вычисленяем остатка и сравните их эффективность. 33.
«М40«Составьте алгоритм лля извлечения квадратного корня, аналогичный алгоритму Р и методу извлечения квадратного корня, который вспользуется при вычисленишс вручную. 34. [40] Разработайте набор машинных подпрограмм для выполнения четырех арифметических операций над произвольными целыми числами без ограниченкй их величины, но с учетом ограничения общего объема оперативной памяти компьютера. (Используйте связное распределение памяти так, чтобы время на поиск места для хранения резулътата совсем ие тратилось.) 35. [е0] Разработайте набор подпрограям для "плавающей арифметики десятикратной точности", используя девятиразрядное представление чисел с плавающей точкой по основанию Ь с избытком О, где Ь равно длине машинного слова, и выделяя для порядка полное слово.
Таким образом, каждое число в формате с плавающей точкой записывается в 10 словах памяти н общее масштабирование выполняется посредством сдвигов машинных слов целиком вместо сдвигов внутри слав.) 36. [Мйб] Поясните, как с высокой точностью вычислить!ай по заданному с соответствующей точностью приближению числа ф, используя только операции сложения и вычитания многократной точности и деления на короткие числа. ь 37. [80] (Ю, Саламин (Е, Яа1аш1п).) Объясните, как в алгоритме П при его реализации на двоичном компьютере запретить нормализацию и денормализацию, не изменяя порядка попыток вычисления разрядов частного, если число Ы представлено па степеням 2. (Как можно на шаге ПЗ вычислить 0, если на шаге В1 не бььта выполнена нормализация?) 38. [М05] Предположим, что и и е — целые числа в интервале 0 < и, в < 2". Предложите способ вычисления среднего геометрического [~/нее+ -') при иомощн О(п) операций сложения, вычитания и сравнения (и+ 2)-битовых чисел.
[Указание. Объедините классические методы умножения и извлечения корней, используя "конвейер".) 39. [85] (Д. Бейли (11, Вайеу), П. Борвейн (Р. Вогпеш) и С, Плуфф (Я. Р)опгге), 199б.) Поясните, как вычислить и-й бит двоичного представления числа к, не зная предыдущях и — 1 бит, используя тождество 1 1 4 2 1 1 ~-'1б" ~85+1 85+4 85+5 81+5) и выполняя О(п!об и) арифметических операций над О(1об и)-битовыми целыми числами. (Полагаем, что двоичные разрклы числа к не содержат слишком длинных строк из нулей нли единиц.) 40. [М84] Иногда возникает необходимость в делении числа и на число в, когда заранее известно, что деление выполнитсв без остатка. Покажите, что если и есть 2п-разрядное число и е является к-разрядным числом, таким, что в шог( е = О, то можно свкономить око- ло 75% объема вычислений в алгоритме П, вычислив сначала половину частного, начиная слева направо, а затем другую половину — справа палево.
ь 41. [М86] Во многих приложениях арифметики с высокой точностью требуются повтор- ные вычисления основания и-разрядного числа м, которое изначально было представлено по основанию Ь. Эти вычисления могут быть ускорены при помощи приема, предложенного Петером Л. Монтгомери (Расее 1.. Мопсбошегу) [Мвгй. Сошр.
44 (1985), 519 — 521]. Он вы- полнял вычисление остатка справа налево вместо общепринятого вытравления вычислений слева направо. а) Для заданных чисел и = х(в .ь — ~ ... к~ во)м ш = (ти„~... ш~ ше)ь и числа м', такого, что шош' шодЬ = 1, покажите. как вычислить и = х(е ~...аггее)м чтобы выполнялось соотношение Ь е щи ш = в шод ш. Ь) Для заданных и-разрядных целых чисел со знаком и, е и ю с [и[, [в[ < ш и заданного ш', как в алгоритме (а), покажите, как вычислить и-разрядное целое число 1, тако», что [г] < ш и Ь" С ш ве (по модулю ш), с) Как алгоритмы (а) н (Ь) упрощают выполнение арифметических операций по модулю шу й = ив+ 128, ш = (((Г/256) + Г)/256), е4.3.2.
Модулярная арифметика Еще один интересный метод выполненкя арифметических действий иад большими целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, чтобы оперировать не непосредственно числом и, а его "остатками" и шорты ипхх(тз, ..., ипюйт„, где ты тз, ..., т„— "модули", не содержащие общих делителей (т. е.
они взаимно просты). Примем для удобства везде в этом разделе следующие обозначения: из — и шоб тз ° и — и той тг (1) н~ = н топ пгы Числа (имнз,...,и„) можно легко вычислить путем деления числа и на простые целые числа иы Важно отметить, что при этом нет никакой потери информации (при условии, что и не очень велико), так как всегда, зная (им из,...,и„), можно восстановить и. Например, если 0 < и < с < 1000, нельзя ппзучить (и шой 7, и той 11, и шой 13), которое равнялось бы (с пхх1 7, с шод 11, е пих1 13). Это следствие китайской теоремы об остатках, рассматриваемой ниже.
Поэтому (нмиз,...,и„) можно рассматривать как новый тип представления в компьютере — "мцдулярное представление" целого числа и". Преимущество модулярного представления заключается в том, что операции сложения, вычитания и умножения выполняются очень просто: (пы...,н,)+(ем...,ог) = ((иг +с1) пкх(ты ..., (и„+е„) шойтг), (ны " нг) — (еы ., е„) = ((иг — сч) пии1 т„..., (и„— е„) шод т„), (нм " ~ иг) х (ом..., сг) = ((н, х сч ) шой т„..., (и, х сг) шой т„) . (3) (3) (4) Для доказательства, к примеру, (4) достаточно показать, что для каждого модуля т1 выполняется равенство ио шод ту = (н шод гну)(о шой т ) шод ту.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
