15. [М49] (Ш. А. Кук (S. А. Cook).) Алгоритм умножения называется алгоритмом реального времени, если ввод (А; + 1)-го бита операнда выполняется только после вычисления к-го выходного бита. Какие самые быстрые алгоритмы умножения в реальном времени можно реализовать на различных автоматах?

► 16. [25] Докажите, что для дискретного преобразования Фурье по (35) требуется всего 0{К log К) арифметических операций, даже если К не равно степени 2. [Указание. Перепишите выражение (35) в виде

o<t<K

и выразите этот результат в виде свертки.]

17. [М26] Схема умножения (2) Карацубы при получении п-разрядного произведения выполняет К„ 1-разрядных операций умножения, где Ki = 1, К2п = ЗКп и K2n+i = 2K„+i -f Кп при п > 1. "Решите" это рекуррентное уравнение путем поиска точной формулы для Кп, когда п = 2=i -Ь 2=2 Н-----h 2", ei > ег > • • • > е« > 0.

► 18. [МЗО] Разработайте схему выделения памяти для промежуточных результатов при выполнении операций умножения по рекурсивному алгоритму, основанному на уравнении (2). Заданы два JV-разрядных целых числа и а v, каждое из которых занимает N разрядов памяти. Покажите, как ограничить вычисления, чтобы произведение uv оказалось в последних значащих 2N разрядах {3N -Ь 0(Iog Л))-разрядной области рабочего пространства.

► 19. [М23] Покажите, как вычислить uv mod т при ограниченном количестве операций, оговоренных в правилах упр. 3.2.1.1-11, если имеется возможность проверить, будет ли один операнд меньше другого. Оба числа и и v переменные, но m постоянно. Указание. Рассмотрите вопрос декомпозиции в (2).

4.4. ПРЕОБРАЗОВАНИЕ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ

Если БЫ НАШИ ПРЕДКИ, изобретая арифметику, вели счет при помощи двух рук или восьми пальцев, а не десяти "цифр", у нас никогда бы не было хлопот с разработкой программ двоично-десятичного преобразования чисел. (И, возможно, мы бы никогда столько не узнали о системах счисления.) В этом разделе б}дут рассмотрены вопросы, связанные с преобразованием чисел из позиционной системы счисления по одному основанию в позиционную систему счисления по другому основанию. Конечно, этот процесс наиболее важен для двоичных компьютеров при преобразовании входных данных, представленных в десятичном формате, в двоичный формат и преобразовании результатов из двоичного формата обратно в десятичный.

А. Четыре основных метода. Преобразование чисел из двоичной системы счисления в десятичную и обратно - одна из наиболее машинно-зависимых операций, поскольку разработчикам компьютеров приходится постоянно изобретать различные способы аппаратной реализации этой операции. В связи с этим далее будут рассматриваться только основные принципы решения данной задачи, на основании которых программисты могут выбирать процедуры, наиболее подходящие для реализации на компьютере конкретной конфигурации.

Будем предполагать, что операции преобразований выполняются только с неотрицательными числами, так как манипулирование знаками легко учесть.

Предположим, что вьшолняется преобразование из системы счисления по основанию b в систему счисления по основанию В. (Обобщение для систем счисления со смешанным основанием рассматривается в упр. 1 и 2.) Большинство процедур преобразования из одного основания в другое основано на операциях умножения и деления, использующих один из четырех методов, которые описываются ниже. Два первых метода применяются для преобразования целых чисел (разделяющая точка расположена справа), а два других - для дробных частей чисел (разделяющая точка расположена слева). Чаще всего нельзя точно выразить конечную дробную часть по основанию b (0.u iu 2 .. .и т)б в виде конечной дробной части по основанию В (O.U-iU-2 U...m)b- Например, десятичная дробь в двоичном формате.представляется бесконечной дробью (0.0001100110011... )2- В связи с этим приходится иногда округлять результат до М разрядов.

Метод 1, а (Деление на В с использованием представления чисел в формате по основанию Ь). Для заданного целого числа и можно получить представление в формате по основанию В вида { U2U\Uq)b, выполняя

Uo=umoAB, C/i = [u/BJ mod В, U2 = [[u/B\/B\moAB,

до тех пор, пока не окажется [... \\и/В\/В\... /В\ = 0.

Метод 1, b (Умножение на В с использованием представления чисел в формате по основанию 6). Если представление числа и по основанию b имеет вид (и ... и\ио)ь, то можно, воспользовавшись арифметическими операциями с числами, которые

представлены в формате по основанию В, получить полином «„6"* Н-----\-uib+uo = и

в виде

((. ..{Umb + Um-l)b +---)b + Ui)b + Uo.

Метод 2, а (Умножение на 6 с использованием представления чисел в формате по основанию В). Для данного дробного числа и можно вычислить значения разрядов (.[/ !С/ 2 )в его представления по основанию В следующим образом: и1 = [иВ\, U-2 = [{uB}B\, Us[{{uB}B}B\,

где {х} означает а; mod 1 = х - [х\. Чтобы округлить результат до М разрядов, вычисления можно прервать после получения U-m, причем если {... {{иВ}В} .. .В} больше , то значение U-m следует увеличить на единицу. (Заметим, однако, что эта операция может привести к необходимости выполнения переносов, которые должны быть при помощи арифметических операций по основанию В включены в результат. Было бы проще перед началом вычислений прибавить к исходному числу и константу В", но это может привести к неправильному результату, если в компьютере число В~ не может быть точно представлено в формате по основанию Ь. Заметим также, что возможно округление результата до (1.00.. .0)в, если 6" > 2Б.)

В упр. 3 рассматривается обобщение этого метода на случай переменного М, достаточно большого для представления исходного числа с заданной точностью. В такой ситуации проблема переносов не возникает.

Метод 2, b (Деление на 6 с использованием представления чисел в формате по основанию В). Если число и представлено по основанию b в виде (0.u iu 2 . . ы-,п)ь, то можно, используя арифметические операции по основанию В, вычислить u-ib + u2b~ Н----+ u-mb" в виде

((. . . {и-т/Ь + Ul-m)/6 + • • + W 2)/6 +

Необходимо внимательно следить за погрешностями, возникающими при усечениях или окр}тлениях во время выполнения операции деления на Ь; они. как правило, незначительны, но это бьшает не всегда.

Подведем итоги. Методы 1, а; 1, Ь; 2, а и 2, b предоставляют по два воз.\южных способа преобразования целых и дробных чисел. И, конечно, существует возможность выполнять преобразования целых чисел в дробные и наоборот путе.м умножения или деления на соответствующую степень b или В. Поэтому для выполнения преобразования имеется на выбор по крайней мере четыре метода.

В. Преобразование с однократной точностью. Чтобы проиллюстрировать эти методы, предположим, что MIX - двоичный компьютер и нужно преобразовать неотрицательное целое число к, представленное в двоичном формате, в десятичнь£й формат, т. е. получить b = 2 и В = 10. Метод 1, а можно запрограммировать следующим образом.

ENT1 О Присвоить j <- 0. LDX и

ENTA О Присвоить гАХ <- и.

1Н DIV =10= (гА,гХ) ([rAX/10j,rAXmodl0).

STX ANSWER,! Uj rX. (1)

INCl 1 jj + l-

SRAX 5 rAX-i-rA.

JXP IB Повторять до тех пор,

пока в результате не получим нуль.

Для вычисления М разрядов необходимо затратить 18М + 4 циклов.