Особенности вычисления сумм частичных произведений
Рассматриваемые далее особенности алгоритмов умножения связаны с чередованием во времени шагов вычисления частичных произведений и их суммированием.
Со школы мы приучены действовать следующим образом.
В первую очередь вычисляются все частичные произведения и записываются друг под другом. При этом младшая цифра каждого следующего частичного произведения записывается под соответствующей цифрой множителя. Затем все частичные произведения складываются по правилу, позволяющему вычислять сразу окончательные значения цифр произведения в последовательности от младшего его разряда к старшему разряду.
Реализация подобной технологии с помощью аппаратных средств оказывается неразумной, так как требует оборудования для хранения значений всех вычисленных частичных произведений. (При этом в среднем половина из этих произведений будет равна нулю, так как в двоичном коде цифра разряда может с одинаковой вероятностью принять одно из двух значений). Кроме того, дополнительные и значительные по объему затраты оборудования понадобятся для обеспечения возможности суммирования сразу всех запомненных частичных произведений. Поэтому при проектировании алгоритмов умножения руководствуются следующими простыми положениями:
- частичные произведения равные нулю отбрасываются;
- произведение вычисляется в режиме последовательного накапливания суммы частичных произведений: каждое вычисленное не равное нулю частичное произведение немедленно прибавляется к накопленной ранее сумме частичных произведений, не ожидая вычисления следующего частичного произведения.
|
|
|
Руководствуясь этими простыми положениями, удается повысить скорость выполнения умножения за счет уменьшения количества операций суммирования кодов, и при этом не расходовать оборудование для запоминания всех частичных произведений.
Различные алгоритмы умножения можно разработать, пользуясь результатами «геометрических» наблюдений, вытекающими из рассмотрения примеров умножения кодов столбиком, аналогичных примеру из таблицы 6.1. Но можно руководствоваться и более формальными методами проектирования таких алгоритмов. Воспользуемся таким формальным подходом.
Дата добавления: 2016-01-04; просмотров: 16; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!