AOP_Tom2 (1021737), страница 87
Текст из файла (страница 87)
[21] Алгоритм А выполняет сложение двух вводимых чисел, двигаясь справа налево, но иногда данные более доступны для считывания слева направо. Разработайте алгоритм, который выдает тот же ответ, что и алгоритм А, но порождает разряды результата слева направо и, если происходит перенос, делающий предыдущее значение неверным, возвращается назад, чтобы изменить предыдущее значение. [Замечание. В ранних индусских и арабских манускриптах, посвященных сложению слева направо, используется именно такой способ сложения. Вероятно, причиной тому послужила ориентация алгоритма А на выполнение операций слева направо на абаках.
Алгоритм сложения справа налево стал логическим продолжением этого алгоритма благодаря работам аль-Уклидиси, возможно, потому, что арабы пишут справа налево.] В. [йй] Разработайте алгоритм, который выполняет сложение слева направо (как в упр. 5), но никогда не запоминает разряд результата, пока существует возможность его изменения из-за последующих переносов.
Уже занесенные значения результата не должны изменяться после запоминания очередного значения любого разряда. [Указание. Следите за количеством последовательных разрядов (Ь вЂ” 1), которые еще не хранятся в результате.) Алгоритм такого вида удобен, например, в ситуации, если вводимые и выводимые числа считываются и записываются на магнитную ленту или если они появляются в простом линейном списке. 7. [Мйб] Определите среднее число случаев, когда выполнение алгоритма иэ упр.
5 приведет к необходимости возврата при переносе и изменению Ь разрядов частичного ответа для Й = 1, 2, ..., и. (Предполагается, что оба входных числа имеют независимые и равномерные распределения на интервале 0 и Ь" — 1.) В. [Мйб] Разработайте программу для н1Х, реалиэуюшую алгоритм из упр. 5, и определите среднее время ее работы, исходя из ожидаемого числа переносов, которое подсчитано в тексте. 9. [э1] Обобщите алгоритм А так, чтобы получившийся алгоритм складывал два и-разрядных числа в системе счисления со смешанным осноеанпем Ьэ, Ьм ... (справа налево). Таким образом, наименее значимый разряд расположен в интервале от 0 до Ьг — 1 и т.
д. (см. формулу 4.1-(9)). 10. (12] Будет ли правильно работать программа В, если поменять местами команды в строках Об н О?, а также в строках 05 и Об? 11. (10] Разработайте алгоритм сравнения двух неотрицательных и-разрядных целых чисел и = (и г ...игио)ь и о = (и г...о|се)ь, который определяет, какое из неравенств, и < о,и = и или и > о, выполняется. 12. [16] В алгоритме 9 предполагается, что заранее известно, какой из двух исходных операндов больше. Даже если информация отсутствует, все равно можно начать и так или иначе выполнить вычитание, но при зтам обнаружится, что лишнее "заимствование" сохранилось до самого конца алгоритлга. Постройте другой алгоритм, в котором можно было бы использовать (еглн в конце работы алгоритма Я имеется "заимствование" ) дополнение (ш -ь шгшо)ь и поэтому вычислять абсолютное значение разности между и и е.
13. (21] Разработайте программу для 811, которая умножает (и„г .. иьио)ь на и, где ив произвольное число, представляемое с однократной точностью (т. е. 0 < о < Ь), и получает в результате (ш ... шгюо)ь Каково время ее выполнения? ь 14. [М22] Приведите формальное доказательство корректности алгоритма М, основываясь на методе индуктивных утверждений, который описан в разделе 1.2.1 (см.
упр, 4). 18. [М20] Если необходимо сформировать произведение двух и-разрядных дробных частей чисел (.иг иг... и„) ь х (.иг иг, . о„) ь, а в качества результата получить только и-разрядное приближение (.геьиг ... ш„)ь, можно при помощи алгоритма М вычислить 2п-разрядный результат, который затем округлить до требуемого приближения.
Но на это потребуется вдвое больше вычислительных затрат, чем необходимо для достижения приемлемой точности, так как учет произведения и;а, при г'+1' > и+ 2 оказывает лишь незначительное влияние на результат. Оцените максимальную ошибкь, которая может возникнуть, если произведения и,и, при г + 1 > и + 2 в ходе умножения будут полагаться равными нулю вместо того, чтобы вычисляться.
° 18. [20] (Коропькое деление.) Постройте алгоритм деления неотрицательного и-разрядного целога числа (и г ...иггье)ь на е, где о — целое чигло, заданное с однократной точностью (т. е. 0 < о < Ь), получив частное (ш„ь... шгше)ь н остаток г. 17, (М20] В обозначениях рис, б предположим, чта о„ь > (Ь/2] Покажите, что если и„= и (, то должно выполняться либо равенство д = Ь вЂ” 1, либо равенство д = Ь вЂ” 2. 18. [М20] В обозначениях рис. б покажите, что если д' = ((и„Ь + и„— г)/(о„-г + 1)], то д' < д.
° 19. (М21] В обозначениях рис, б пусть д — некоторое приближение к д и б = и„Ь + и„-ь — да„-ь Предположим, что е г > О. Покажите, что если до„г > Ьг + и„г, то д < д. (Указание. Усовершенствуйте доказательство теоремы А, исследован влияние величины о„-г ] 20. (М22] Используя обозначения и предположения нз упр. 19, покажите, что если до г < Ьг + и — г, та д = д илн д = д — 1. ь 21. (М22] В обозначениях из упр.
19 и 20 покажите, что если о г > (Ь/2] н ди„-г < Ьг+и г, но д ~ д, то и шаг) а > (1 — 2/Ь)о. (Последнее событие происходит с вероятностью, приблизительно равной 2/Ь, так что если Ь есть размер машинного слова, то в алгоритме П (за крайне редкими исключениями) должно выполняться равенство д, = д.) ь 22. [24] Приведите пример деления четырехразрядного числа на трехраэрядное, для которого необходимо включение в алгоритм П шага Пб, если основание системы счисления — 10. 23. [МЯЯ] Докажите, чта для заданных целых чисел о и и, таких, чта 1 < и < Ь, всегда выполняются неравенства [Ь/2] < о[Ь/(о+ 1)] < (а+ 1) [6/(и+ 1)] < 6.
24. [МЯО] Используя закан распределения наиболее значимых разрядов, описанный в разделе 4.2.4, получите приближенную формулу вероятности того, что 4 = 1 в алгоритме Р. (При 4 = 1 можно, разумеется, опустить большую часть вычислений на шагах Р1 и Р8.) 25. [28] Напишите программу для 81Х, реализующую шаг Р1 алгоритма Р, что необходимо для завершения праграььмы Р.
28. [81] Напишите программу для Н1Х, реализующую шаг Р8 алгоритма Р, что необходимо для завершения программы Р. 27. [МЯО] Докажите, что в начале шага Р8 алгоритма Р ненормализованный остаток (и„-ь... иь ио)ь всегда является точным кратным ь?. 28. [Мой] (А. БтоЬас(а, Бого/е па Хргвсотап? 1п/оггпас? 9 (1983), 25-32.) Обозначим о = (и -ь ...аьио)ь для любого целого основания Ь при и ь ф О. Выполним следующие действия.
?Ь?1. Если и„ь < Ь/2, Умнажим о на [(6+ 1)/(о„ь + 1)]. Обозначим РезУльтат этого шага через (и о -ь. оьоо)ь. ?х?2. Если о„= О, присвоим о+- и+(1/Ь) [Ь(Ь вЂ” и„ь)/(о„ь+ 1)]а, и пусть результатом этого шага будет (о„о ь... вол ... )ь. Будем повторять шаг Н2 до тех пор> пока не получим с ?Ь О, Докажите, что шаг 92 выполнится не более трех раз и что в конце вычиглений всегда будет о„= 1 и и„г = О. [Замечание. Если оба числа и и о умножить на указанные выше константы, значение частного и/о не изменится, а делитель примет вид (10о„о...
ао.о ьо оо з)ь. Такой вид делителя очень удобен, так как в обозначениях алгоритма Р в начале шага РЗ, если (и,+„+и и„~. ) = (1, О), в качестве пробного делителя берется 8 = и„.ь„или д = Ь вЂ” Ц 29. [15] Докажите или опровергните следующее утверждение: в начале шага Р? алгоритма Р равенство иое„= О выполняется всегда. ь ЗО. [88] В случае ограниченного объема памяти при выполнении некоторых алгоритмов, описанных в этом разделе, ддя ввода и вывода информации желательно отводить одни и те же ячейки памяти. Можно ли при выполнении алгоритма А или Я хранить числа шо, том ..., ш„-ь и ио,, и„ь или ао, ..., и„ь в одних и тех же ячейках памяти? Можно ли допустить, чтобы при выполнении алгоритма Р значения частного уо,..., дм занимали те же ячейки памяти, что и и, ..., и~+ ? Допустимо ли перекрытие ячеек памяти, используемых при выполнении алгоритма М для хранения входных и выходных данных? 31.
[88] Пусть основание системы счисления Ь = 3 и и = (и + ь... и1ио)з, о = (а -ь... оьоо)о — целые числа, заданные в уравновешенной троичной системе счисления (гм. раздел 4.1), причем о„ь ф О Напишите алгоритм деления и на о, вычисляя остаток, абсолютное значение которого не должно превышать -']о]. Попробуйте найти алгоритм, достаточно эффективный для аппаратной реализации иа компьютере со встроенной уравновешенной троичной арифметикой.
32. [6440] Предположим, что основание системы Ь = 2ь, а числа и и а — комплексные числа, представленные в мнимочетверичной системе счисления. Погтройте нескачько алгоритмов деления и на а с возможным вычислением остатка и сравните их эффективность. 33. [М40] Составьте алгоритм для извлечения квадратного корня, аналогичный алгоритму Р и методу извлечения квадратного корня, который испатьзуется при вычислениях вручную.
34. [40] Разработайте набор машинных подпрограмм для выполнения четырех арифметических операций над произвольными целыми числами без ограничений их величины, но с учетом ограничения общего объема оперативной памяти компьютера. (Используйте связное распределение памяти так, чтобы время на поиск места для хрюьення результата совсем не тратилось.) 35. [40] Разработайте набор подпрограмм для "плавающей арифметики десятикратной точности", используя девятирвзрядное представление чисел с плавающей точкой по основанию Ь с избытком О, где Ь равно длине машинного слова, и выделяя для порядка полное глава.
Таким образом, каждое число в формате с плавающей точкой записывается в 10 словах памяти я общее масштабирование выполняется посредством сдвигов машинных слов целиком вместо сдвигов внутри слов.) 36. [М25] Поясните, как с высокой точностью вычислить !е 4 по заданноиу с соответствующей точностью приближению числа сЬ, используя только операции сложения и вычитания многократной точности и деления на короткие числа.
ь 37. [20] (Ю, Саламин (К. За!аппп).) Объясните,как в алгоритме П прн его реализации на двоичном компьютере запретить нормализацию и денормализацию, не изменяя порядка попыток вычисления разрядов частного, если число с( представлено по степеням 2. (Как можно на шаге ПЗ вычислить д, если на шаге П1 пе была выполнена нормализация".) 38. [М55] Предположим, что и и о — целые числа в интервале О < и, о < 2". Предложите способ вычисления среднего геометрического [ь/йо+ ь] прн помощи 0(п) операций сложения, вычитания и сравнения (п + 2)-битовых чисел. [указание. Объедините классические методы умножения и извлечения корней, используя "конвейер".) 39.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
