•Во-,

-5>;

А,-» В,.

Каждый б-индекс представляет собой соответствующий Л-индекс, циклически сдвинутый влево на одну позицию (при использовании циклического вращения трех битов). Обратный внешнему идеальному перемешиванию процесс получается путем циклического сдвига каждого индекса вправо. Ряд подобных соответствий приведен в табл. 7.1. Здесь п - количество элементов массива, а циклические сдвиги производятся над logj и битами.

Таблица 7.1. Перегруппировки и преобразовация индексов

ГЛАВА 8 УМНОЖЕНИЕ

8.1. Умножение больших чисел

Такое умножение может бьпъ вьшолнено традиционным школьным способом "в столбик". Однако вместо использования массива промежуточных результатов гораздо эффективнее добавлять к произведению каждую новую строку немедленно после ее вычисления.

Если множимое состоит из т слов, множитель - из и слов, то произведение занимает не более т + п слов, независимо от того, вьшолняется знаковое или беззнаковое умножение.

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

Код данной процедуры представлен в листинге 8.1. Здесь в качестве "цифр" используются полуслова. Параметр w содчмсит результат, а и и v- множимое и множитель соответственно. Каждый параметр представляет собой массив полуслов, в котором первое полуслово (w[o],u[03,v[o]) является младшей значащей цифрой (прямой порядок). Параметры тип представляют собой количество полуслов в массивах и и v соответственно.

Листинг 8.1. Знаковое умножение больших чисел

void multnns (unsigned short w[], unsigned short u[], unsigned short v[], int m, int n) { unsigned int k, t, b; int i, j;

for (i = 0; i < m; i++)

w[i3 = 0; for (j = 0; j < n; j++) {

к = 0;

for (i = 0; i < m; i++) {

t = u[i]*v[j] + w[i + j] + k;

W[i + j] = t; (Т.е., t & OxFFFF). к = t » 16;

w[j + m] = k;

Теперь w[] содержит беззнаковое произведение. Корректируем вычитанием v*2**16m при и < О и вычитанием и*2**1бп при v < О if ((short)и[m - 1] < 0) {

b = 0; Инициализируем заем

for (j =0; j < n; j++) {

t = w[j + ra] - V[j] - b; w[j + m] = t; b = t » 31;

if ((short)v[n - 1] < 0) { b = 0;

for (i = 0; i < m; i++) {

t = w[i + n] - u[i] - b; w[i + n] = t;

b = t >> 31;

return;

Понять код из листинга 8.1 поможет следующая иллюстрация (никакой связи между п и m нет, любое из них может быть больше другого):

... и.

Данная процедура следует алгоритму М из [39, раздел 4.3.1], но в качестве рабочего языка использует С и модифицирована для выполнения знакового умножения. Заметим, что присвоение t в первой половине листинга 8.1 не может вызвать переполнения, поскольку максимальное значение, которое может быть присвоено t, равно (2"-1)42(2"-1) = 2-1.

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

1. Получить абсолютные значения каждого входного операнда, выполнить беззнаковое умножение, а затем изменить знак результата, если сомножители имеют разные знаки.

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

3. Выполнить беззнаковое умножение, а затем скорректировать полученный результат.

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

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