Алгоритм Харви — ван дер Хувена — алгоритм умножения двух ${\displaystyle n}$ -битных целых чисел с временной сложностью ${\displaystyle O(n\log n)}$ в модели . Предложен математиками Дэвидом Харви из университета Нового Южного Уэльса и из Национального центра научных исследований Франции. По состоянию на 2023 год является самым быстрым известным алгоритмом умножения чисел в данной модели, при этом оценка в ${\displaystyle O(n\log n)}$ на временную сложность алгоритмов умножения, по всей видимости, является неулучшаемой.

История

Вопрос о существовании быстрых алгоритмов умножения целых чисел занимает важное место в теории сложности вычислений . Наиболее известные методы умножения, такие как умножение «в столбик» требуют ${\displaystyle O(n^{2})}$ арифметических операций. Впервые данная оценка была улучшена в 1960 году Анатолием Карацубой , предложившим алгоритм умножения со временем работы ${\displaystyle O(n^{\log _{2}3})}$ . В 1971 году Шёнхаге и Штрассен предложили алгоритм на основе быстрого преобразования Фурье со временем работы ${\displaystyle O(n\log n\log \log n)}$ . В той же работе ими была выдвинута гипотеза о том, что оптимальный алгоритм умножения требует ${\displaystyle O(n\log n)}$ элементарных операций. Однако долгое время оценка сверху, заданная алгоритмом Шёнхаге и Штрассена оставалась без улучшений. Только в 2007 году, спустя 36 лет, Мартин Фюрер предложил алгоритм со временем работы ${\displaystyle O(n\log n\cdot K^{\log ^{*}n})}$ для неуточнённой константы ${\displaystyle K>1}$ , где ${\displaystyle \log ^{*}n}$ — итерированный логарифм . В дальнейшем Харви и ван дер Хувен улучшили эту оценку сперва до ${\displaystyle O(n\log n\cdot 4^{\log ^{*}n})}$ , а затем до ${\displaystyle O(n\log n)}$ , таким образом подтверждая выдвинутую в гипотезе Шёнхаге и Штрассена оценку сверху . Алгоритм имеет большое теоретическое значение, так как на нём достигается предположительная нижняя оценка на время работы алгоритмов умножения чисел в модели многоленточной машины Тьюринга. Однако практическое ускорение достигается лишь на числах, длина двоичной записи которых превосходит ${\displaystyle 2^{1729^{12}}\approx 2^{7\cdot 10^{38}}}$ бит, в то время как число частиц в наблюдаемой вселенной оценивается как ${\displaystyle 2^{270}}$ .

Примечания