Перестановка с повторением: предотвращение переполнения

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

Они известны как полиномиальные коэффициенты, которые я буду обозначать m(a,b,...).

И вы можете эффективно вычислить их, избегая переполнения, используя это тождество (что должно быть довольно просто доказать):

m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ...
m(0,0,0,...) = 1 // base case
m(anything negative) = 0 // base case 2

Тогда это просто вопрос использования рекурсии для вычисления коэффициентов. Обратите внимание: чтобы избежать экспоненциального времени выполнения, вам нужно либо кэшировать результаты (чтобы избежать пересчета), либо использовать динамическое программирование.

Чтобы проверить переполнение, просто убедитесь, что суммы не переполнятся.

И да, очень плохая идея использовать библиотеки произвольной точности для выполнения этой простой задачи.

Самый безопасный способ переполнения - это способ, предложенный Дейвом. Вы находите показатель степени, с которой простое число p делит n! путем суммирования

m = n;
e = 0;
do{
    m /= p;
    e += m;
}while(m > 0);

Вычтите показатели степени p при разложении на множители a! и т. д. Сделайте это для всех простых чисел <= n, и вы получите факторизацию полиномиального коэффициента. Это вычисление переполняется тогда и только тогда, когда переполняется окончательный результат. Но полиномиальные коэффициенты растут достаточно быстро, так что уже при достаточно малых n у вас будет переполнение. Для существенных вычислений вам понадобится библиотека bignum (если вам не нужны точные результаты, вы можете обойтись немного дольше, используя doubles).

Даже если вы используете библиотеку bignum, стоит не допустить, чтобы промежуточные результаты были слишком большими, поэтому вместо вычисления факториалов и деления огромных чисел лучше вычислять части последовательно,

n!/(a! * b! * c! * ...) = n! / (a! * (n-a)!) * (n-a)! / (b! * (n-a-b)!) * ...

и чтобы вычислить каждый из этих факторов, возьмем второй для иллюстрации,

(n-a)! / (b! * (n-a-b)!) = \prod_{i = 1}^b (n-a+1-i)/i

рассчитывается с

prod = 1
for i = 1 to b
    prod = prod * (n-a+1-i)
    prod = prod / i

Наконец, умножьте части. Это требует n делений и n + number_of_parts - 1 умножений, сохраняя промежуточные результаты умеренно небольшими.

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

Это сводит исходную задачу к вычислению биномиального коэффициента с контролем переполнения.

Обозначения: n! = prod(1,n) где prod вы можете догадаться, что делает.

Это очень просто, но сначала вы должны знать, что для любых двух положительных целых чисел (i, n > 0) это выражение является положительным целым числом:

prod(i,i+n-1)/prod(1,n)

Таким образом, идея состоит в том, чтобы разбить вычисление n! на небольшие куски и разделить как можно скорее.

С a, потом с b и так далее.

perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!)

Каждый из этих факторов является целым числом, поэтому, если perm не переполнится, ни один из его факторов не подойдет.

Хотя при расчете такого коэффициента может быть переполнение в числителе или знаменателе, но этого можно избежать, выполняя умножение в числителе, а затем деление попеременно:

prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b

Таким образом, каждое деление даст целое число.