AOP_Tom2 (1021737), страница 100
Текст из файла (страница 100)
гл, 6, раздел 18) был дан систематический метод перевода дробей из системы счисления с основанием 60 в систему счисления с основанием 10. (В первом издании книги Отреда 1631 года этот материал отсутствовал.) Правила преобразований из одной системы счисления в другую были сформулированы еще аль-Каши из Самарканда в его работе Ключ к арифметике (1427), в которой ясно изложены методы 1, а; 1, Ь и 2, а [Историко- математические исследования 7 (1954), 126-135], но в Европе его работа была неизвестна. В 18 веке американский математик Хью Джонс (НнкЬ Допев) для описания правил преобразования из восьмеричной системы счисления в десятичную ввел термины "осгагайопь (октавированне) и "Йесппайопп (децнмирование), но его методы оказались столь же неясными, как и его терминология.
А. М. Лежандр заметил, что положительные целые числа могут быть легко преобразованы в двоичный формат с помощью повторного деления на 64 [ТйеоНе Иеа ХошЬгея (Рапз, 1798), 229]. В 1946 году Г. Г. Гольдстайн (Н. Н. Со16вв!пе) и Дж, фон Нейман (3. чоп зеишапп) в своем классическом сочинении Р1апп1пя апс! Соайпб РгоЫетя Гог вп Е1ессгошс Со»прцВпб 1пяСгшпепс дали глубокий анализ проблелзы преобразований из одной системы счисления в другую в связи с необходимостью обосиоваиия применимости двоичной арифметики. (См. Зо)зп чоп Хеишапп, Со!1ессес! Бог)ся 5 ( зеш Уог)с: »Маспп!!ап, 1963), 127-142.) Другая ранняя работа, посвященная преобразованию чисел из одной системы счислеиия в другую в двоичных компьютерах, была опубликована Ф.
Кунс (Р. Коопв) и С. Лубкииым (8. ).иЫс!и) в журнале МасЛ. Сотр. 3 (1949), 427 — 431, где оии предложили пе совсем обычный метод преобразований, Несколько позже Ф. Л. Бауэр (Р. !.. Ваиег) и К. Замельсои (К. Багпе!воп) опубликовали первое обсуждение проблемы преобразования чисел с плавающей точкой [йе!С. сйг влбвя апс!Се Мас!з.
ипс! Р)»уя1!с 4 (1953), 312 — 316(. Исторический интерес представляют также заметки Г. Т. Лэйка (С. Т. !.а)се) (САСМ 5 (1962), 468 — 469(, в которых описываются методы аппаратной реализации преобразоваиий и приводятся понятные примеры, и статья А. Х. Строуда (А. Н, 81гоиб) и Д. Секреста (П. БесгевС) (Сотр.,у. 6 (1963), 62-66), в которой рассмотрено преобразование чисел, заданных с многократной точностью, Преобразования пеяаржалпвавапных чисел с плавающей точкой, сохраняющие соответствующую представлению "значимость", были рассмотрены Г. Кэвнером (Н. Каппег) в 3АСМ 12 (1965), 242-246, и Н.
Метрополисом (Х. »»Месгоро1!в) и Р. Л. Эшенхерстом (Н. !., Авйепйигвг) в Ма!1». Сотр. 19 (1965), 435-441. (См. также статью К, 8!)сс!аг, Вап1сйуа ВЗО (1968), 315-334„и приведенный в ней список литературы.) Ф. Дж. Плогер (Р. 3. Р!аибег) в книге Т)»е Всвпс1агс) С ПЬгагу (Ргепйсе-На!1, 1992), 301-331, приводит подробное описание подпрограмм форматированного ввода-вывода целых чисел и чисел с плавающей точкой, написанных иа языке программирования С. УПРАЖНЕНИЯ 1. (йо) Обобщите метод 1, Ь таким образам, чтобы ан был применим к позиционным системам счисления са смещенным основанием; преобразуйте выражение а Ь -» Ь»6о+ .
+ а»Ьо+ аз в АмВм-»...В»Во+ + А»Во + Аз, где 0 < аГ< Ь» и 0 < А» < В» при 0 < 1 < пз я 0 < » < М. Прапллюстряруйте работу обобщенного таким образом метода нв примере, выполнив перевод вручную величины о3 лпя, 9 часов, 12 минут и 37 секунд" в длинные тонны, хаядредвейты, стоуны, фунты и унции. (Пусть одна секунда равва одной унции. В британской системе весов 1 стоун равен 14 фунталз, 1 ханлредвейт равен В стоунам, 1 длинная тонна равна 20 хвплредвейтвм.) Другими славами, пусть Ьо = 60, 6» = 60, Ьз = 24, »и = 3, Во = 16, В» = 14, Вз = 3, Вз = 20, М = 4. Задача заключается в поиске при папаши систематического метода, обобщающего метод 1, Ь, таких чисел Аа,, Ао, расположенных в подлежащих интервалах, чтобы 3Ь»6»6о+ОЬ»Ьо +12Ьо + 37 = А»Вз»»Во + Аз»»Во+ А»В»Во + А»Во + Ао.
(Все арифметические операции должны выполняться в системе счисления са смешанным основанием.) 2. (33) Обобщите метод 1, а так,чтобы ан был применим к позиционной системе счисления са смешанным основанием, как в упр. 1, и приведите пример рабаты полученного обобщения, решив вручную ту же задачу преобразования,чта и в упр. 1. 3. (з»») (Д. Тараита (О. Твтапса).) При преобразования дробей остается открытым вопрос а количестве разрядов представления результата. Разработайте простое обобщение метода 2, а, такое, что для заданных двух положительных дробей и и ц принимающих значения между 0 и 1 и представленных в формате по основанию Ь, дробь и преобразуется в свой округленный эквивалент по основанию В, который имеет достаточный размер ЛХ справа от разделяющей точки, чтобы обеспечить выполнение неравенства [ — и[ < е.
(В частности, если и кратно Ь и е = Ь /2, значение У будет представлено достаточным количеством разрядов, так что по заданным У и гл дробь и может быть восстановлена точно, Заметим, что М может равняться нулю, Например, если е < э и и > 1 — е, то правильный ответ — П = 1.) 4. [М21] (а) Докажите, что любое вещественное число с конечным двоичным представлением имеет также конечное деслтпчное представление, (Ь) Найдите простое соотношение между положительными числами Ь н В, которое дает необходимые и достаточные условия для того, чтобы любое вещественное число, имеющее конечное представление в формате по основанию Ь, имело также конечное представление в формате по основанию В. 5.
[М20) Покажите, что программа (4) будет выполняться, если команду ЬОХ "10" заменить командой СОХ с при определенных значениях константы с. О. [20] Исгледуйте методы 1, а; 1, Ь; 2, а и 2, Ь для случая, когда 6 или В равно -2. 7. [М12) Известно, что 0 < а < х < а+1/ю и 0 < и < ш где и — целое число, Докажите, что [их] равно либо (ои), либо [ои) + 1. Более того, [их) = [аи) точно, если и < аю и а ' — целое число.
8. [24] Напишите йХХ-программу, аналогичную (1), которая использует соотношение (5) и не содержит команд деления. 9. [МЯУ] Назначение данного упражнения — вычисление [и/10] и и пюс(10 только при помощи операций двоичного сдвига, маскирования и сложения, если и — неотрицательное целое число. Положите Ь фиксированным целым числом, которое > 2, и рассмотрите процесс вычисления о» вЂ” и+ 1, о ь- о + 1:)', о е- и + ~ — ]', о <- и + ~ — ], о г- е + 2 10 25б ' 12е~) ' уе- ~ — ~,г+-ошо41б,г+-г+ Я,г <- Я Чему равно наименьшее положительное целое число и, такое, что д ~ [и/10) или г Ф я шоб 10? 10.
° [ЯЯ) В табл. 1 показано, как на двоичном компьютере с использованием различных операций сдвига, маскирования и сложения может быть удвоено десятичное число, закодированное в двоичной системе. Предложите аналогичный метод, который позволял бы вычислять половину двоично-кодированного десятичного числа (с отбрасыванием остатка в случае, когда число нечетное). 11. [1б) Преобразуйте число (57721)е в десятичное представление. ° 12. [22) Придумайте быстрый метод преобразования вручную целых чисел из троичной системы счисления в десятичную и проиллюстрируйте его, преобразовав в десятичный вид число (1212011210210)э. Как перевести число иэ десятичной системы счисления в троичную? ь 13. [26] Предположим, что в ячейках памяти 0+ 1, О+ 2,, Оч-гл содержится заданная с многократной точностью дробь (.и 1и е...
о м)м где 6 — размер слова компьютера йХХ. Напишите 21Х-программу, выполняющую преобразование этой дроби в десятичный формат и усекаюшую ее до 180 десятичных разрядов. Ответ должен быть напечатан в двух строчках, разряды должны быть сгруппированы в 20 блоков по 9 разрядов в каждом, разделенных пробелами. (Воспользуйтесь командой СНАЕ) ° ' 14. ]МЯ7] (А.
Шенхаге (А. Бсбопбабе).) При большом и время, необходимое для выполнения преобразования и-разрядного целого числа рассмотренным в разделе методом преобразования целых чисел многократной точности, имеет порядок п~. Покажите, что и-разрядное целое числа можно перевести в двоичный формат за 0(М(п) !ой и) шагов, где М(п) — количество пиклов, необходимых для выполнения операции умножения п-битовых чисел, которые удовлетворяют "условиям гладкости" М(2п) > 2М(п). 15. (М47] Можно ли существенным образом понизить верхнюю грань времени выполнения преобразования больших целых чисел, данную в упр.
14? (См. упр. 4.3.3-12.) 16. ]41] Постройте быструю линейную итерационную конфигурацию для преобразования чисел из десятичной системы счисления в двоичную (см. раздел 4.3.3Е). 17. ]М40] Разработайте "идеальные" подпрограммы, выполняющие преобразования чисел с плавающей точкой, которые переводили бы р-разрядные десятичные числа в Р-разрядные двоичные числа и наоборот, выдавая в обоих случаях правильный округленный результат в терминах раздела 4.2.2. 19. (НМ34] (Дэвид В. Матула (ПатЫ Чг. МаМа).) Пусть гоапбь(и, р) — функция 6, и и р, которые являются наилучшим приближением р-битового числа и с плавающей точкой, представленного в системе счисления по основанию Ь в смысле раздела 4.2.2.
Предполагая, что (окв 6 иррационально и что целая 'часть принадлежит бесконечному интервалу, докажите, что и = гоппс)ь(гоапбв(и, Р), р) для всех р-бнтовых чисел и с плавающей точкой, представленных по основанию 6 тогда н только тогда, когда Вг ' > Ьг.
(Другими словами, "идеальное" входное преобразование произвольного числа и в представление по независимому основанию В и выполняемое после него "идеальное" выходное преобразование этого результата всегда снова даст число и тогда и только тогда, когда промежуточная точность Р будет достаточно большой, как определено вышеприведенной формулой.) 19. ]Мяу] Предположим, что десятичное число и = (иг... иько)ье представлено как двоична-закодированное десятичное число У = (и?...иьиа)ье. Найдите соответствующие константы с, и маски гл„такие, что операция (? +- У вЂ” с,((? А т,), повторенная для ь = 1,2,3,переводит число (? в двоичное представление числа и, где "Лк означает извлечение (побитового 190), 4.5. АРИФМЕТИКА РАЦИОНАЛЬНЫХ ЧИСЕЛ При рвшйнии вычислительных задач зачастую важно знать, чем выражается результат: точным числом (например, 1/3) нли числом с плавающей точкой (например, "0.333333574о).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
