Алгоритм Харви — ван дер Хувена

Алгоритм Харви — ван дер Хувена — алгоритм умножения двух $n$$n$-битных целых чисел с временной сложностью $O(n\log <!--\; \; -->n)$$O(n\log n)$ в модели многоленточной машины Тьюринга.^[en] Предложен математиками Дэвидом Харви из университета Нового Южного Уэльса и Йорисом ван дер Хувеном^[en] из Национального центра научных исследований Франции. По состоянию на 2020 год является самым быстрым известным алгоритмом умножения чисел в данной модели, при этом оценка в $O(n\log <!--\; \; -->n)$$O(n\log n)$ на временную сложность алгоритмов умножения, по всей видимости, является неулучшаемой.

ИсторияПравить

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