Метод умножения двоичных целых без знаков

Умножение беззнаковое

Как следует из раздела 2.1, двоичные коды (n) -разрядных дробных чисел и соответствующих целых в масштабе 2ⁿ совпадают. Следовательно, двоичные коды дробных произведений в масштабе 2²ⁿ также совпадают с соответствующими целыми произведениями и алгоритмы дробных произведений применимы к целым.

S=A*B=A(B=b_n-1..b₀) = A(b_n-12^n-1 + … +b₁2¹+b₀2⁰)=

=(0+Ab_n-1)*2+ Ab_n-2)*2+… +_Ab₀ =>

S₀=0 => S₁=2S₀+Ab_n-1 à S₂= 2S₁+Ab_n-2à… à2S_n-1 +Ab₀

Рекуррентная формула вычисления целого произведения со стороны старших разрядов

(2.4) S_i+1=2S_i+Ab_{n-I ,} S₀ =0. i=1,...n или

Рекурсивная функция

S(i+1)=2S(i) +A b_n-I

(2.5) с общим членом ряда со стороны младших разрядов

S_i+1=S_i+B_ib_{n-i ,} B_i+1=2B_i S₁ =0, B₁=1; i=n…1

Схема умножения по формуле (2.4) приведена на рис. 2.2. и применима как к целым, так и к дробным в масштабах 2ⁿ в Ассемблере и в Си.

(b_n-i) 2n-1 n 0 shl

B/S S

+ A

n-1 0

Рис.2.2. Схема умножения целых чисел.

В схеме используются (2n+1)-разрядный регистр хранения произведения, в старших n разрядах размещается множитель B. Промежуточный разряд (n) добавляется, чтобы сохранить возможный при суммировании перенос в старшем разряде промежуточного произведения.

(n)- разрядный регистр множимого A.

Цикл умножения в С.

For(char i=0; i<8; i++)

S= (S&0x8000)? (S<<1) +A: S<<1;

Дата добавления: 2014-12-27