Пн. Фев 5th, 2024

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

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

23
×
43
46
21
92
10 (четное)
184
5
368
2 (четное)
736
1

Первый столбец состоит из результатов последовательного умножения первого сомножителя на 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-разрядах дает верный результат с точки зрения обычной арифметики.

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

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

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

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

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

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

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

От content

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

У нас нет баннеров, флэшей, анимации, отвратительных звуков или всплывающих объявлений. Мы не реализовываем эти типы надоедливых объявлений! Нам нужны деньги для обслуживания сайта, и почти все они приходят от нашей интернет-рекламы.

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
100% Free SEO Tools - Tool Kits PRO