Таким образом, лучше выбрать третий метод. Для того чтобы понять, как именно он работает, рассмотрим умножение двух знаковых целых значений - и и v размером М и N битов соответственно. Вычисления в первой части листинга 8.1 рассматривают и как беззнаковую величину, имеющую значение u + au.i, где - знаковый бит и (т.е. и„ , = 1, если и отрицательно, и «„ , = О в противном случае). Аналогично, v интерпретируется программой как имеющее значение v + 2" v i.

Программа вычисляет произведение этих беззнаковых величин, а именно: {и + 2"u„,){v + 2%.,) = «V + 2"«„ ,v + 2"v ,« + 2""u„.,v, ,.

Для того чтобы nojp"iHTb требующийся результат (uv), необходимо вычесть из беззнакового произведения величину 2*u„ ,v + 2v, ,u . Вычитать член 2"*"и„ у,, нет необходимости, поскольку известно, что результат можно выразить при помощи М + N битов, так что нет необходимости вычислять биты старше, чем бит в позиции М + N ~\. Описанные вычитания выполняются в листинге 8.1 после трехСтрокового комментария и требуют прохода максимум по т + и полусловам.

Может оказаться соблазнительным использовать приведенную в листинге 8.1 программу, передавая ей в качестве параметров массивы из полных слов. Такая программа будет работать на машине с прямым порядком байтов, но не с обратным. Если хранить массивы в обратном порядке, когда и [о] содержит старшее полуслово (и программа будет соответствующим образом изменена), то при передаче в качестве параметров массивов полных слов программа будет работоспособной на машине с обратным (но не с прямым) порядком байтов.

8.2. Старшее слово 64-битового умножения

Теперь рассмотрим задачу вычисления старших 32 бит произведения двух 32-битовых целых чисел. Это функции из нашего базового набора RISC-команд - старшее слово знакового умножения (multiply high signed, mulhs) и старшее слово беззнакового умножения (multiply high unsigned, mulhu).

В случае беззнакового умножения хорошо работает алгоритм из перйой части листинга 8.1. Перепишем его для чртного случая т = п = 2 с развернутыми циклами и выполнением очевидных упрощений (изменив параметры на 32-битовые целые числа).

В случае знакового умножения нет необходимости в корректирующем коде из второй половины листинга 8.1. Этот код можно опустить, если правильно подойти к промежуточным результатам, объявляя их как знаковые. Конечный алгоритм приведен в листинге 8.2. При использовании беззнаковой версии просто замените все объявления int объявлениями unsigned.

Листинг 8.2. Старшее слово результата знакового умножения

int mulhs(int u, int v) {

unsigned uO, vO, wO;

int ul, vl, wl, w2, t;

uO = U & OxFFFF; Ul = u >> 16;

vO = V & OxFFFF; vJ. = v >> 16;

wO = U0*v0;

t = U1*V0 + (wO >> 16); wl = t & OxFFFF;

w2 = t >> 16;

wl = uO*vl + wl;

return ul*vl + w2 + (wl >> 16) ;

Данный алгоритм требует выполнения 16 базовых RISC-команд в каждой из версии (знаковой и беззнаковой), четыре из которых являются умножениями.

8.3. Преобразование знакового и беззнакового произведений

Предположим, что ijaui компьютер позволяет легко вычислить старшую половину 64-бнтового произведения двух 32-битовых беззнаковых целых чисел, но нам требуется выполнение этой операции для знаковых чисел. Можно воспользоваться процедурой нз листинга 8.2, но она требует вьшолнения четырех умножений. Более эффекщвную процедуру можно найти в [6].

Анализ данного алгоритма представляет собой частный случай анализа преобразованного для умножения знаковых чисел алгоритма Кнута (см. листинг 8.1). Пусть дг и у означают два 32-битовых знаковых целых числа, которые требуется перемножить. Компьютер рассматривает х как беззнаковое целое число, имеющее значение х+2"хз,, где Xji - целая величина, равная 1, если х отрицательно, и О в противном случае. Аналогично, у рассматривается как беззнаковое число, имеющее значение у + 2Уз.

Хотя нас интересуют только старшие 32 бита величины ху, компьютер производит вычисление

{х + 2х„){у + 2"уу,) = ху + 2"{х„у + у,,х) + 2х„у,,.

Для того чтобы получить интересующий нас результат, необходимо вычесть из полученной величины 2" {х,,у + у„х) + 2Xij,i. Поскольку известно, что результат может быть

записан при помощи 64 битов, можно использовать арифметику по модулю 2. Это означает, что можно спокойно игнорировать последний член и вычислять знаковое произведение, как показано ниже (посредством семи базовых RISC-команд).

р <- mulhu(*,y) Команда беззнакового 64-битового умножения

j:»3l)&y t,=x„y (1)

ya>3l Sex II Г2 = УзХ

p *- p-ti-t p - искомый результат

Беззнаковое произведение

Обратное преобразование- знакового произведения в беззнаковое- выполняется так же просто. Полученная в результате программа представляет собой (1) с тем отличием, что первая команда заменяется командой знакового 64-битового умножения, а последняя операция заменяется на р *- р+/, +.

Совершенно очевидно, что умножение на константу можно преобразовать в последовательность сдвигов и сложений. Например, для умножения х на 13 (1101 в двоичном представлении) можно воспользоваться приведенным ниже,способом (результат умножения - г).

/, <-дг«2 /j <-дг«3 r<г-t+U +X

В этом разделе левые сдвиги записываются как умножения на степени двойки, так что приведенный план вычислений записывается как г <-8ж+4ж + ж; это должно ясно показывать, что для вычислений на большинстве компьютеров нам потребуется четыре базовых RISC-команды.

Хотелось бы подчеркнуть, что тема умножения на константы сложнее, чем кажется на первый взгляд. Кроме прочего, при рассмотрении разных вариантов умножения следует учитывать не только количество сдвигов и сложений, необходимых для реализации того или иного умножения. Для иллюстрации сказанного рассмотрим два варианта умножения на 45 (101101 в двоичном представлении).

(<- 4* (, <- 4*

t<-2t t,32x

n-r+t ri-t + x

t<-4t tjt,+t

rr+t r<:-r+t.

План вычислений, представленный слева, использует переменную t для хранения величины х, сдвинутой на количество позиций, соответствующих единичным битам множителя. Каждое сдвинутое значение получается из сдвинутого перед этим. Такой план обладает следующими преимуществами:

• для работы кроме регистров для входного и выходного значения требуется только один регистр;

• все команды, за исключением первых двух, двухадресные;

• величины сдвигов относительно невелики.

Эти же свойства остаются действительными и для других множителей.

В схеме справа сначала вьшолняются все сдвиги с д; в качестве операнда. Главное преимущество такого решения - увеличение параллелизма вычислений. На компьютере с достаточными возможностями распараллеливания вычислений на уровне команд правая схема ш-полняется всего за три такта, в то время как левая схема на машине с неограниченными возможностями распараллеливания вычислений на уровне команд требует четыре такта.

Кроме того, задача поиска минимального количества команд (подразумевая под ними команды сдвига и сложения) для выполнении умножения на константу нетривиальна. Далее будем считать, что множество допустимых команд состоит из сложения, вычитания, сдвига влево и отрицания (не). Кроме того, будем считать, что формат команд - трехадресный. Впрочем, если ограничиться только сложением (при этом сдвиг влево осуществляется путем сложения числа с самим собой, затем суммы с самой собой и т.д.), задача отнюдь не упрощается, как и в случае, если в набор команд добавить другие ко-