[Перевод] Разработка высокоскоростного ведического умножителя с использованием техник ведической математики

Habrahabr 4
Реферат: Эта статья посвящена разработке высокоскоростного ведического умножителя, использующего технику древнееиндийской ведической математики, модифицированной для улучшения быстродействия.
Ведическая математика — это древняя система математики с уникальной системой вычислений, основанной на 16-и сутрах. В статье показана эффективность Урдхва Триагбхайам (Urdhva Triyagbhyam) — ведического метода умножения, и выделяется разница с обычным умножением. Метод основан на параллельной генерации независимых произведений, устранении шагов с нулевым результатом и масштабировании к старшим битам с использованием алгоритма Карацубы (Karatsuba), совместимого с различными типами данных. Сутра Урдхва Триагбхайам является самым эффективным алгоритмом, дающим минимальную задержку для умножения всех типов чисел, и больших, и малых. Далее приводится код алгоритма на Verilog HDL для умножения 32х32 бита и реализация на FPGA с помощью Xilinx Synthesis Tool на Spartan 3E с выводом результата на LCD. Синтез результата показывает, что время вычислений для произведения 32х32 бита равно 31.526 ns.
Ключевые слова: ведическая математика, сутра урдхва триагбхайам, алгоритм Карацубы-Офмана Читать дальше →