Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 100
Текст из файла (страница 100)
Ба1»е) ]САСМ 5 (1962), 468-469], в которых описываются методы аппаратной реализации преобразований и приводятся понятные примеры, и статья А. Х. Строуда (А. Н. Вагон»!) и Д. Секреста (П. Весгевв) (Сощр. Л. 6 (1963), 62-66], в которой рассыотрено преобразование чисел, заданных с многократной точностью. Преобразования кенаря»аливаеанных чисел с плавающей точкой, сохраняющие соответствующую представлению "значимость", были рассмотрены Г.
Кэвнером (Н. Каплет) в ЛАСМ 12 (1965), 242-246, и Н. Метрополисом (Х. Месгоро!!в) и Р. Л. Эшенхерстом (Н, 1. АвЬеп)гцгвз) в Май. Сощр. 19 (1965), 435-441. (См. также статью К. Вйс)аг, Вал!Йуа ВЗО (1968), 315-334, н приведенный в ней список литературы,) Ф. Дж. Плогер (Р. Л. Р!апбег) в книге Т]ге Вгап»(аг»( С 7.»Ьгагу (РгепВсе-Най, 1992), 301-331, приводит подробное описание подпрограмм форматированного ввода-вывода целых чисел и чисел с плавакицей точной, написанных на языке программирования С.
УПРАЖНЕНИЯ 1. (36] Обобщите метод 1, Ь таким образом, чтобы он был применим к позииионным системам счисления со смешанным основанием; преобразуйте выражение а„Ь„, г...Ь!Ьа+ . +а»Ьа+аа в АмВм г .. В»Ва+ +А»В»+Ао, гдеО<аз <Ь; и0<Аг <Вг приО<Л<глнО<у<гчз. Пранллкктрнруйте работу обобщенного таким образом метода на примере, выполнив перевал вручную величины "3 дня, 9 часов, 12 минут и 37 секунд" в длинные тонны, хандредвейты, стоуны, 4»унты и унции.
(Пусть одна секунда равна одной унции. В британской системе весов 1 стоун равен 14 фунтам, 1 хандредвейт равен 8 стоунам, 1 длинная тонна равна 20 хаидредвейтам.) Другими словами, пусть Ьа = 60, Ь = 60, Ьг = 24, гл = 3, Ва = 16, Вг = 14, Вг = 8, Вз = 20, М = 4. Задача заключается в поиске при помощи систематического метода, абобщающепг метод 1, Ь, таких чисел А»,, Аа, расположенных в наачежаших интервалах, чтобы 3ЬгЬ,Ьа+9Ь»Ьа+12Ьа+37 = А»Вз»»Ва+АзВгВ»Ва+ АгВ»Во + А»Ва + Аа. (Все арифметические операции должны выполняться в системе счисления са смешанным основанием.) 2. (36] Обобщите метод 1, а твк, чтобы он был применим к позиционной системе счисления со смешанным основанием, как в упр. 1, и приведите пример работы полученного обобщения, решив вручную ту же задачу преобразования, что н в упр, 1.
3. (ка] (Д. Таранто (П. Тагяшо).) При преображшанин дробей остается открытым вопрос о количестве разрядов представления результата. Рвзработайче простое обобщение метода 2, а, такое, что для зэдаиных двух положительных дробей и и», принимающих значения между 0 и 1 и предстаэлевиых в формате по осиоваикю Ь, дробь и преобразуется в свой округленный эквивалент по основанию В, который имеет достаточиый размер М справа от разделяющей точки, чтобы обеспечить выполнение иерэвеиства ]У вЂ” к] <». (Б частности, если и кратио Ь и» = Ь /2, значение П будет представлено достаточным количеством разрядов, так что по заданным У и ш дробь в мов»ет быть восствновлеиа точно.
Заметим„что М может равняться нулю, Например, если с < -' и к > 1 — », то правильный ответ — »/ = 1.) 4. (М21 ] (а) Докажите, что любое веществе»иое число с конечным деокчимм представлением имеет также конечное деслшвчиэе представление. (Ь) Найдите простое соотиошеиие между положительными числами Ь и В, которое дает необходимые и достаточные условия лля того, чтобы любое вещественное число, имекядее конечное представление в формате по основанию Ь, имело также конечное представление в формате по основанию В.
б. ]МХР] Покажите, что программа (4) будет выполняться, если хомякам' ЬОХ ~10" заменить командой ХОХ с при определенных значениях коистаиты с. 6. (РР] Исследуйте методы 1, а; 1, Хц! 2, а и 2, Ь для случая, когда Ь или В равко -2. Т. (М18] Известно, что О < а < к < а+ 1/ю и 0 < и < ю, где к — целое число. Докажите, что 1вк] равно либо (пк], либо 1ак] + 1. Более того, (вк] = (аи] точно, если в < ою и а ' — целое число.
В. ]24] Напишите НХХ-программу, аиааогичиую (1), которая использует соотношение (5) и ие содержит команд деления, 9. ]МЯР] Назначение данного упражнения — вычисление (в/10] и и шо»(10 только при помощи операций двоичного сдвига, маскирования и сложения, если в — неотрицательное целое число, Положите Ь фиксированным целым числом, которое > 2, и рассмотрите процесс вычислеиия »в! »э! »е! е ] е»-к+1е» е+ ] ],е» о+ ] ~,э+»!+ ] ],» в+ ~ ь ! ! ],101' ],2бб] ' ] 22а] ' е»- ~ — ~,г»- эшо»(1б,г»- г+ ]-],г»- Я Чему равно наименьшее положительное целое чисдо и, такое, что 9 ф (к/10] ш»и г Э» и шод 10? 10.. [82] Б табл.
1 показано, как иа двоичном компьютере с использованием различных операций сдвига, маскирования и сложения может быть удвоено десятичное число, закодировэилое в двоичной системе. Предложите аналогичный метод, который позволял бы вычислять пэлэеииу двоичпо-кодированиого десятичного числа (с отбрасыванием остатка в случае, когда число иечетиое).
11. ]18] Преобразуйте число (Я'781 )э в десятичиое цредставлеиие. э 12. ]23] Придумайте быстрый метод преобразования вручную целых чисел из троечной системы счислеиия в десятичную и проиллюстрируйте его, преобразовав в десятичный вид число (12120П210210)э, Как перевести чвсло нз десятичной системы счисления в троичную? ь 13. (88] Предположим, что в ячейках памяти у+ 1, у+ 2, ..., у+ и» содержится заданная с многократной точностью дробь (.в »в э...
к )э, где Ь вЂ” размер слова компьютерайХХ. Напишите йХХ-программу, выполия»ощую преобразоваике этой дроби в десятичный формат и усекающую ее до 180 десятичиых разрядов. Ответ должен бмть ивпечатаи в двух строчках, разряды должны быть сгруппироввиы в 20 блоков по 9 разрядов в каждом, разделеннмх пробелами. (Воспользуйтесь командой СНЬХ,) ь 14. [Мх7[ (А. Шенхаге (А. ЗсбопЬабе),) При большом и время, необходимое для выподнения преобразования и-разрядного целого числа рассмотренным в разделе методом преобразования целых чисел миогократной точности, имеет порядок лз.
Покажите, что и-разрядное целое число можио перевести в двоичный формат за 0(М(п)!об ц) шагов, где М(п) — количество циклов, необходимых для выполнения операции умножения и-битовых чисел, которые удовлетворяют "условиям гладкости" М(2п) > 2М(п). 13. [М47[ Можно ли существенным образом поиизить верхнюю грань времени выполиеиия преобразов илия больших целых чисел, данную в упр. 147 (См. упр, 4.3.3-12.) 16. [41[ Постройте быструю лииейиую итерациоиную конфигурацию для преобразования чисел из десятичной системы счисления в двоичную (см. раздел 4.3.3Е).
17. [М40) Разработайте "идеальные" подщюграммы, выпшшяющие преобразования чисел с плавающей точкой, которые переводили бы р-разрядиме десятичные числа в Р-разрядные двоичные числа и наоборот, выдавая в обоих случаях прюшльный округлениый результат в терминах раздела 4.2.2, 13. [ЛМ34[ (Дзвид В. Ьбатула (ПатЫ Ж. Масп)а).) Пусть говпдь(в,р) — функция Ь, и и р, которые являются наилучшим приближением р.битового числа и с цлавающей точкой, представленного в системе счисления по осиоваиию Ь в смысле раздела 4.2.2. Предполагая, что (обв Ь иррациональио и что целая часть принадлежит бескоиечиому интервалу, докажите, что в = гоивбь(гоиидв(и, Р),р) для всех р-битовых чисел и с плавающей точкой, предстаеленвых по основанию Ь тогда и только тогда, когда В' ' > Ь".
(Другимн словами, "идеальное" входное преобразование произвольного числа и в представлеиие по иезависимому основаиию В и выполняемое после него "идеальиое" выходное преобразование этого результата всегда снова даст число и тогда и только тогда, когда промежуточиая точность Р будет достаточно большой, как определено вышеприведенной формулой.) 19. [Мйу[ Предположим, что десятичное число в = (вг... в~во) ~о представлено как лвоичио-закодироваииое десятичиое число У = (вг...и~во)~в Найдите соответствующке константы с, и маски вь, такие, что операция У +- П вЂ” с;(У Л еы), повторениая для г = 1, 2, 3, переводит число У в двоичное представление числа и, где "Лт озиачает извлече. иие (побитового Ьйо).
4.5. АРИФМЕТИКА РАЦИОНАЛЬНЫХ ЧИСЕЛ При Решении вычислительных задач зачастую важно знать, чем выражается результат: точным числом (например, 1/3) яли числом с плавающей точкой (например, в0.333333574н). Если арифметические операции выполняются иад дробями, а не над приближениями к ним, то при выполнении большинства вычислений совершенно не накапливаются ошибки ок)эугленпл.
Это порождает чувство спокойной уверенности (которое часто отсутствует при выполнении операций над числами с плавающей точкой), что точность вычислений больше повышена быть не может. 4.5.1. Дроби При выполнении арифметических операций нвд дробями числа могут быть представлены в виде пары целых чисел (и/и'), где и и и' взаимно просты и и' > О. Число нуль представляется как (О/1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
