- PVSM.RU - https://www.pvsm.ru -
Наткнувшись недавно на эту статью [1], я понял, что редко упоминаются способы вычисления факториала, отличные от банального перемножения последовательных чисел. Нужно эту ситуацию исправить.
Предлагаю рассмотреть «асимптотически наиболее быстрый» алгоритм вычисления факториала!
Для начала напомню, что факториал n — это произведение всех натуральных чисел от 1 до n (), при этом ;
Введём функцию, именуемую swinging factorial, следующим образом:
Данная дробь всегда будет целым числом по простой причине — она кратна центральному биномиальному коэффициенту , который равен
Разворачивая определение swinging factorial, мы получим новую рекуррентную формулу факториала:
Она будет особенно хороша, если мы научимся эффективно вычислять значения .
Обозначим как степень простого числа в примарном разложении . Тогда будет справедлива следующая формула:
Для последнего выражения воспользуемся тем фактом, что , и получим нужную нам формулу.
Как следствие, и . Если нечётно, то . Другие частные случаи:
$$display$$begin{array}{lrrl} (a)&lfloor n/2rfloor &< p leqslant & n & Rightarrow & l_p(nwr)=1\ (b)&lfloor n/3rfloor &< p leqslant & lfloor n/2rfloor & Rightarrow & l_p(nwr)=0\ (c)&sqrt{n} &< p leqslant & lfloor n/3rfloor & Rightarrow & l_p(nwr)=lfloor n/prfloor:mod:2\ (d)&2 &< p leqslant & sqrt{n} & Rightarrow & l_p(nwr) < log_2(n)\ (e)& & p = & 2 & Rightarrow & l_p(nwr) =sigma_2(lfloor n/2rfloor)\ end{array}$$display$$
здесь означает количество единиц в двоичном представлении числа . Все эти факты могут быть использованы для дополнительной оптимизации в коде. Доказательства я приводить не буду, при желании вы легко сможете получить их самостоятельно.
Теперь, зная степени всех простых делителей , у нас есть способ вычисления swinging factorial:
Можно показать, что вычисление имеет сложность . Как ни странно, вычисление имеет ту же сложность (в оценке используется алгоритм Шёнхаге-Штрассена [3], отсюда и такая интересная трудоёмкость; доказательства по ссылке в конце статьи).
Несмотря на то, что формально перемножение чисел от 1 до n имеет ту же трудоёмкость, алгоритм PrimeSwing на практике оказывается самым быстрым.
// main function
public static BigInteger factorial(int n) {
return factorial(n, primes(n));
}
// recursive function with shared primes array
private static BigInteger factorial(int n, int[] primes) {
if (n < 2) return BigInteger.ONE;
BigInteger f = factorial(n / 2, primes);
BigInteger ps = primeSwing(n, primes);
return f.multiply(f).multiply(ps);
}
// swinging factorial function
private static BigInteger primeSwing(int n, int[] primes) {
List<BigInteger> multipliers = new ArrayList<>();
for (int i = 0; i < primes.length && primes[i] <= n; i++) {
int prime = primes[i];
BigInteger bigPrime = BigInteger.valueOf(prime);
BigInteger p = BigInteger.ONE;
int q = n;
while (q != 0) {
q = q / prime;
if (q % 2 == 1) {
p = p.multiply(bigPrime);
}
}
if (!p.equals(BigInteger.ONE)) {
multipliers.add(p);
}
}
return product(multipliers, 0, multipliers.size() - 1);
}
// fast product for the list of numbers
private static BigInteger product(List<BigInteger> multipliers, int i, int j) {
if (i > j) return BigInteger.ONE;
if (i == j) return multipliers.get(i);
int k = (i + j) >>> 1;
return product(multipliers, i, k).multiply(product(multipliers, k + 1, j));
}
// Eratosthenes sieve
private static int[] primes(int upTo) {
upTo++;
if (upTo >= 0 && upTo < 3) {
return new int[]{};
}
int length = upTo >>> 1;
boolean sieve_bool[] = new boolean[length];
for (int i = 1, iterations = (int) Math.sqrt(length - 1); i < iterations; i++) {
if (!sieve_bool[i]) {
for (int step = 2 * i + 1, j = i * (step + 1); j < length; j += step) {
sieve_bool[j] = true;
}
}
}
int not_primes = 0;
for (boolean not_prime : sieve_bool) {
if (not_prime) not_primes++;
}
int sieve_int[] = new int[length - not_primes];
sieve_int[0] = 2;
for (int i = 1, j = 1; i < length; i++) {
if (!sieve_bool[i]) {
sieve_int[j++] = 2 * i + 1;
}
}
return sieve_int;
}
Автор: ibessonov
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/254029
Ссылки в тексте:
[1] эту статью: https://habrahabr.ru/post/327544/
[2] теоремой Лежандра о простых множителях факториала: https://en.wikipedia.org/wiki/Legendre%27s_formula
[3] алгоритм Шёнхаге-Штрассена: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%83%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%A8%D1%91%D0%BD%D1%85%D0%B0%D0%B3%D0%B5_%E2%80%94_%D0%A8%D1%82%D1%80%D0%B0%D1%81%D1%81%D0%B5%D0%BD%D0%B0
[4] страница с различными алгоритмами вычисления факториала;: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
[5] детальное описание алгоритма из статьи (и не только).: http://www.luschny.de/math/factorial/SwingIntro.pdf
[6] Источник: https://habrahabr.ru/post/323770/
Нажмите здесь для печати.