Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 99
Текст из файла (страница 99)
Другими словами, можно определить, где произошла ошибка, начав с проверки среднего результата, и затем в зависимости от того, верен ли результат, применить ту же процедуру к первой илн второй части вычислений. Ввиду того„что существует один шанс из девяти, что два схучайнмл целых числа будут отличаться по модулю девять, надежность процедуры выбрасывания девяток равна только 89%. Более надежный способ проверки — преобразовать результат обратно в восьмеричный формат с использованием обратного метода, который и будет сейчас рассмотрен.
Преобразование целых чисел, представленных в десятичном формате, в восьмеричный формат. Для выполнения обратного преобразования можно использовать аналогичную процедуру. Запишем заданное в десятичном формате число, удвоим на Й-м шаге к ведущих разрядов, используя представление в восьмеричмо и формате, и слолсим полученные (х + 1) ведущих разрядов, опять же используя представление в восьмеричном формате. Для заданного числа, содержащего (го + 1) разрядов, процесс заканчивается через щ шагов.
Пример 2. Преобразовать число (1419857) ш в восьмеричный формат. 1.4 1 9 8 5 7 + 16.19857 + 74 8 1 6.9 8 5 7 + 438 3616857 + 6436 86666.57 + 67664 4868417 +1668608 Реэулътлаян (6686181 )в. (Заметим, что при вычислении восьмеричного представления присутствуют невосьмеричные цифры 8 и 9.) Проверка результата может быть выполнена описанным выше способом. Этот метод был опубликован Шарлем П. Розье (СЬаг!еэ Р.
Воаег), ИВЕ 2галэ. СЕ-11 (1982), 708-709. Обе описанные процедуры представляют собой, по существу, вариации метода 1, Ь обобщенного преобразования из одной системы счисления в другую. Операции удваивания и вычитания в десятичной системе счисления подобны умножению на 10 — 2 = 8. Операции удваивания и вычитания в восьмеричной системе счисления подобны умножению на 8+ 2 = 10. Аналогичный метод существует и для преобразования из шестнадцатеричной системы счисления в десятичную, но это преобразование выполняется немного сложнее, так,как вместо операции умножения на 2 оно включает операцию умножения на б. Чтобы запомнить оба этих метода, нужно уяснить, что при переводе числа нз восьмеричной системы счисления в десятичную выполняется емчнпюние, так как представление чисел в десятичном формате короче, чем в восьмеричном. Аналогично при переводе числа из представления в десятичном формате в восьмеричный необходимо выполнять слолсенне.
Вычисления выполняются в формате представления результата, а не в исходном формате представления числа; в противном случае требуемый результат получен не будет. Преобразование дробей. Аналогичные методы, пригодные для столь же быстрого преобразования вручную дробей, неизвестны. Похоже, что наилучшим является метод 2, а, в котором с целью упрощения операций умножения на 10 или 8 выполняются операции удвоения и сложения. В этом случае критерий выбора сложения и~или вычитания меняется на обратный — при преобразовании чисел в десятичный формат выполняется сложение, а при преобразовании чисел в восьмеричный формат выполняется вычитание. Кроме того, при вычислениях используется формат, в котором представлено исходное число, а не формат, в котором подставляется результат (см. приведенные ниже примеры 3 и 4).
Реализация этого процесса требует примерно в два раза больше вычислений, чем рассмотренный выше метод преобразования целых чисел. Пример 3. Преобразование числа (.14159)ш в восьмеричный формат. 14159 2 6 316- 1.1 3 2 7 2 2 6 5 4 4- 1,0 б 1 7 6 1 2 3 5 2- 0.4 9 4 0 8 968 16- 6.9 5 2 4 6 190528- 762112 124224— 4.9 6 8 9 6 Резрльтавм (.110374...)з Пример 4. Преобразование числа (.110674)э в десятичный формат.
.1 1 О Я 7 4 880770+ 1.684 760 661660+ 4181160 84804 О+ 14 6л 14 О 1160600+ 5.6 7 1 7 О 0 1 6 6 6 6 О О+ 8,6 0 8 6 О д 1 8 О 6 4 0 О+ 6,8 Я Я 4 О 0 Резрльгпевп (.141586" ° )ге. ьз. Преобразование чисел с плавающей точкой. При выполнении преобразований чисел с плавающей точкой необходимо одновременно выполнять операции как с целой частью числа, так и с дробной, поскольку преобразование целой части числа оказывает влияние на дробную часть. Для преобразования числа У 2' в десятичный формат можно сначала представить 2' в виде Г 10 (обычно при помощи вспомогательных таблиц) и затем уже преобразовать Ру в десятичный фоРмат. Аналогично можно Умножить е на 1ойю2 н затем окРУглить РезУльтат до ближайшего целого числа Е; после этого разделить у 2' на 10н и преобразовать результат.
Обратно, для преобразован 1я числа Р 10н в двоичный формат можно преобразовать Р, а затем умножить е~ о на пк;ю тп", пре„вставленное в формате с плавающей точкой (снова используя вспомогательные таблицы). Для уменьшения максимальных размеров вспомогательных таблиц используется обычная методика, основанная на применении нескольких операций умножения и/или деления, хотя зто может привести к распространению ошибки вследствие округления промежуточных результатов. Вопросы минимизации таких ошибок рассмотрены в упр. 17. Е. Преобразование с многократной точностью. Начинать преобразование очень длинных чисел удобнее всего с преобразования блоков разрядов, операции с которыми можно выполнять с однократной точностью. Затем следует объединить эти блоки, пользуясь простыми способами, которые специфичны для многократной точности.
Например, пусть 10 — наивысшая степень 10, меньшая, чем размер машинного слова. Тогда: а) чтобы преобразовать целое число с многократной точностью из двоичного формата в десятичный, необходимо многократно разделить его на 10 (выполняя таким образом преобразование из двоичной системы счисления в десятичную с основанием 10" по методу 1, а); при помощи операций с однократной точностью получим и десятичных разрядов для каждой единицы представления в системе счисления с основанием 10"; Ь) чтобы преобразовать дробнрю часть числа с многократной точностью нз двоичного формата в десятичный, поступим подобным образом, умножив его на 10" (т.
е. использовав метод 2, а, где В = 10"); с) чтобы преобразовать целое число с многократной точностью нз десятичной системы счисления в двоичную, преобразуем сначала блоки по и разрядов; затем для перехода из системы счисления с основанием 10" в двоичный формат используем метод 1, Ь; Й) для преобразования дробной части с многократной точностью из представления в десятичном формате в двоичный сначала выполним преобразование в систему с основанием 10", как и в процедуре (с), а затем используем метод 2, Ь.
Р. История н библиография. Приемы преобразования чисел из одной системы счисления в другую использовались еще в древности в задачах, связанных с мерами, весами и деньгами, когда обычно приходилось иметь дело с системами счисления со смешанными основаниями, Этн преобразования обычно выполнялись с помощью вспомогательных таблиц, В 17 веке, когда шестидесятеричные дроби были вытеснены десятичными, возникла необходимость выполнять преобразование из одной системы счисления в другую с тем, чтобы можно было пользоваться имеющимися книгами астрономических таблиц. В 1667 году в книге под редакцией Вильяма Отреда (1т'ЬЬаш ОпйЬггед) С1агй Магйешабсш (см.
гл. 6, раздел 18) был дан систематический метод перевода дробей из системы счисления с основанием 60 в систему счисления с основанием 10, (В первом издании книги Отреда 1631 года этот материал отсутствовал.) Правила преобразований из одной системы счисления в другую были сформулированы еще аль-Каши из Самарканда в его работе Ключ к арифметике (1427), в которой ясно изложены методы 1, а; 1, Ь и 2, а (Нсторпкоматематяческне исследования 7 (1954), 126 — 135), но в Европе его работа была неизвестна. В 18 веке американский математик Хью Джонс (НпйЬ 3опеэ) для описания правил преобразования из восьмеричной системы счисления в десятичную ввел термины "осгаэат)оп" (октавирование) и "Йес1шаг1оп" (децимированне), но его методы оказались столь же неясными, как и его терминология.
А. М. Лежандр заметил, что положительные целые числа могут быть легко преобразованы в двоичный формат с помощью повторного деления на 64 1ТИеог1е 4еэ Хошбгел (Раг(э, 1798), 229). В 1946 году Г. Г, Гольдстайн (Н. Н. Оо!овгще) и Дж. фон Нейман (Л. топ Хецпщпп) в своем классическом сочинении Р!апп!пб ап»! Со»(!пб РгоЫшпв Рог ап Е!ее!гоше СощриПпб Лпвггиглепг дали глубокий анализ проблемы преобразований из одной системы счисления в другую в связи с необходимостью обоснования применимости двоичной арифметики.
(См. ЛоЬп топ Нещпапп, Со!!ессеи 14гаг)гв 5 (Хогг ггог]с Маспп1!ап, 1963), 127-142.) Другая ранняя работа, посвященная преобразованию чисел из одной системы счисления в другую в двоичных компьютерах, была опубликована Ф. Кунс (Р. Коопв) и С. Лубкнным (В. 1 цЫпп) в журнале Май.
Сотр. 3 (1949), 427-431, где они предложили не совсем обычный метод преобразований, Несколько позже Ф. Л, Бауэр (Р. 1. Вацег) и К. Замельсон (К. Ваше)воп) опубликовали первое обсуждение проблемы преобразования чисел с плавающей точкой [ЪЛ. гйг вийе»гази!ге Магй, ип»] Р)гуш)» 4 (1953), 312-316]. Исторический интерес представляют также заметки Г. Т. Лэйка (б. Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
