Рекурсивный алгоритм типа n! = n*(n-1)! неработоспособен. Вешать за такие надо. Памяти на стек требует громадное количество.
Школьный алгоритм очевиден.
N_factorial = 1;
for ( i = 1; i <= N ; ++i ) N_factorial *= i;
Если требуется вычислить очень длинный факториал - можно воспользоваться кустарной библиотекой длинных чисел, описанной здесь или более быстрым пакетом Freelipzip
Обращаю внимание на то, что при вычислениях происходит последовательное умножение длинного числа на обычное (из базового типа данных, например, long int). В результате алгоритм умножения имеет сложность O(m), m - длина числа, и прост в реализации.
#include "lip.h"
#define FACTSIZE 20000
void main()
{
long i;
verylong a=0,b=0;
zstart();
zintoz(1, &a);
for(i=1;i<=FACTSIZE;i++) zsmul( a, i, &a);
printf("length = %ld",(long)zslog(a, 10) +1);
}
© Radionov Alexey
Вот приближение десятичного логарифма факториала:
#include <math.h>
double log10factorial(double n)
{
return((-log(902961561600.0)+log(2.0)/2.0+log(0.3141592653589793E1)/2.0
+log(902961561600.0*n*n*n*n*n*n*n+75246796800.0*n*n*n*n*n*n
+3135283200.0*n*n*n*n*n-2421135360.0*n*n*n*n-207204480.0*n*n*n
+707957280.0*n*n+62961828.0*n-534703531.0)-13.0/2.0*log(n)
+n*log(n)-n)/log(10.0));
}
Целая часть этого покажет количество знаков числа-1, а с мантиссой можно работать.
Можно вычислять факториал как eln(n!), и это будет быстрее, чем прямое умножение. Но это не будет точное значение для больших значений n, где есть реальный выигрыш в скорости.
Тем не менее, часто(например, в вычислении биномиальных коэффициентов) нам нужен не сам факториал, а некое значение, получающееся в результате деления громадного факториала на другие числа того же порядка, и в результате получается небольшое число.
В этом случае имеет смысл оперировать именно с логарифмом факториала, который вычисляется (как видно, например, из исходника выше) гораздо проще и быстрее. Деление и умножение будут заменены разностью и суммой логарифмов. Если нужны реально эффективные вычисления, то такой путь при контроле точности вычислений, безусловно, предпочтительнее.
На более высоком уровне о вычислении обобщения факториала - гамма-функции можно прочитать в соответствующей статье.
Обсудить на форуме »
|
