Вычислительная сложность математических операций

В следующих таблицах перечислена вычислительная сложность различных алгоритмов для распространенных математических операций .

Здесь сложность относится к временной сложности выполнения вычислений на многоленточной машине Тьюринга . ^[1] См. обозначение большой буквы O для объяснения используемых обозначений.

Примечание. Из-за разнообразия алгоритмов умножения $M(n)$ ниже обозначает сложность выбранного алгоритма умножения.

Арифметические функции [ править ]

В этой таблице указана сложность математических операций с целыми числами.

Операция	Вход	Выход	Алгоритм	Сложность
Добавление	Два $n$ -значные числа	Один $n+1$ -значное число	Дополнение к учебнику с переноской	$\Theta (n)$
Вычитание	Два $n$ -значные числа	Один $n+1$ -значное число	Вычитание учебника с заимствованием	$\Theta (n)$
Умножение	Два $n$ -значные числа	Один $2n$ -значное число	Учебник длинного умножения	$O{\mathord {\left(n^{2}\right)}}$
			Алгоритм Карацубы	$O{\mathord {\left(n^{1.585}\right)}}$
			Трехстороннее умножение Тума – Кука	$O{\mathord {\left(n^{1.465}\right)}}$
			$k$ -способ умножения Тума-Кука	$O{\mathord {\left(n^{\frac {\log(2k-1)}{\log k}}\right)}}$
			Тум-Кук смешанного уровня (Кнут 4.3.3-T) ^[2]	$O{\mathord {\left(n\,2^{\sqrt {2\log n}}\,\log n\right)}}$
			Алгоритм Шёнхаге – Штрассена	$O{\mathord {\left(n\log n\log \log n\right)}}$
			Алгоритм Харви-Хувена ^[3]^[4]	$O(n\log n)$
Разделение	Два $n$ -значные числа	Один $n$ -значное число	Учебник длинного деления	$O{\mathord {\left(n^{2}\right)}}$
			Подразделение Бурникеля-Зиглера «Разделяй и властвуй» ^[5]	$O(M(n)\log n)$
			Подразделение Ньютона-Рафсона	$O(M(n))$
Квадратный корень	Один $n$ -значное число	Один $n$ -значное число	метод Ньютона	$O(M(n))$
Модульное возведение в степень	Два $n$ -цифровые целые числа и $k$ -битная экспонента	Один $n$ -цифровое целое число	Повторное умножение и сокращение	$O{\mathord {\left(M(n)\,2^{k}\right)}}$
			Возведение в степень возведением в степень	$O(M(n)\,k)$
			Возведение в степень с сокращением Монтгомери	$O(M(n)\,k)$

В более сильных вычислительных моделях, в частности, в указательной машине и, следовательно, в машине произвольного доступа с единичной стоимостью, можно умножить два $n$ -битных числа за время O ( n ). ^[6]

Алгебраические функции [ править ]

Здесь мы рассматриваем операции над полиномами, а $n$ обозначает их степень; для коэффициентов мы используем модель удельной стоимости , игнорируя количество битов в числе. На практике это означает, что мы предполагаем, что они являются машинными целыми числами.

Операция	Вход	Выход	Алгоритм	Сложность
Полиномиальная оценка	Один многочлен степени $n$ с целыми коэффициентами	Один номер	Прямая оценка	$\Theta (n)$
Полиномиальная оценка	Один многочлен степени $n$ с целыми коэффициентами	Один номер	метод Горнера	$\Theta (n)$
Полиномиальный НОД (более $\mathbb {Z} [x]$ или $F[x]$ )	Два многочлена степени $n$ с целыми коэффициентами	Один многочлен степени не более $n$	Евклидов алгоритм	$O{\mathord {\left(n^{2}\right)}}$
Полиномиальный НОД (более $\mathbb {Z} [x]$ или $F[x]$ )	Два многочлена степени $n$ с целыми коэффициентами	Один многочлен степени не более $n$	Быстрый алгоритм Евклида (Лемера) ^{[ нужна ссылка ]}	$O(M(n)\log n)$

Специальные функции [ править ]

Многие из методов в этом разделе приведены в Borwein & Borwein. ^[7]

Элементарные функции [ править ]

Элементарные функции строятся путем составления арифметических операций, показательной функции ( $\exp$ ), натуральный логарифм ( $\log$ ), тригонометрические функции ( $\sin ,\cos$ ) и их обратные. Сложность элементарной функции эквивалентна сложности ее обратной, поскольку все элементарные функции аналитичны и, следовательно, обратимы с помощью метода Ньютона. В частности, если либо $\exp$ или $\log$ в комплексной области можно вычислить с некоторой сложностью, то эта сложность достижима для всех других элементарных функций.

Ниже размер $n$ относится к количеству цифр точности, с которой должна быть вычислена функция.

Алгоритм	Применимость	Сложность
серия Тейлора ; повторное сокращение аргументов (например, $\exp(2x)=[\exp(x)]^{2}$ ) и прямое суммирование	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)n^{1/2}\right)}}$
серия Тейлора; БПФ Ускорение на основе	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)n^{1/3}(\log n)^{2}\right)}}$
серия Тейлора; двоичное разделение + алгоритм пакетной передачи битов ^[8]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$
Среднеарифметико-геометрическая итерация ^[9]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O(M(n)\log n)$

Неизвестно, является ли $O(M(n)\log n)$ – оптимальная сложность элементарных функций. Самая известная нижняя оценка — это тривиальная оценка $\Omega$ $(M(n))$ .

Неэлементарные функции [ править ]

Функция	Вход	Алгоритм	Сложность
Гамма-функция	$n$ -значное число	Рядовая аппроксимация неполной гамма-функции	$O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$
	Фиксированное рациональное число	Гипергеометрическая серия	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$
	$m/24$ , для $m$ целое число.	Средняя арифметико-геометрическая итерация	$O(M(n)\log n)$
Гипергеометрическая функция ${}_{p}\!F_{q}$	$n$ -значное число	(Как описано в Borwein & Borwein)	$O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$
Гипергеометрическая функция ${}_{p}\!F_{q}$	Фиксированное рациональное число	Гипергеометрическая серия	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$

Математические константы [ править ]

В этой таблице указана сложность вычисления аппроксимации заданных констант до $n$ правильные цифры.

Постоянный	Алгоритм	Сложность
Золотое сечение , $\phi$	метод Ньютона	$O(M(n))$
Квадратный корень из 2 , ${\sqrt {2}}$	метод Ньютона	$O(M(n))$
число Эйлера , $e$	Бинарное расщепление ряда Тейлора для показательной функции	$O(M(n)\log n)$
число Эйлера , $e$	Ньютоновское обращение натурального логарифма	$O(M(n)\log n)$
Пи , $\pi$	Бинарное расщепление арктанса в формуле Мачина	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$ ^[10]
Пи , $\pi$	Алгоритм Гаусса – Лежандра	$O(M(n)\log n)$ ^[10]
постоянная Эйлера , $\gamma$	Метод Суини (приближение экспоненциальным интегралом )	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$

Теория чисел [ править ]

Алгоритмы теоретико-числовых расчетов изучаются в вычислительной теории чисел .

Операция	Вход	Выход	Алгоритм	Сложность
Наибольший общий делитель	Два $n$ -цифровые целые числа	Одно целое число, не более $n$ цифры	Евклидов алгоритм	$O{\mathord {\left(n^{2}\right)}}$
			Бинарный алгоритм НОД	$O{\mathord {\left(n^{2}\right)}}$
			Левый/правый k -арный двоичный алгоритм НОД ^[11]	$O{\mathord {\left({\frac {n^{2}}{\log n}}\right)}}$
			Алгоритм Стеле – Циммермана ^[12]	$O(M(n)\log n)$
			Алгоритм Евклидова спуска, управляемый Шёнхаге ^[13]	$O(M(n)\log n)$
Символ Якоби	Два $n$ -цифровые целые числа	$0$ , $-1$ или $1$	Алгоритм Евклидова спуска, управляемый Шёнхаге ^[14]	$O(M(n)\log n)$
Символ Якоби	Два $n$ -цифровые целые числа	$0$ , $-1$ или $1$	Алгоритм Стеле – Циммермана ^[15]	$O(M(n)\log n)$
Факториал	Положительное целое число, меньшее $m$	Один $O(m\log m)$ -цифровое целое число	Умножение снизу вверх	$O{\mathord {\left(M\left(m^{2}\right)\log m\right)}}$
			Бинарное расщепление	$O(M(m\log m)\log m)$
			Возведение в степень простых множителей $m$	$O(M(m\log m)\log \log m)$ , ^[16] $O(M(m\log m))$ ^[1]
Тест на примитивность	А $n$ -цифровое целое число	Правда или ложь	Тест на простоту AKS	$O{\mathord {\left(n^{6+o(1)}\right)}}$ ^[17]^[18] $O(n^{3})$ , предполагая гипотезу Агравала
			Доказательство простоты эллиптической кривой	$O{\mathord {\left(n^{4+\varepsilon }\right)}}$ эвристически ^[19]
			Тест на простоту Бэйли – PSW	$O{\mathord {\left(n^{2+\varepsilon }\right)}}$ ^[20]^[21]
			Тест на простоту Миллера – Рабина	$O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ ^[22]
			Тест на простоту Соловея – Штрассена	$O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ ^[22]
Целочисленная факторизация	А $b$ -битовое входное целое число	Набор факторов	Сито общего числового поля	$O{\mathord {\left((1+\varepsilon )^{b}\right)}}$ ^{[номер 1]}
Целочисленная факторизация	А $b$ -битовое входное целое число	Набор факторов	Алгоритм Шора	$O(M(b)b)$ , на квантовом компьютере

Матричная алгебра [ править ]

Следующие цифры сложности предполагают, что арифметика с отдельными элементами имеет сложность O (1), как и в случае с арифметикой с плавающей запятой фиксированной точности или операциями над конечным полем .

Операция	Вход	Выход	Алгоритм	Сложность
Умножение матрицы	Два $n\times n$ матрицы	Один $n\times n$ матрица	Умножение матрицы школьного учебника	$O(n^{3})$
			Уличный алгоритм	$O{\mathord {\left(n^{2.807}\right)}}$
			Алгоритм Копперсмита – Винограда ( галактический алгоритм )	$O{\mathord {\left(n^{2.376}\right)}}$
			Оптимизированные CW-подобные алгоритмы ^[23]^[24]^[25]^[26] ( галактические алгоритмы )	$O{\mathord {\left(n^{2.3728596}\right)}}$
Умножение матрицы	Один $n\times m$ матрица и один $m\times p$ матрица	Один $n\times p$ матрица	Умножение матрицы школьного учебника	$O(nmp)$
Умножение матрицы	Один $n\times \left\lceil n^{k}\right\rceil$ матрица и один $\left\lceil n^{k}\right\rceil \times n$ матрица, для некоторых $k\geq 0$	Один $n\times n$ матрица	Алгоритмы, приведенные в ^[27]	$O(n^{\omega (k)+\epsilon })$ , где верхние границы $\omega (k)$ даны в ^[27]
Инверсия матрицы	Один $n\times n$ матрица	Один $n\times n$ матрица	Элиминация Гаусса – Джордана	$O{\mathord {\left(n^{3}\right)}}$
			Уличный алгоритм	$O{\mathord {\left(n^{2.807}\right)}}$
			Алгоритм Копперсмита – Винограда	$O{\mathord {\left(n^{2.376}\right)}}$
			Оптимизированные CW-подобные алгоритмы	$O{\mathord {\left(n^{2.373}\right)}}$
Разложение по сингулярным значениям	Один $m\times n$ матрица	Один $m\times m$ матрица, один $m\times n$ матрица и один $n\times n$ матрица	Двудиагонализация и QR-алгоритм	$O{\mathord {\left(m^{2}n\right)}}$ ( $m\geq n$ )
Разложение по сингулярным значениям	Один $m\times n$ матрица	Один $m\times n$ матрица, один $n\times n$ матрица и один $n\times n$ матрица	Двудиагонализация и QR-алгоритм	$O{\mathord {\left(mn^{2}\right)}}$ ( $m\leq n$ )
QR-разложение	Один $m\times n$ матрица	Один $m\times n$ матрица и один $n\times n$ матрица	Алгоритмы в ^[28]	$O{\mathord {\left(mn^{1+{\frac {1}{4-\omega }}}\right)}}$ ( $m\geq n$ )
Определитель	Один $n\times n$ матрица	Один номер	Расширение Лапласа	$O(n!)$
			Алгоритм без деления ^[29]	$O{\mathord {\left(n^{4}\right)}}$
			LU-разложение	$O(n^{3})$
			Алгоритм Барейсса	$O{\mathord {\left(n^{3}\right)}}$
			Быстрое умножение матриц ^[30]	$O{\mathord {\left(n^{2.373}\right)}}$
Обратная замена	Треугольная матрица	$n$ решения	Обратная замена ^[31]	$O{\mathord {\left(n^{2}\right)}}$

В 2005 году Генри Кон , Роберт Кляйнберг , Балаж Сегеди и Крис Уманс показали, что любая из двух разных гипотез будет означать, что показатель умножения матриц равен 2. ^[32]

Трансформирует [ править ]

Алгоритмы вычисления преобразований функций (в частности, интегральных преобразований ) широко используются во всех областях математики, в частности в анализе и обработке сигналов .

Операция	Вход	Выход	Алгоритм	Сложность
Дискретное преобразование Фурье	Конечная последовательность данных размера $n$	Набор комплексных чисел	Учебник	$O(n^{2})$
Дискретное преобразование Фурье	Конечная последовательность данных размера $n$	Набор комплексных чисел	Быстрое преобразование Фурье	$O(n\log n)$

Примечания [ править ]

^ Эта форма субэкспоненциального времени действительна для всех $\varepsilon >0$ . Более точную форму сложности можно представить как $O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.$

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Шёнхаге, А.; Гротефельд, AFW; Веттер, Э. (1994). Быстрые алгоритмы — реализация многоленточной машины Тьюринга . Издательство BI Science. ISBN 978-3-411-16891-0 . ОСЛК 897602049 .
^ Кнут 1997
^ Харви, Д.; Ван дер Хувен, Дж. (2021). «Целое умножение за время O (n log n)» (PDF) . Анналы математики . 193 (2): 563–617. дои : 10.4007/анналы.2021.193.2.4 . S2CID 109934776 .
^ Кларрайх, Эрика (декабрь 2019 г.). «Умножение достигает предела скорости». Коммун. АКМ . 63 (1): 11–13. дои : 10.1145/3371387 . S2CID 209450552 .
^ Бурникель, Кристоф; Зиглер, Иоахим (1998). Быстрое рекурсивное деление . Отчеты об исследованиях Института компьютерных наук Макса Планка. Саарбрюккен: Библиотека компьютерных наук и документация MPI. OCLC 246319574 . МПИИ-98-1-022.
^ Шенхаге, Арнольд (1980). «Машины для модификации хранилища». SIAM Journal по вычислительной технике . 9 (3): 490–508. дои : 10.1137/0209036 .
^ Борвейн, Дж.; Борвейн, П. (1987). Пи и AGM: исследование аналитической теории чисел и сложности вычислений . Уайли. ISBN 978-0-471-83138-9 . OCLC 755165897 .
^ Чудновский, Дэвид; Чудновский, Григорий (1988). «Приближения и комплексное умножение по Рамануджану». Рамануджан вновь посетил: Материалы столетней конференции . Академическая пресса. стр. 375–472. ISBN 978-0-01-205856-5 .
^ Брент, Ричард П. (2014) [1975]. «Методы нахождения нуля многократной точности и сложность вычисления элементарных функций» . В Траубе, Дж. Ф. (ред.). Аналитическая вычислительная сложность . Эльзевир. стр. 151–176. arXiv : 1004.3412 . ISBN 978-1-4832-5789-1 .
^ Jump up to: Перейти обратно: ^а ^б Ричард П. Брент (2020), Братья Борвейн, Пи и годовое собрание акционеров , Springer Proceedings in Mathematics & Статистика, vol. 313, arXiv : 1802.07558 , doi : 10.1007/978-3-030-36568-4 , ISBN 978-3-030-36567-7 , S2CID 214742997
^ Соренсон, Дж. (1994). «Два быстрых алгоритма НОД». Журнал алгоритмов . 16 (1): 110–144. дои : 10.1006/jagm.1994.1006 .
^ Крэндалл, Р.; Померанс, К. (2005). «Алгоритм 9.4.7 (двоично-рекурсивный НОД Стеле-Циммермана)» . Простые числа - вычислительная перспектива (2-е изд.). Спрингер. стр. 471–3. ISBN 978-0-387-28979-3 .
^ Мёллер Н (2008). «Об алгоритме Шёнхаге и вычислении субквадратичных целых НОД» (PDF) . Математика вычислений . 77 (261): 589–607. Бибкод : 2008MaCom..77..589M . дои : 10.1090/S0025-5718-07-02017-0 .
^ Бернштейн, DJ «Более быстрые алгоритмы для поиска неквадратных чисел по модулю наихудших целых чисел» .
^ Брент, Ричард П.; Циммерманн, Пол (2010). "Ан $O(M(n)\log n)$ Алгоритм для символа Якоби» . Международный симпозиум по алгоритмической теории чисел . Springer. стр. 83–95. arXiv : 1004.2091 . doi : 10.1007/978-3-642-14518-6_10 . ISBN 978-3-642-14518-6 . S2CID 7632655 .
^ Борвейн, П. (1985). «О сложности вычисления факториалов». Журнал алгоритмов . 6 (3): 376–380. дои : 10.1016/0196-6774(85)90006-9 .
^ Ленстра-младший, HW ; Померанс, Карл (2019). «Тестирование простоты с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–69. дои : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 .
^ Тао, Теренс (2010). «1.11 Тест на простоту АКС» . Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том. 117. Американское математическое общество. стр. 82–86. дои : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4 . МР 2780010 .
^ Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений . 76 (257): 493–505. arXiv : math/0502097 . Бибкод : 2007MaCom..76..493M . дои : 10.1090/S0025-5718-06-01890-4 . МР 2261033 . S2CID 133193 .
^ Померанс, Карл ; Селфридж, Джон Л .; Вагстафф-младший, Сэмюэл С. (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹ Математика (PDF) . вычислений . 35 (151): 1003–26. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .
^ Бэйли, Роберт; Вагстафф-младший, Сэмюэл С. (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . МР 0583518 .
^ Jump up to: Перейти обратно: ^а ^б Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты» . Теоретическая информатика . 12 (1): 97–108. дои : 10.1016/0304-3975(80)90007-9 . МР 0582244 .
^ Алман, Джош; Уильямс, Вирджиния Василевска (2020), «Усовершенствованный лазерный метод и более быстрое умножение матриц», 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021) , arXiv : 2010.05846 , doi : 10.1137/1.9781611976465.32 , S2CID 2 22290442
^ Дэви, AM; Стотерс, AJ (2013), «Улучшенная оценка сложности матричного умножения», Proceedings of the Royal Society of Edinburgh , 143A (2): 351–370, doi : 10.1017/S0308210511001648 , S2CID 113401430
^ Василевска Уильямс, Вирджиния (2014), Преодоление барьера Копперсмита-Винограда: умножение матриц в O (n ^2.373) время
^ Ле Галль, Франсуа (2014), «Степень тензоров и быстрое умножение матриц», Труды 39-го Международного симпозиума по символическим и алгебраическим вычислениям — ISSAC '14 , стр. 23, arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L , doi : 10.1145/2608628.2627493 , ISBN 9781450325011 , S2CID 353236
^ Jump up to: Перейти обратно: ^а ^б Ле Галль, Франсуа; Уррутия, Флорен (2018). «Улучшенное умножение прямоугольных матриц с использованием степеней тензора Копперсмита-Винограда». В Чумае, Артур (ред.). Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики. дои : 10.1137/1.9781611975031.67 . ISBN 978-1-61197-503-1 . S2CID 33396059 .
^ Найт, Филип А. (май 1995 г.). «Быстрое умножение прямоугольной матрицы и QR-разложение» . Линейная алгебра и ее приложения . 221 : 69–81. дои : 10.1016/0024-3795(93)00230-w . ISSN 0024-3795 .
^ Роте, Г. (2001). «Алгоритмы без делений для определителя и пфаффиана: алгебраические и комбинаторные подходы» (PDF) . Вычислительная дискретная математика . Спрингер. стр. 119–135. ISBN 3-540-45506-Х .
^ Ахо, Альфред В .; Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1974). «Теорема 6.6». Проектирование и анализ компьютерных алгоритмов . Аддисон-Уэсли. п. 241. ИСБН 978-0-201-00029-0 .
^ Фрели, Дж. Б.; Борегар, РА (1987). Линейная алгебра (3-е изд.). Аддисон-Уэсли. п. 95. ИСБН 978-0-201-15459-7 .
^ Кон, Генри; Кляйнберг, Роберт; Сегеди, Балаж; Уманс, Крис (2005). «Теоретико-групповые алгоритмы умножения матриц». Материалы 46-го ежегодного симпозиума по основам информатики . IEEE. стр. 379–388. arXiv : math.GR/0511460 . дои : 10.1109/SFCS.2005.39 . ISBN 0-7695-2468-0 . S2CID 6429088 .

Дальнейшее чтение [ править ]

Брент, Ричард П .; Циммерманн, Пол (2010). Современная компьютерная арифметика . Издательство Кембриджского университета. ISBN 978-0-521-19469-3 .
Кнут, Дональд Эрвин (1997). Получисловые алгоритмы . Искусство компьютерного программирования . Том. 2 (3-е изд.). Аддисон-Уэсли. ISBN 978-0-201-89684-8 .

[23] Эта форма субэкспоненциального времени действительна для всех $\varepsilon >0$ . Более точную форму сложности можно представить как $O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.$

[Schonhage-1] Jump up to: Перейти обратно: ^а ^б Шёнхаге, А.; Гротефельд, AFW; Веттер, Э. (1994). Быстрые алгоритмы — реализация многоленточной машины Тьюринга . Издательство BI Science. ISBN 978-3-411-16891-0 . ОСЛК 897602049 .

[2] Кнут 1997

[3] Харви, Д.; Ван дер Хувен, Дж. (2021). «Целое умножение за время O (n log n)» (PDF) . Анналы математики . 193 (2): 563–617. дои : 10.4007/анналы.2021.193.2.4 . S2CID 109934776 .

[4] Кларрайх, Эрика (декабрь 2019 г.). «Умножение достигает предела скорости». Коммун. АКМ . 63 (1): 11–13. дои : 10.1145/3371387 . S2CID 209450552 .

[5] Бурникель, Кристоф; Зиглер, Иоахим (1998). Быстрое рекурсивное деление . Отчеты об исследованиях Института компьютерных наук Макса Планка. Саарбрюккен: Библиотека компьютерных наук и документация MPI. OCLC 246319574 . МПИИ-98-1-022.

[6] Шенхаге, Арнольд (1980). «Машины для модификации хранилища». SIAM Journal по вычислительной технике . 9 (3): 490–508. дои : 10.1137/0209036 .

[7] Борвейн, Дж.; Борвейн, П. (1987). Пи и AGM: исследование аналитической теории чисел и сложности вычислений . Уайли. ISBN 978-0-471-83138-9 . OCLC 755165897 .

[8] Чудновский, Дэвид; Чудновский, Григорий (1988). «Приближения и комплексное умножение по Рамануджану». Рамануджан вновь посетил: Материалы столетней конференции . Академическая пресса. стр. 375–472. ISBN 978-0-01-205856-5 .

[9] Брент, Ричард П. (2014) [1975]. «Методы нахождения нуля многократной точности и сложность вычисления элементарных функций» . В Траубе, Дж. Ф. (ред.). Аналитическая вычислительная сложность . Эльзевир. стр. 151–176. arXiv : 1004.3412 . ISBN 978-1-4832-5789-1 .

[brent-10] Jump up to: Перейти обратно: ^а ^б Ричард П. Брент (2020), Братья Борвейн, Пи и годовое собрание акционеров , Springer Proceedings in Mathematics & Статистика, vol. 313, arXiv : 1802.07558 , doi : 10.1007/978-3-030-36568-4 , ISBN 978-3-030-36567-7 , S2CID 214742997

[11] Соренсон, Дж. (1994). «Два быстрых алгоритма НОД». Журнал алгоритмов . 16 (1): 110–144. дои : 10.1006/jagm.1994.1006 .

[12] Крэндалл, Р.; Померанс, К. (2005). «Алгоритм 9.4.7 (двоично-рекурсивный НОД Стеле-Циммермана)» . Простые числа - вычислительная перспектива (2-е изд.). Спрингер. стр. 471–3. ISBN 978-0-387-28979-3 .

[13] Мёллер Н (2008). «Об алгоритме Шёнхаге и вычислении субквадратичных целых НОД» (PDF) . Математика вычислений . 77 (261): 589–607. Бибкод : 2008MaCom..77..589M . дои : 10.1090/S0025-5718-07-02017-0 .

[14] Бернштейн, DJ «Более быстрые алгоритмы для поиска неквадратных чисел по модулю наихудших целых чисел» .

[15] Брент, Ричард П.; Циммерманн, Пол (2010). "Ан $O(M(n)\log n)$ Алгоритм для символа Якоби» . Международный симпозиум по алгоритмической теории чисел . Springer. стр. 83–95. arXiv : 1004.2091 . doi : 10.1007/978-3-642-14518-6_10 . ISBN 978-3-642-14518-6 . S2CID 7632655 .

[16] Борвейн, П. (1985). «О сложности вычисления факториалов». Журнал алгоритмов . 6 (3): 376–380. дои : 10.1016/0196-6774(85)90006-9 .

[Lenstra19-17] Ленстра-младший, HW ; Померанс, Карл (2019). «Тестирование простоты с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–69. дои : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 .

[tao-aks-18] Тао, Теренс (2010). «1.11 Тест на простоту АКС» . Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том. 117. Американское математическое общество. стр. 82–86. дои : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4 . МР 2780010 .

[morain-19] Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений . 76 (257): 493–505. arXiv : math/0502097 . Бибкод : 2007MaCom..76..493M . дои : 10.1090/S0025-5718-06-01890-4 . МР 2261033 . S2CID 133193 .

[PSW-20] Померанс, Карл ; Селфридж, Джон Л .; Вагстафф-младший, Сэмюэл С. (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹ Математика (PDF) . вычислений . 35 (151): 1003–26. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .

[lpsp-21] Бэйли, Роберт; Вагстафф-младший, Сэмюэл С. (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . МР 0583518 .

[monier-22] Jump up to: Перейти обратно: ^а ^б Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты» . Теоретическая информатика . 12 (1): 97–108. дои : 10.1016/0304-3975(80)90007-9 . МР 0582244 .

[aw20-24] Алман, Джош; Уильямс, Вирджиния Василевска (2020), «Усовершенствованный лазерный метод и более быстрое умножение матриц», 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021) , arXiv : 2010.05846 , doi : 10.1137/1.9781611976465.32 , S2CID 2 22290442

[25] Дэви, AM; Стотерс, AJ (2013), «Улучшенная оценка сложности матричного умножения», Proceedings of the Royal Society of Edinburgh , 143A (2): 351–370, doi : 10.1017/S0308210511001648 , S2CID 113401430

[26] Василевска Уильямс, Вирджиния (2014), Преодоление барьера Копперсмита-Винограда: умножение матриц в O (n ^2.373) время

[27] Ле Галль, Франсуа (2014), «Степень тензоров и быстрое умножение матриц», Труды 39-го Международного симпозиума по символическим и алгебраическим вычислениям — ISSAC '14 , стр. 23, arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L , doi : 10.1145/2608628.2627493 , ISBN 9781450325011 , S2CID 353236

[Le_Gall-28] Jump up to: Перейти обратно: ^а ^б Ле Галль, Франсуа; Уррутия, Флорен (2018). «Улучшенное умножение прямоугольных матриц с использованием степеней тензора Копперсмита-Винограда». В Чумае, Артур (ред.). Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики. дои : 10.1137/1.9781611975031.67 . ISBN 978-1-61197-503-1 . S2CID 33396059 .

[29] Найт, Филип А. (май 1995 г.). «Быстрое умножение прямоугольной матрицы и QR-разложение» . Линейная алгебра и ее приложения . 221 : 69–81. дои : 10.1016/0024-3795(93)00230-w . ISSN 0024-3795 .

[30] Роте, Г. (2001). «Алгоритмы без делений для определителя и пфаффиана: алгебраические и комбинаторные подходы» (PDF) . Вычислительная дискретная математика . Спрингер. стр. 119–135. ISBN 3-540-45506-Х .

[31] Ахо, Альфред В .; Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1974). «Теорема 6.6». Проектирование и анализ компьютерных алгоритмов . Аддисон-Уэсли. п. 241. ИСБН 978-0-201-00029-0 .

[32] Фрели, Дж. Б.; Борегар, РА (1987). Линейная алгебра (3-е изд.). Аддисон-Уэсли. п. 95. ИСБН 978-0-201-15459-7 .

[33] Кон, Генри; Кляйнберг, Роберт; Сегеди, Балаж; Уманс, Крис (2005). «Теоретико-групповые алгоритмы умножения матриц». Материалы 46-го ежегодного симпозиума по основам информатики . IEEE. стр. 379–388. arXiv : math.GR/0511460 . дои : 10.1109/SFCS.2005.39 . ISBN 0-7695-2468-0 . S2CID 6429088 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[номер 1]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]