Наименьшее количество ворот для умножения

9

Каков наилучший результат для числа затворов в схеме, умножающей два n-разрядных целых числа?

Очевидный метод генерирует θ(N2)ворота. Есть лучшие подходы сθ(nlognloglogn) а также θ(nlogn2log(n)) ворота.

Я не смог найти ни одного семейства булевых цепей, которое может обрабатывать умножение с nlognворота. Интересно, существует ли такое семейство цепей?

эмир
источник
1
Вы ищете арифметическую схему или логическую схему?
Суреш Венкат
1
Я ищу булеву схему.
Амир
для записи, что является O(nlogn)алгоритм? Разве это не использует столько ворот?
ВЗН
3
@vzn Нет, алгоритм Мартина Фюрера является самым известным, и он дает схему с O(nlogn2logn)ворота. Schonhage-Strassen фактически используется в некоторых системах компьютерной алгебры для очень больших чисел.
Сашо Николов
4
Есть некоторые накладные расходы, чтобы превратить ТМ в цепь. Времяt(n) Алгоритм двери не подвести t(n)ворота. Общий перевод не может быть лучше, чем сложность схемы проблемы значения схемы. С другой стороны, лучшая равномерная сложность не подразумевает нижнюю границу сложности схемы, так как есть издержки также в обратном направлении, то есть могут быть схемы размераO(nlgn)даже если нет ТМ с таким временем выполнения для умножения.
Каве

Ответы:

2

Ниже приводится подробный обзор 2008 года, который охватывает основные теоретические алгоритмы умножения, в том числе те, которые обсуждались в комментариях к вашему вопросу (в том числе алгоритм Шёнхаге-Штрассена и O(nlogn2logn)Алгоритм Фюрера, см. Стр. 335 опроса). Однако реализация - это другой вопрос, и некоторые из этих алгоритмов могут не считаться практичными; Опрос не охватывает практические реализации. Хотя опрос включает в себя алгоритмы для полиномов, степенных рядов, действительных чисел и 2-адических чисел, целые числа являются частным случаем этого (см. Рис. 1 на стр. 336).

Быстрое умножение и его приложения , Бернштейн (Алгоритмическая теория чисел / Публикации MSRI / Том 44, 2008)

ВЗН
источник
В связанном документе нет страниц 335 или 336. Возможно, вы имели в виду ссылку на другой файл?
argentpepper
упс! спасибо за совет. вышеуказанная версия отмечена как черновик. эта версия с процитированным pg #s может быть окончательной?
ВЗН
1
@vzn: Даже эта бумага имеет большой O по всему log(n),