Умножение

Как видно из рис.3.16 и 3.17, при сложении и вычитании формат представления исходных данных и результата ^_одинаковый. На рис. 3.18 приведен пример умножения двух беззнаковых чисел, представленных в формате “слово” длиной 4 бита в дополнительном коде. Произведение этих чисел должно иметь длину 4 ^.2 ^_ 1 = 7

битов без потери точности.

Алгоритмы умножения, реализованные в различных процессорах, отличаются от общепринятого в двоичной

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

0 1 0 0

X

0 0 1 1

---------------

0 1 0 0

0 1 0 0

0 0 0 0

0 0 0 0

----------------------

0 0 0 1 1 0 0

Рис. 3. 18.Умножение в дополнительном коде

Без потери точности произведение двух беззнаковых чисел, представленных в формате “слово” длиной nбитов, должно иметь длину (2n^_1) битов. В процессорах с ФТ результат умножения размещается либо в формате “двойное слово”MSP:LSPдлиной 2nбитов, либо вMSP:LSPчасти расширенного слова также длиной 2n.

Отсюда возникает проблема “ лишнего” бита. Кроме того, появляется вопрос о сохранении вычисленного произведения в формате “слово” длиной nбитов – какую из частей произведенияMSPилиLSPследует сохранить? Выясним эти моменты на одном примере умножения (рис.3.18) при различных трактовках типа данных и различных арифметиках в процессоре. Рассмотрим следующие четыре ситуации:

1. Умножение целыхчисел прицелочисленной арифметике (рис.3.19):

• “лишний” бит используется как старший бит MSBв словеMSP:LSPдля хранениярасширения знака результата;

Десятичные

3 2 1 0 эквиваленты

0

1

0

0

2²= 4

X

3 2 1 0

1

1

0

1

^_2³ + 2²+ 2⁰=^_ 3

7 6 5 4 3 2 1 0

1

1

1

1

0

1

0

0

^_2^7+ 2^6+ 2^5+ 2^4+ 2^2=^_12

Расширение Значащие цифры

знака

MSP LSP

Рис 3.19. Умножение целых чисел при целочисленной арифметике

• знаковыми становятся два старших бита,значащими – остальные биты;

• если длина каждого из сомножителей не превышает n/2, результат размещается в младшем словеLSP,и его можно сохранить в формате “слово”без потерь; старшее словоMSPслужит для расширения знака;

• если длина сомножителей превышает n/2, для хранения результата потребуетсядваслова и специальная организация дальнейшей обработки.

2. Умножение дробных чисел прицелочисленнойарифметике; в этом случае дробные числа заменяются ихцелочисленнымиэквивалентами (рис.3.20):

• “лишний” бит используется, как старший битMSBв словеMSP:LSPдля хранениярасширения

знакарезультата;

• знаковыми становятсядва старших бита,значащими – остальные биты;

• в формате “слово” сохраняется старшеесловоMSPрезультата,младшее словоLSPотбрасывается; перед

выполнением дальнейших операций, для устранения лишнего знакового бита, содержимое двойного слова

MSP:LSPследует сдвинуть на один бит влево.

3. Умножение дробных чисел придробной арифметике (рис. 3.21)

• “лишний” бит используется, как младший бит LSBв словеMSP:LSPдля хранения нуля;LSB= 0;

• знаковым остается один старший бит, значащими -- остальные биты;

• для хранения результата в формате “слово” выбирается старшее слово MSP, младшее словоLSP

отбрасывается.

4. Умножение целых чисел при дробной арифметике; в этом случае целые числа заменяются их дробными

экивалентами (3.22):

• “лишний” бит используется, как младший битLSBв словеMSP:LSPдля хранения нуля;LSB= 0;

• знаковым остается один старший бит,значащими– остальные битыбез младшего битаLSB; после сдвига вправо на 1 бит получается результат точно такой же, как целое число при целочисленной арифметике – с расширением знака в двух старших битах словаMSP:LSP(сравните с рис. 3.19).

Отметим, что отсутствие ”лишнего” знакового бита в представлении результата умножения дробных чисел при дробной арифметике, наряду с отсутствием необходимости масштабирования данных, считается преимуществом дробной арифметики.

Теперь рассмотрим один из наиболее расппространенных алгоритмов умножения, реализованный в большинстве процессоров с ФТ.

Алгоритм умножениядвух беззнаковых двоичных чиселxиy,представленных в дополнительном коде в формате “слово” длинойn.

Десятичные Машинная

эквиваленты единица

3 2 1 0

0

1

0

0

2⁷/ 8 = 0,5 2³ = 8

X

3 2 1 0

1

1

0

1

^_2³/8 + 2²/8 + 2⁰/8 =^_0, 375

7 6 5 4 3 2 1 0

1

1

1

1

0

1

0

0

Расширение Значащие биты целочисленного

знака эквивалента дробного числа

MSPLSP

После сдвига MSP:LSPна 1 бит влево 2⁷ = 128

7 6 5 4 3 2 1 0

1

1

1

0

1

0

0

0

^_2^7/128 + 2^6/ 128 + 2^5/ 128 + 2^3/128= ^_0,1875 –точный результат

SЗначащие биты целочисленного

эквивалента дробного числа

MSPLSP

2³= 8

3 2 1 0

1

1

1

0

^_2^3/8 + 2^2/8 + 2^1/8 =^_0,125^_приближенный результат

S

S– знак

Рис. 3. 20. Умножение дробных чисел при целочисленной арифметике

3 2 1 0 Десятичные эквиваленты

0

1

0

0

2^-1= 0,5

X

3 2 1 0

1

1

0

1

^_2⁰+ 2^-1+2^-3= 0,375

7 6 5 4 3 2 1 0

1

1

1

0

1

0

0

0

^_2^0+ 2^-1 + 2^-2+ 2^-4 = ^_ 0,1875 – точный результат

SЗначащие биты дробного числа

MSP LSP

3 2 1 0

1

1

1

0

^_2^0+ 2^-1+2^-2=^_0,25 – приближенный результат

S

S –знак

Рис. 3. 21.Умножение дробных чисел при дробной арифметике

x = x₀ x₁ … x_i … x_n-1;

y = y₀ y₁ … y_i … y_n-1,

где x_iиy_i– значенияi–xбитов,

включает следующие шаги:

1. Подготовка к циклу:

• i=n^_1;

• начальная сумма локальных произведений s_i+1 = 0 …0 (формат “слово ” длинойn)

2. Тело цикла:

• вычисляется сумма локальных произведений s_i=s _i+1 +y^.x_i,

еслиx_i= 0, значениеs_iне меняется;

если x_i= 1, к значениюs_iприбавляетсяy, при этом оба слагаемых выровнены по

левому краю;

• выполняется расширение знака суммы s_i на один бит;

• присваивается i=i^_ 1.

Десятичные эквиваленты

Машинная единица равна 1, что соответствует maxпо модулю целому числу 2³=8

3 2 1 0

0

1

0

0

2­^-1.8=4

X

3 2 1 0

1

1

0

1

-2^0.8+2^-1.8+2^-3.8=-3

76 5 4 3 2 1 0

1

1

1

0

1

0

0

0

Машинная единица равна 1, что соответствует maxпо модулю целому числу 2⁶/2=64

SЗначащие биты дробного Не

эквивалента целого числа учитывается

MSP LSP

После сдвига MSP:LSPна 1 бит вправо

7 6 5 4 3 2 1 0

1

1

1

1

0

1

0

0

^_2^0 .64+2^-1 ^. 64 + 2^-2 .64 + 2^-4 . 64 = ^_ 12 точный результат

Расширение Значащие биты дробного эквивалента

Sцелого числа

MSP LSP

Рис.3.22. Умножение целых чисел при дробной арифметике

3. Проверка окончания цикла:

• цикл повторяется до i= 1 включительно.

4. Выход из цикла:

• при i= 0 вычисляется разностьs₀ =s₁^_y^.x₀:

если x₀ = 0, значениеs₀не меняется;

если x₀= 1, из значенияs₀вычитаетсяy; при этом вычитаемое и уменьшаемое

выровнены по левому краю;

• разность s₀равна произведению беззнаковых чиселxиyв дополнительном коде

и имеет длину (2n^_1) битов, где старший бит – знаковый;

• конечный результат формируется в формате “двойное слово” длиной 2n; при

этом “лишний” бит используется по – разному в зависимости от типа арифметики,

а именно:

“лишний” бит применяется, как старший бит MSBдля расширения знака, при

целочисленной арифметике;

“лишний” бит играет роль младшего бита LSB(LSB= 0) при дробной арифметике.