Pull to refresh

Comments 21

Теперь, зная степени всех простых делителей n≀, у нас есть способ вычисления swinging factorial.


С какой сложностью нам достается это знание?

Простых чисел от 1 до n всего O(n / log n), вычисление lp происходит за O(log n).
Сложностью же перемножения простых чисел в соответствующих степенях будет O(n (log n)2 log log n) — это уже не очевидная оценка, её доказательство есть по второй ссылке.

Асимптотику распределения простых чисел я знаю.
Я правильно понимаю, что придется хранить или генерировать таблицу простых чисел от 2 до n/2?
Какова трудоемкость детерминированного алгоритма теста на простоту?

Не совсем, понадобится таблица простых чисел от 2 до n.
Решето Эратосфена составляется за O(n * log log n), это меньше, чем время вычисления факториала. Отдельного способа проверки на простоту алгоритм не требует.

Прекрасно. Как-то я упустил, что сложность решета ниже сложности вычисления факториала.
Мне кажется, самый практичный метод вычисления факториала

array[0, 1, 2, 6, 24, 120, ...]

Простите за серость, а зачем нужно вычислять большие факториалы? Криптография? Комбинаторика? Ряды Тейлора? Собеседование в Гугл?

Боюсь, что это вопрос не ко мне. Вероятнее всего различные алгоритмы вычисления факториала имеют соревновательный характер.
Хранить массив может быть очень затратно по памяти, особенно если нужны значения порядка 1000000! (вдруг они кому-то нужны). На практике я такого не встречал и сам всегда хранил кэшированные значения в обычном массиве (во время решения задач по программированию).

Факториалы чисел порядка миллионов иногда встречаются в олимпиадном программировании в задачах на комбинаторику, где после вывода формулы решения оказывается, что нужно считать большие биномиальные коэффициенты по какому-нибудь простому модулю. Но даже в этом случае проще сначала посчитать все прямые и обратные факториалы, а потом уже из них собирать то, что нужно, более сложный алгоритм вычисления факториалов мне лично ни разу не пригодился.
Несмотря на то, что формально перемножение чисел от 1 до n имеет ту же трудоёмкость, алгоритм PrimeSwing на практике оказывается самым быстрым.

Предположим, что разделим числа на две половины, рекурсивно вычислим произведение и перемножим половины. Сложность у этого метода ~M(n*log(n))*log(n), что хуже ~M(n*log(n)) у PrimeSwing. Или как предлагается перемножать?
Извиняюсь, действительно у меня в этом моменте ошибка. Вычисление с помощью PrimeSwing имеет трудоёмкость как у простого перемножение двух чисел порядка n!, а не вычисления n! стандартным способом. Сейчас внесу обновление в статью.
Спасибо!
Стоит отметить, что статья имеет практическую направленность, но согласно вики:
Метод Шёнхаге — Штрассена считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был заявлен новый метод с лучшей оценкой сложности умножения.[3] На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка 10^10000-10^40000.
Таким образом становится актуальным вопрос о константе в оценке.
Интересно вышло, алгоритм PrimeSwing был опубликован в 2008-м, автор уже мог знать о более оптимальном способе умножения чисел.
Если я верно понял, автор производил вычисления факториалов примерно до 1000000, то есть результаты были не настолько большими, чтобы использовать Алгоритма Фюрера (если верить википедии). А так да, теоретическую оценку наверняка можно улучшить.
На практике я не заморачивался и использовал то умножение, какое было реализовано за меня в BigInteger.
Спасибо за замечание.
В BigInteger (по крайней мере раньше было) реализовано умножение столбиком (за квадрат). И не забудьте еще расходы времени на перевод из десятичной в двоичную СС.
В Java используются более быстрые алгоритмы. А перевод для вывода — если печатать в консоль — да, займет время :)
Хорошо про умножение с практической точки зрения написано здесь
Стать интересная, не знал что и здесь простые числа применяются. На практике мне не встречались задачи где нужно было вычислять просто факториалы чисел больше 20-30 (например в uint64_t влезает 20, а вот 21! уже нет, зато в double влезает, хоть и с погрешностью). Встречались отношения (дроби) больших факториалов (комбинаторные сочетания Cmn для близких чисел и размещения Amn для сильно разных чисел), порядка 300-т. Но в этих задачах я решал просто разложением на простые множители всех чисел произведения в числителе и знаменателе, подсчёту количества таких множителей в числителе и знаменателе, сокращению, и дальнейшему вычислению отношения (там обычно много чего сокращалось и части дроби «влазили» с малой погрешностью в тип double, но чаще вообще в uint64_t).

Зачем считать для цешек факториалы, если есть треугольник паскаля?
Я могу оценить время на генерацию N строк как O(N^3).
В Вашем случае (N = 300) — пара минут максимум.

Зачем использовать треугольник Паскаля, если есть замечательное соотношение C(n, k) = C(n — 1, k — 1) * (n / k)? Вычисляется, в отличие от треугольника Паскаля, за O(k) операций над числами, а из операций потребуется только умножение и деление на короткое число (причем деление всегда гарантированно нацело будет).

Ух ты ж.
Спасибо, отличное соотношение!

В этом алгоритме мы по сути выделяем большой множитель, являющийся квадратом. То есть A[k] = A[k+1]^2 * B[k+1], A[0] = n!, для вычисления A[k] мы вычисляем A[k+1], B[k+1]. Но мы можем выделить ещё больший множитель, оставляя в B[k+1] только произведение простых, входящие в A[k] нечётных степенях. Кажется, это должно работать ещё быстрее, хотя разница должна быть невелика.
«в примарном разложении» — должно быть «в разложении на простые множители». «Примарное разложение» это немного другое (см. теорему Ласкера).
Sign up to leave a comment.

Articles