Каков наилучший результат для числа затворов в схеме, умножающей два n-разрядных целых числа?
Очевидный метод генерирует ворота. Есть лучшие подходы с а также ворота.
Я не смог найти ни одного семейства булевых цепей, которое может обрабатывать умножение с ворота. Интересно, существует ли такое семейство цепей?
Ответы:
Ниже приводится подробный обзор 2008 года, который охватывает основные теоретические алгоритмы умножения, в том числе те, которые обсуждались в комментариях к вашему вопросу (в том числе алгоритм Шёнхаге-Штрассена иO(nlogn2log∗n) Алгоритм Фюрера, см. Стр. 335 опроса). Однако реализация - это другой вопрос, и некоторые из этих алгоритмов могут не считаться практичными; Опрос не охватывает практические реализации. Хотя опрос включает в себя алгоритмы для полиномов, степенных рядов, действительных чисел и 2-адических чисел, целые числа являются частным случаем этого (см. Рис. 1 на стр. 336).
Быстрое умножение и его приложения , Бернштейн (Алгоритмическая теория чисел / Публикации MSRI / Том 44, 2008)
источник