Старорусский метод удвоения-деления пополам

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

Операнды представлены в коде с естественными весами 8-4-2-1 и при сдвигах как влево, так и вправо необходима коррекция.

Сдвиг влево требует такой же коррекции, как и при алгебраическом сложении: для «неправильных» тетрад и для тетрад, из которых сформировались единицы переноса, нужна коррекция кодом +6₁₀=0110₂.

Сдвиг вправо требует коррекции кодом -3₁₀=1101₂ для тетрад, в которые сформировались единицы переноса. Этот корректирующий код образуется как разность между результатом деления пополам 16-ти и нужным результатом деления пополам 10-ти: 8-5=3. Эту разность надо вычесть из тетрад, в которые сформировались единицы переноса.

Основной недостаток метода – невысокое быстродействие из-за множества коррекций.

Пример.

Перемножить десятичные числа 43*38, считая число 43 множителем, и использовать для кодирования десятичных цифр код с естественными весами 8-4-2-1 и старорусский метод умножения.

43₁₀=101011₂=0100.0011._2-10; 38₁₀=0011.1000._2-10

В соответствии с алгоритмом множимое должно сдвигаться влево, поэтому регистр множимого должен иметь дополнительные разряды. Кроме того, операнды положительные – опускаем операцию со знаками.

Примечание.

Цифры в младшем разряде множителя после очередного сдвига и коррекции, взятые в обратном порядке, образуют представление множителя в двоичной системе счисления (в таблице эти цифры выделены жирным шрифтом и подчёркнуты). Этот способ можно использовать для перевода чисел из двоично-десятичной системы счисления в двоичную систему счисления: 43₁₀=0101011₂.

Десятично-двоичный метод умножения

Метод основан на преобразовании множителя, представленного в коде с естественными весами 8-4-2-1, в сумму произведений степени двойки на десятичные числа, содержащих лишь две цифры: 0 и 1. Причём, количество слагаемых в сумме – не более четырёх в связи с тем, что в двоичной тетраде четыре разряда.

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

Пример.

Выполнить умножение десятично-двоичным методом чисел 746 и 238, считая число 746 множителем.

Сначала преобразуется множитель:

746₁₀=.0111.0100.0110._2-10=

= (0*2³ +1*2² +1*2¹ +1*2⁰)*10²+

+(0*2³ +1*2² +0*2¹ +0*2⁰)*10¹+

+(0*2³ +1*2² +1*2¹ +0*2⁰)*10⁰=

= 000*2³ +111*2² +101*2¹ +100*2⁰

Проверим правильность преобразования множителя:

111*4+101*2+100=444+202+100=746

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

Множимое М=238₁₀ =0010.0011.1000._2-10 представлено в коде с естественными весами 8-4-2-1 и так как в процессе выполнения алгоритма его надо будет сдвигать влево, предусмотрены дополнительные разряды в регистре множимого и в регистре суммы частичных произведений.

Таблица

В таблице представлены этапы пошаговой реализации трёх частичных произведений с необходимыми коррекциями, а на последнем этапе – формирование полного произведения.

График выполнения курсовой работы

Защита курсовой работы не позднее 17-й недели семестра.

Поиск по сайту: