Алгоритм фюрерса - Fürers algorithm

Алгоритм Фюрера является алгоритм целочисленного умножения для очень больших целых чисел с очень низким асимптотическая сложность. Он был опубликован в 2007 году швейцарским математиком. Мартин Фюрер Университета штата Пенсильвания^[1] как асимптотически более быстрый алгоритм при анализе на многоленточной машине Тьюринга, чем его предшественник, алгоритм Алгоритм Шёнхаге – Штрассена.^[2]

Фон

Алгоритм Шёнхаге – Штрассена использует быстрое преобразование Фурье (БПФ) для вычисления целых произведений во времени ${\displaystyle O(n\log n\cdot \log \log n)}$ и его авторы, Арнольд Шёнхаге и Фолькер Штрассен, предположим нижнюю оценку ${\displaystyle \Omega (n\log n)}$. Алгоритм Фюрера сокращает разрыв между этими двумя границами. Его можно использовать для умножения целых чисел длины ${\displaystyle n}$ во время ${\displaystyle O\left(n\log n\ \cdot 2^{O(\log ^{*}n)}\right)}$ куда бревно*п это повторный логарифм. Разница между ${\displaystyle \log \log n}$ и ${\displaystyle 2^{\log ^{*}n}}$ с точки зрения сложности, асимптотически выгодно алгоритму Фюрера для целых чисел, больших, чем ${\displaystyle 2^{2^{64}}}$. Однако разница между этими условиями для реальных значений ${\displaystyle n}$ очень маленький.^[1]

Улучшенные алгоритмы

В 2008 г. и другие дал аналогичный алгоритм, основанный на модульная арифметика вместо сложной арифметики, чтобы добиться того же времени работы.^[3]Было подсчитано, что он становится быстрее, чем Schönhage-Strassen, для входных данных, превышающих длину ${\displaystyle 10^{10^{4796}}}$.^[4]

В 2015 году Харви, ван дер Хувен и Лесерф^[5] дал новый алгоритм, который обеспечивает время работы ${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$ делая явным подразумеваемую константу в ${\displaystyle O(\log ^{*}n)}$ экспонента. Они также предложили вариант своего алгоритма, который позволяет ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$ но чья справедливость основана на стандартных предположениях о распределении Простые числа Мерсенна.

В 2015 году Кованов и Томе представили еще одну модификацию алгоритма Фюрера, которая обеспечивает такое же время работы.^[6]Тем не менее, он остается таким же непрактичным, как и все другие реализации этого алгоритма.^[7][8]

В 2016 году Кованов и Томе предложили алгоритм целочисленного умножения, основанный на обобщении Простые числа Ферма который предположительно достигает границы сложности ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$. Это соответствует условному результату 2015 года Харви, ван дер Хувена и Лесерфа, но использует другой алгоритм и основывается на другой гипотезе.^[9]

В 2018 году Харви и ван дер Ховен использовали подход, основанный на существовании коротких векторов решетки, гарантированных Теорема Минковского доказать безусловную оценку сложности ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$.^[10]

В марте 2019 года Харви и ван дер Ховен опубликовали долгожданный ${\displaystyle O(n\log n)}$ алгоритм целочисленного умножения, который предположительно является асимптотически оптимальным.^[11][12] Поскольку Шёнхаге и Штрассен предсказывали, что п бревно(п) является «наилучшим возможным» результатом, по словам Харви: «... ожидается, что наша работа станет концом пути к решению этой проблемы, хотя мы пока не знаем, как это строго доказать».^[13]

Смотрите также

• Теоретико-числовое преобразование

Рекомендации

1. М. Фюрер (2007). "Более быстрое целочисленное умножение " Материалы 39-го ежегодного симпозиума ACM по теории вычислений (STOC), 55–67, Сан-Диего, Калифорния, 11–13 июня 2007 г., и SIAM Журнал по вычислениям, Vol. 39 Выпуск 3, 979–1005, 2009.
2. Schönhage, A .; Штрассен, В. (1971). "Schnelle Multiplikation großer Zahlen" [Быстрое умножение больших чисел]. Вычисление (на немецком). 7 (3–4): 281–292. Дои:10.1007 / BF02242355.
3. А. Де, К. Саха, П. Курур и Р. Саптариши (2008). «Быстрое целочисленное умножение с использованием модульной арифметики» Материалы 40-го ежегодного симпозиума ACM по теории вычислений (STOC), 499–506, Нью-Йорк, Нью-Йорк, 2008 г., и SIAM Журнал по вычислениям, Vol. 42 Выпуск 2, 685–699, 2013. arXiv:0801.1416
4. Людерс, Кристоф (2015). Реализация алгоритма DKSS умножения больших чисел (pdf). Международный симпозиум по символьным и алгебраическим вычислениям. С. 267–274.
5. Д. Харви, Дж. Ван дер Ховен и Г. Лесерф (2015). «Еще более быстрое целочисленное умножение», февраль 2015 г. arXiv:1407.3360
6. Covanov, S .; Томе, Э. (2015). «Быстрая арифметика для более быстрого умножения целых чисел». arXiv:1502.02800v1. Опубликовано как Кованов и Томе (2019).
7. С. Кованов и Э. Томе (2014). «Эффективная реализация алгоритма умножения больших чисел», Отчет о внутреннем исследовании, Политехническая школа, Франция, июль 2014 г.
8. С. Кованов и М. Морено Мацца (2015). «Внедрение алгоритма Фюрера на практике», магистерский исследовательский отчет, Политехническая школа, Франция, январь 2015 г.
9. Кованов, Святослав; Томе, Эммануэль (2019). «Быстрое целочисленное умножение с использованием обобщенных простых чисел Ферма». Математика. Комп. 88: 1449–1477. arXiv:1502.02800. Дои:10.1090 / mcom / 3367.
10. Д. Харви и Дж. Ван дер Хувен (2018). «Более быстрое целочисленное умножение с использованием коротких векторов решетки», февраль 2018 г. arXiv:1802.07932
11. Харви, Дэвид; Ван дер Хувен, Джорис (12 апреля 2019 г.). Целочисленное умножение за время O (n log n).
12. Хартнетт, Кевин (2019-04-14). «Математики открывают идеальный способ умножения». Проводной. ISSN  1059-1028. Получено 2019-04-15.
13. Гилберт, Лахлан (4 апреля 2019 г.). «Математик решает задачу умножения 48-летней давности». UNSW. Получено 18 апреля 2019.