Операция умножения

Рассмотрим способность реализации в двоичной арифметике умножения. «Быстрый» вариант обыкновенного умножения был известен еще в Древнем Египте, его также называют «русским» или «крестьянским» методом.

Разберем пример такого умножения. Умножим 23 на 43 «русским методом».

Первый столбец состоит из результатов последовательного умножения первого сомножителя на 2, а второй — из результатов последовательного целочисленного деления второго сомножителя на 2. Далее суммируем числа первого столбца, рядом с которыми во втором столбце стоят нечетные числа.

Ответ: 23 х 43 = 23 + 46 + 184 + 736 = 989.

Такое умножение основано на следующих тождествах:

• а — четное: а х b = a/2 × (b × 2) = (a/2 × b) × 2
• а — нечетное: а х b = (a-1)/2 × (b × 2) + b = ((a-1)/2 × b) × 2 + b.

В результате получаем следующий рекурсивный алгоритм умножения целых двоичных чисел:

• если a = 0, то Mult(a, b) = 0; конец;
• a — четное: Mult(a, b) = Mult(a >> 1, b) << 1; конец;
• a — нечетное: Mult(a, b) = Mult(a >> 1, b) << 1 + b; конец;

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

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

• Если оба множителя положительны или отрицательны, то их произведение должно быть меньше, чем 2^k — 1; (если оба числа а и b отрицательны, то с помощью дополнительного кода они записаны как 2^k — |a| и 2^k — |b| и их произведение равно:

(2^k — |a|)(2^k — |b|) = 2^2k — 2^k (|a| + |b|) + |a|·|b|,

что в k -разрядной арифметике соответствует просто |a|·|b|, так как остальные слагаемые выходят за пределы k разрядов);

• Если множители имеют разный знак, например, а < 0, b > 0, то их произведение, можно представить как:

(2^k — |a|)|b| = 2^k|b| — |a|·|b|, но в k разрядах это просто 2^k — |a|·|b|,

т.е. дополнительный код числа -|a|·|b| и для получения правильного результата умножения достаточно, чтобы |a|·|b| ≤ 2^k-1.

Целочисленное деление с остатком в двоичной системе сводится к сравнению и вычитанию. Если как делимое так и делитель представимы в k-разрядном типе, то и результат деления и остаток от него будут получены правильно. Однако, если в делении участвуют отрицательные числа, то остаток компьютерного деления может не совпадать с математическим понятием остатка, и об этом следует помнить при программировании.