:: алгоритмы  и методы ::
:: олимпиадные задачи ::
:: связь ::
:: форум ::
:: о сайте ::
:: ссылки ::

Path: Математика » Быстрые вычисления » Факториал
  Вычисление факториала



Рекурсивный алгоритм типа 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, где есть реальный выигрыш в скорости.

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

В этом случае имеет смысл оперировать именно с логарифмом факториала, который вычисляется (как видно, например, из исходника выше) гораздо проще и быстрее. Деление и умножение будут заменены разностью и суммой логарифмов. Если нужны реально эффективные вычисления, то такой путь при контроле точности вычислений, безусловно, предпочтительнее.

На более высоком уровне о вычислении обобщения факториала - гамма-функции можно прочитать в соответствующей статье.

Обсудить на форуме »


  Комментарии для веб-мастера






Автор: Без имени
Время: 29-03-04 06:31


  

  

Ваши комментарии. Вопросы будут удалены: для них есть форум.
Имя:
E-mail:
  


Copyright 2000-2002 © Ilia Kantor, при поддержке проекта MANUAL.RU

АлгоЛист на CD