Согласно выдвинутой А. Н. Колмогоровым гипотезе n² [1] сложность операции умножения, то есть количество простых операций выполняемых для получения произведения, пропорциональна квадрату разрядности сомножителей. Следовательно и аппаратные затраты на реализации умножителя должны расти пропорционально квадрату разрядности сомножителей. Желание упростить реализацию умножителей привело к разработке методов быстрого умножения, для которых сложность реализации пропорциональна nlog23. [2].
Ниже рассмотрены результаты реализации метода быстрого умножения, базирующиеся на использовании выражения:
.
Суть метода базируется на том, что для позиционной системы счисления умножение на число, равное основанию этой системы равносильно сдвигу записи числа на один разряд, то есть его выполнение не требует применения дополнительных средств. Практически при реализации умножителя двоичные 2*n разрядные числа A и B записывают в виде 
и 
. Тогда алгоритм умножения приобретает вид:
В этом случае перемножаются числа, разрядность которых в два раза меньше исходных со сдвигом промежуточных результатов на требуемое число разрядов, что предполагает уменьшение аппаратных затрат на реализацию.
Исследование критического пути, параллельной канонической формы графа данного алгоритма, показало, что время получения результата определяется выражением:
,
где: 
,
,
- время суммирования n разрядных аргументов,
- время умножения n разрядных аргументов.
Для исследования зависимости аппаратных затрат, требуемых на реализацию данного алгоритма, от разрядности аргументов использовалась написанная на языке AHDL параметризированная программа. Исследования проводились для ПЛИС семейств Cyclone II и Stratix II. Эти ПЛИС предполагают выполнение операции умножения либо с использованием только логических блоков (ЛБ), либо с использованием специализированных встроенных умножителей, разрядности 9 х 9 бит.
Исследования показали, что в первом случае при увеличении разрядности аргументов использование алгоритмa быстрого умножения позволяет уменьшить затраты на реализацию умножителя для ПЛИС Cyclone II при n>15 (параметр maximize_speed = 0) и для ПЛИС Stratix II при n>35. При использовании встроенных умножителей применение метода быстрого умножения также позволяет снизить затраты на реализацию. В этом случае, например для ПЛИС семейства Cyclone II существует несколько областей (20≤n≤34 ,56≤n≤70, n>90) где его применение предпочтительнее стандартной мегафункции.
Полученные аналитические зависимости времени выполнения операции от разрядности аргументов для алгоритма быстрого умножения и стандартной мегафункции позволили найти минимальное число разрядов аргументов (nгр) для которого применение метода быстрого умножения позволяет уменьшить время вычисления относительно стандартной мегафункции lpm_mult :
- для ПЛИС Cyclone II, случай только ЛБ и maximize_speed = 0 ;nгр ≥ 24
- для ПЛИС Cyclone II, случай только ЛБ и maximize_speed = 10 ;nгр ≥42
- для ПЛИС Cyclone II, случай встроенных умножителей ;nгр ≥90
- для ПЛИС Stratix II, случай только ЛБ ;nгр ≥170
- для ПЛИС Stratix II, случай встроенных умножителей nгр ≥107
Подытоживая сказанное можно сделать вывод, что при увеличении разрядности сомножителей применение метода быстрого умножения позволяет получить выигрыш как по требуемым аппаратным ресурсам ПЛИС, так и по скорости вычисления.
СПИСОК ЛИТЕРАТУРЫ:
- http://mech.math.msu.su/probab/Kolmogorov/kolmogorov.html
- http://www.ccas.ru/personal/karatsuba/alg.htm