Алгоритм фюрер является алгоритмом умножения целого числа для очень больших чисел с очень низкой асимптотической сложностью . Он был опубликован в 2007 году швейцарским математиком Мартином Фюрером из Пенсильванского государственного университета [1] как асимптотически более быстрый алгоритм при анализе на многолентовой машине Тьюринга, чем его предшественник, алгоритм Шёнхаге – Штрассена . [2]
Задний план
Алгоритм Шёнхаге-Штрассена использует быстрое преобразование Фурье (БПФ) для вычисления целочисленных произведений во времени.и его авторы, Арнольд Шёнхаге и Фолькер Штрассен , предполагают нижнюю оценку. Алгоритм Фюрера сокращает разрыв между этими двумя границами. Его можно использовать для умножения целых чисел длины во время где log * n - повторный логарифм . Разница между а также с точки зрения сложности, асимптотически в пользу алгоритма Фюрера для целых чисел, больших, чем . Однако разница между этими условиями для реальных значенийочень маленький. [1]
Улучшенные алгоритмы
В 2008 году Де и др. Представили аналогичный алгоритм, который полагается на модульную арифметику вместо сложной арифметики для достижения фактически того же времени работы. [3] Было подсчитано, что он становится быстрее, чем Шёнхаге-Штрассен, для входных данных, превышающих длину. [4]
В 2015 году Харви, Йорис ван дер Ховен и Лесерф [5] представили новый алгоритм, который обеспечивает время работы делая явным подразумеваемую константу в экспонента. Они также предложили вариант своего алгоритма, который позволяетно чья справедливость основана на стандартных предположениях о распределении простых чисел Мерсенна .
В 2015 году Кованов и Томе представили еще одну модификацию алгоритма Фюрера, которая обеспечивает такое же время работы. [6] Тем не менее, он остается таким же непрактичным, как и все другие реализации этого алгоритма. [7] [8]
В 2016 году Кованов и Томе предложили алгоритм целочисленного умножения, основанный на обобщении простых чисел Ферма, который предположительно достигает границы сложности. Это соответствует условному результату 2015 года Харви, ван дер Ховена и Лесерфа, но использует другой алгоритм и основывается на другой гипотезе. [9]
В 2018 году Харви и ван дер Ховен использовали подход, основанный на существовании коротких векторов решетки, гарантированных теоремой Минковского, для доказательства безусловной оценки сложности. [10]
В марте 2019 года Харви и ван дер Хувен опубликовали долгожданный алгоритм целочисленного умножения, который предположительно является асимптотически оптимальным. [11] [12] Поскольку Шёнхаге и Штрассен предсказали, что n log ( n ) является «наилучшим возможным» результатом, Харви сказал: «... ожидается, что наша работа станет концом пути к решению этой проблемы, хотя мы и не делаем этого». я пока не знаю, как это строго доказать ». [13]
Смотрите также
Рекомендации
- ^ а б М. Фюрер (2007). « Более быстрое целочисленное умножение » Труды 39-го ежегодного симпозиума ACM по теории вычислений (STOC), 55–67, Сан-Диего, Калифорния, 11–13 июня 2007 г., и SIAM Journal on Computing , Vol. 39 Выпуск 3, 979–1005, 2009.
- ^ Schönhage, A .; Штрассен, В. (1971). "Schnelle Multiplikation großer Zahlen" [Быстрое умножение больших чисел]. Вычислительная техника (на немецком языке). 7 (3–4): 281–292. DOI : 10.1007 / BF02242355 .
- ^ A. De, С. Саа, П. Kurur и Р. Saptharishi (2008). «Быстрое целочисленное умножение с использованием модульной арифметики» Труды 40-го ежегодного симпозиума ACM по теории вычислений (STOC), 499–506, Нью-Йорк, штат Нью-Йорк, 2008 г., и SIAM Journal on Computing , Vol. 42 Issue 2, 685–699, 2013. arXiv : 0801.1416
- ^ Людерс, Кристоф (2015). Реализация алгоритма DKSS умножения больших чисел (pdf) . Международный симпозиум по символьным и алгебраическим вычислениям. С. 267–274.
- Перейти ↑ D. Harvey, J. van der Hoeven и G. Lecerf (2015). «Еще более быстрое целочисленное умножение», февраль 2015 г. arXiv : 1407.3360
- ^ Кованов, С .; Томе, Э. (2015). «Быстрая арифметика для более быстрого умножения целых чисел». arXiv : 1502.02800v1 . Цитировать журнал требует
|journal=
( помощь )Опубликовано как Covanov & Thomé (2019) . - ^ С. Кованов и Э. Томе (2014). «Эффективная реализация алгоритма умножения больших чисел», Отчет внутреннего исследования, Политехническая школа, Франция, июль 2014 г.
- ^ С. Кованов и М. Морено Мацца (2015). «Применение алгоритма Фюрера на практике», магистерский исследовательский отчет, Политехническая школа, Франция, январь 2015 г.
- ^ Кованов, Святослав; Томе, Эммануэль (2019). «Быстрое целочисленное умножение с использованием обобщенных простых чисел Ферма». Математика. Комп. 88 : 1449–1477. arXiv : 1502.02800 . DOI : 10.1090 / MCOM / 3367 .
- Перейти ↑ D. Harvey and J. van der Hoeven (2018). «Более быстрое целочисленное умножение с использованием коротких векторов решетки», февраль 2018 г. arXiv : 1802.07932
- ^ Харви, Дэвид; Ван дер Хувен, Джорис (12 апреля 2019 г.). Целочисленное умножение за время O (n log n) .
- ^ Хартнетт, Кевин (14.04.2019). «Математики открывают идеальный способ умножения» . Проводной . ISSN 1059-1028 . Проверено 15 апреля 2019 .
- ^ Гилберт, Лахлан (4 апреля 2019 г.). «Математик решает задачу 48-летней давности на умножение» . UNSW . Проверено 18 апреля 2019 .