Алгоритм Харви — ван дер Хувена (Glikjnmb }gjfn — fgu ;yj }rfyug)

Перейти к навигации Перейти к поиску

Алгоритм Харви — ван дер Хувена — алгоритм умножения двух -битных целых чисел с временной сложностью в модели многоленточной машины Тьюринга[англ.]. Предложен математиками Дэвидом Харви из университета Нового Южного Уэльса и Йорисом ван дер Хувеном[англ.] из Национального центра научных исследований Франции. По состоянию на 2023 год является самым быстрым известным алгоритмом умножения чисел в данной модели, при этом оценка в на временную сложность алгоритмов умножения, по всей видимости, является неулучшаемой.

Вопрос о существовании быстрых алгоритмов умножения целых чисел занимает важное место в теории сложности вычислений. Наиболее известные методы умножения, такие как умножение «в столбик» требуют арифметических операций. Впервые данная оценка была улучшена в 1960 году Анатолием Карацубой, предложившим алгоритм умножения со временем работы [1]. В 1971 году Шёнхаге и Штрассен предложили алгоритм на основе быстрого преобразования Фурье со временем работы [2]. В той же работе ими была выдвинута гипотеза о том, что оптимальный алгоритм умножения требует элементарных операций. Однако долгое время оценка сверху, заданная алгоритмом Шёнхаге и Штрассена оставалась без улучшений. Только в 2007 году, спустя 36 лет, Мартин Фюрер предложил алгоритм со временем работы для неуточнённой константы , где  — итерированный логарифм[3]. В дальнейшем Харви и ван дер Хувен улучшили эту оценку сперва до [4], а затем до , таким образом подтверждая выдвинутую в гипотезе Шёнхаге и Штрассена оценку сверху[5]. Алгоритм имеет большое теоретическое значение, так как на нём достигается предположительная нижняя оценка на время работы алгоритмов умножения чисел в модели многоленточной машины Тьюринга. Однако практическое ускорение достигается лишь на числах, длина двоичной записи которых превосходит бит, в то время как число частиц в наблюдаемой вселенной оценивается как [6].

Примечания

[править | править код]
  1. А. Карацуба, Ю. Офман. Умножение многозначных чисел на автоматах // Докл. АН СССР. — 1962. — 9 февраля (т. 145, № 2). — С. 293—294.
  2. A. Schönhage, V. Strassen. Schnelle Multiplikation großer Zahlen (нем.) // Computing. — 1971-09-01. — Bd. 7, H. 3. — S. 281–292. — ISSN 1436-5057. — doi:10.1007/BF02242355.
  3. Martin Fürer. Faster Integer Multiplication (англ.) // SIAM Journal on Computing. — 2009-01. — Vol. 39, iss. 3. — P. 979–1005. — ISSN 1095-7111 0097-5397, 1095-7111. — doi:10.1137/070711761.
  4. David Harvey, Joris van der Hoeven. Faster integer multiplication using short lattice vectors (англ.) // The Open Book Series. — 2019-01-28. — Vol. 2, iss. 1. — P. 293–310. — ISSN 2329-9061 2329-907X, 2329-9061. — doi:10.2140/obs.2019.2.293.
  5. David Harvey, Joris Van Der Hoeven. Integer multiplication in time O(n log n) (англ.). — 2019. Архивировано 8 апреля 2019 года.
  6. Erica Klarreich. Multiplication hits the speed limit (англ.) // Communications of the ACM. — 2019. — 20 December. — doi:10.1145/3371387. Архивировано 30 июня 2020 года.