может привести к распространению ошибки вследствие округления промежуточных результатов. Вопросы минимизации таких ошибок рассмотрены в упр. 17.

E. Преобразование с многократной точностью. Начинать преобразование очень длинных чисел удобнее всего с преобразования блоков разрядов, операции с которыми можно вьшолнять с однократной точностью. Затем следует объединить эти блоки, пользуясь простыми способами, которые специфичны для многократной точности. Например, пусть 10" - наивысшая степень 10, меньшая, чем размер машинного слова. Тогда:

a) чтобы преобразовать целое число с многократной точностью из двоичного формата в десятичный, необходимо многократно разделить его на 10" (вьшолняя таким образом преобразование из двоичной системы счисления в десятичную с основанием 10" по методу 1, а); при помощи операций с однократной точностью получим п десятичных разрядов для каждой единицы представления в системе счисления с основанием 10";

b) чтобы преобразовать дробную часть числа с многократной точностью из двоичного формата в десятичный, поступим подобным образом, умножив его на 10" (т. е. использовав метод 2, а, где В = 10");

c) чтобы преобразовать целое число с многократной точностью из десятичной системы счисления в двоичную, преобразуем сначала блоки по п разрядов; затем для перехода из системы счисления с основанием 10" в двоичный формат используем метод 1, Ь;

d) для преобразования дробной части с многократной точностью из представления в десятичном формате в двоичный сначала выполним преобразование в систему с основанием 10", как и в процедуре (с), а затем используем метод 2, Ь.

F. История и библиография. Приемы преобразования чисел из одной системы счисления в другую использовались еще в древности в задачах, связанных с мерами, весами и деньгами, когда обычно приходилось иметь дело с системами счисления со смешанными основаниями. Эти преобразования обычно вьшолнялись с помощью вспомогательных таблиц. В 17 веке, когда шестидесятеричные дроби были вытеснены десятичными, возникла необходимость вьшолнять преобразование из одной системы счисления в другую с тем, чтобы можно было пользоваться имеющимися книгами астрономических таблиц. В 1667 году в книге под редакцией Вильяма Отреда (William Oughtred) Clavis Mathematics (см. гл. 6, раздел 18) был дан систематический метод перевода дробей из системы счисления с основанием 60 в систему счисления с основанием 10. (В первом издании книги Отреда 1631 года этот материал отсутствовал.) Правила преобразований из одной системы счисления в другую были сформулированы еще аль-Каши из Самарканда в его работе Ключ к арифметике (1427), в которой ясно изложены методы 1, а; 1, b и 2, а [Историко-математические исследования 7 (1954), 126-135], но в Европе его работа была неизвестна. В 18 веке американский математик Хью Джонс (Hugh Jones) для описания правил преобразования из восьмеричной системы счисления в десятичную ввел тер-.мины "octavation" (октавирование) и "decimation" (децимирование), но его методы оказались столь же неясными, как и его терминология. А. М. Лежандр заметил, что положительные целые числа могут быть легко преобразованы в двоичный формат с помощью повторного деления на 64 [Tieorie des Nombres (Paris, 1798), 229].

в 1946 году Г. Г. Гольдстайн (Н. Н. Goldstine) и Дж. фон Нейман (J. von Neumann) в своем классическом сочинении Planning and Coding Problems for an Electronic Computing Instrument дали глубокий анализ проблемы преобразований из одной системы счисления в другую в связи с необходимостью обоснования применимости двоичной арифметики. (См. John von Neumann, Collected Works 5 (New York: Macmillan, 1963), 127-142.) Другая ранняя работа, посвященная преобразованию чисел из одной системы счисления в другую в двоичных компьютерах, была опубликована Ф. Куне (F. Koons) и С. Лубкиным (S. Lubkin) в журнале Math. Сотр. 3 (1949), 427-431, где они предложили не совсем обычный метод преобразований. Несколько позже Ф. Л. Бауэр (F. L. Bauer) и К. Замельсон (К. Samelson) опубликовали первое обсуждение проблемы преобразования чисел с плавающей точкой [Zeit. fiir angewandte Math, und Physik 4 (1953), 312-316].

Исторический интерес представляют также заметки Г. Т. Лэйка (G. Т. Lake) [САСМ 5 (1962), 468-469], в которых описываются методы аппаратной реализа-Щ1И преобразований и приводятся понятные примеры, и статья А. X. Строуда (А. Н. Stroud) и Д. Секреста (D. Secrest) [Сошр. J. 6 (1963), 62-66], в которой рассмотрено преобразование чисел, заданных с многократной точностью. Преобразования ненормализованных чисел с плавающей точкой, сохраняющие соответствующую представлению "значимость", были рассмотрены Г. Кэннером (Н. Kanner) в JACM 12 (1965), 242-246, и Н. Метрополисом (N. MetropoUs) и Р. Л. Эшенхерстом (R. L. Ashenhurst) в Math. Сошр. 19 (1965), 435-441. (См. также статью К. Sikdar, Sankhya ВЗО (1968), 315-334, и приведенный в ней список литературы.) Ф. Дж. Пло-гер (Р. J. Plauger) в книге The Standard С Library (Prentice-Hall, 1992), 301-331, приводит подробное описание подпрограмм форматированного ввода-вывода целых чисел и чисел с плавающей точкой, написанных на языке программирования С.

УПРАЖНЕНИЯ

► 1. [25] Обобщите метод 1, b таким образом, чтобы он был применим к позиционным системам счисления со смешанным основанием; преобразуйте выражение

ашЬт-1 -bibo-{-----(-ai6o-l-ao в АмВм-i . BiBo-----\-AiBo-\-Ao,

где О < а/< bj и О < Aj < Bj при 0<j<7nH0<J<M.

Проиллюстрируйте работу обобщенного таким образом метода на примере, выполнив перевод вручную величины "3 дня, 9 часов, 12 минут и 37 секунд" в длинные тонны, хан-дредвейты, стоуны, фунты и унции. (Пусть одна секунда равна одной унции. В британской системе весов 1 стоун равен 14 фунтам, 1 хандредвейт равен 8 стоунам, 1 длинная тонна равна 20 хандредвейтам.) Другими словами, пусть 6о = 60, 6i = 60, 62 = 24, тп = 3, Во = 16, Bi = 14, В2 = 8, Вз = 20, М - А. Задача заключается в поиске при помощи систематического метода, обобщающего метод 1, Ь, таких чисел А4,..., Ао, расположенных в надлежащих интервалах, чтобы 3626i6o-f96i6o-H26o -f37 = A4B3B2BiBo-f А3В2В1В0 -\-А2В1В0 + AiBo + Aq. (Все арифметические операции должны выполняться в системе счисления со смешанным основанием.)

2. [25] Обобщите метод 1, а так, чтобы он был применим к позиционной системе счисления со смешанным основанием, как в упр. 1, и приведите пример работы полученного обобщения, решив вручную ту же задачу преобразования, что и в упр. 1.

► 3. [25] (Д. Таранто (D. Taranto).) При преобразовании дробей остается открытым вопрос о количестве разрядов представления результата. Разработайте простое обобщение

метода 2, а, такое, что для заданных двух положительных дробей и и е, принимающих значения между О и 1 и представленных в формате по основанию 6, дробь и преобразуется в свой округленный эквивалент по основанию В, который имеет достаточный размер М справа от разделяющей точки, чтобы обеспечить выполнение неравенства \U - и\ < е. (В частности, если и кратно 6""" и е = Ь~"/2, значение U будет представлено достаточным количеством разрядов, так что по заданным U и т дробь и может быть восстановлена точно. Заметим, что М может равняться нулю. Например, если е<ии>1 - е, то правильный ответ - U = 1.)

4. [М21 ] (а) Докажите, что любое вещественное число с конечным двоичным представлением имеет также конечное десятичное представление. (Ь) Найдите простое соотношение между положительными числами 6 и Б, которое дает необходимые и достаточные условия для того, чтобы любое вещественное число, имеющее конечное представление в формате по основанию Ь, имело также конечное представление в формате по основанию В.

5. [М20] Покажите, что программа (4) будет выполняться, если команду LDX «10"" заменить командой LDX «с« при определенных значениях константы с.

6. [30] Исследуйте методы 1, а; 1, Ь; 2, а и 2, b для случая, когда 6 или В равно -2.

7. [М18] Известно, что О < а < X < a + l/u; и О < U < ш, где U - целое число. Докажите, что [их] равно либо [auj, либо [auj + 1. Более того, [их] = [аи] точно, если и < ак; и а" -целое число.

8. [24] Напишите MIX-программу, аналогичную (1), которая использует соотношение (5) и не содержит команд деления.

► 9. [М29] Назначение данного упражнения - вычисление [u/lOj и и mod 10 только при помощи операций двоичного сдвига, маскирования и сложения, если и - неотрицательное целое число. Положите к фиксированным целым числом, которое > 2, и рассмотрите процесс вычисления

V и + 1,V V +

LieJ

, г «- n mod 16, г «- г +

Чему равно наименьшее положительное целое число и, такое, что q ф [u/lOJ или г ф и mod 10?

10.. [22] В табл. 1 показано, как на двоичном компьютере с использованием различных операций сдвига, маскирования и сложения может быть удвоено десятичное число, закодированное в двоичной системе. Предложите аналогичный метод, который позволял бы вычислять половину двоично-кодированного десятичного числа (с отбрасыванием остатка в случае, когда число нечетное).

11. [16] Преобразуйте число (5772/)8 в десятичное представление.

► 12. [22] Придумайте быстрый метод преобразования вручную целых чисел из троичной системы счисления в десятичную и проиллюстрируйте его, преобразовав в десятичный вид число (1212011210210)з. Как перевести число из десятичной системы счисления в троичную?

► 13. [25] Предположим, что в ячейках памяти V + 1, V+2, ..., U + т содержится заданная с многократной точностью дробь (.u-iu-a .. • и-т)ь, где 6 - размер слова компьютера MIX. Напишите MIX-программу, выполняющую преобразование этой дроби в десятичный формат и усекающую ее до 180 десятичных разрядов. Ответ должен быть напечатан в двух строчках, разряды должны быть сгруппированы в 20 блоков по 9 разрядов в каждом, разделенных пробелами. (Воспользуйтесь командой CHAR.)