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

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

Фон

Алгоритм Шёнхаге – Штрассена использует быстрое преобразование Фурье (БПФ) для вычисления целых произведений во времени и его авторы, Арнольд Шёнхаге и Фолькер Штрассен, предположим нижнюю оценку . Алгоритм Фюрера сокращает разрыв между этими двумя границами. Его можно использовать для умножения целых чисел длины во время куда бревно*п это повторный логарифм. Разница между и с точки зрения сложности, асимптотически выгодно алгоритму Фюрера для целых чисел, больших, чем . Однако разница между этими условиями для реальных значений очень маленький.[1]

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

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

В 2015 году Харви, ван дер Хувен и Лесерф[5] дал новый алгоритм, который обеспечивает время работы делая явным подразумеваемую константу в экспонента. Они также предложили вариант своего алгоритма, который позволяет но чья справедливость основана на стандартных предположениях о распределении Простые числа Мерсенна.

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

В 2016 году Кованов и Томе предложили алгоритм целочисленного умножения, основанный на обобщении Простые числа Ферма который предположительно достигает границы сложности . Это соответствует условному результату 2015 года Харви, ван дер Хувена и Лесерфа, но использует другой алгоритм и основывается на другой гипотезе.[9]

В 2018 году Харви и ван дер Ховен использовали подход, основанный на существовании коротких векторов решетки, гарантированных Теорема Минковского доказать безусловную оценку сложности .[10]

В марте 2019 года Харви и ван дер Ховен опубликовали долгожданный алгоритм целочисленного умножения, который предположительно является асимптотически оптимальным.[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.