Как программно посчитать n!

psm61

как посчитать n! ( имеется ввиду программная реализация, например на С) с абсолютной точностью, для любого n - практически как вычислить все его ненулевые разряды, количество нулей понятное дело считает легко.

tinka2302

Идиоты делают это рекурсией.
Остальные перемножают в цикле. А в чем, собственно, вопрос?

psm61

в том как тебе компьютер посчитает к примеру 100!, который имеет порядок 190
у компа ведь точность ограниченная, два в 32ой...

tinka2302

А, тогда понятно.
Когда-то сам такую фигню делал, перемножал столбиком
Насчет готовых библиотек не знаю, возможно есть.

h_alishov

 
у компа ведь точность ограниченная, два в 32ой...

Это если пользоваться целочисленным int. А если, например, использовать длинную арифметику, либо double (правда, в этом случае будет некоторая погрешность то никаких проблем не будет.
зы. А это не Чернопрак на ВМиК? Там такое задание три года назад точно было.

psm61

!
столбиком?

tinka2302

Ну да, а в чем проблема?
Я делал умножение столбиком двух чисел, а дальше в цикле.
Числа представлял как строки из цифр, длиной что-то около 10000, но если нужно, можно и больше заложить

tinka2302

double на больших числах дает очень большую погрешность.
У него максимальная точность на отрезке [0,1]

h_alishov

Относительная погрешность почти не меняется от порядка (в рамках разумного, разумеется). В некоторых задачах хватает и точности double. Но, конечно, не для задачи автора темы.

h_alishov

имеется ввиду программная реализация, например на С

Есть готовый алгоритм на C#. Пойдет?

psm61

пойдет, давай

disepa

Лучше используй Mathematica
100! = 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000\
00

h_alishov

Зы. Если тебе только уметь считать нужно, действительно, лучше установить Maple или Mathematica

vovatroff


как тебе компьютер посчитает к примеру 100!, который имеет порядок 190
Эмпирически мыслящие люди прологарифмировали бы факториал и поскладывали бы логарифмы натуральных чисел.

psm61

кому интересно, вот программка
#define MAX_DIGITS 1000
void factorial(int n)
{
int i;
int res[MAX_DIGITS];
memset(res,0,MAX_DIGITS*sizeof(int;
int num[n];
num[0]=2;
for( i=3;i<n;i++)
{
num_to_array(i,num);
len = multiply(i,res,len);
}

printf("%d! = ",n);
for (i=0;res[i]>0;i++){}
for( i--;i>=0;i--)
printf("%d",res[i]);
}
num_to_array(int i, int* num)
{
int k;
for(k=1; i/pow(10,k) > 0 ; k++)
num[k-1] = i % pow(10,k);
}
int multiply(int * num, int * res, int len)
{
int num2[len],num3[len], i,k;
memset(num3,0,len+1);
for( i = 0 ; num[i] > 0; i++)
{
num2[i] = ( res[k-i]*num[i]%pow(10,k-i+1)
num3[i] += num2[i];
for(k=i+1;res[k] >0;k++)
{
num2[k-i] = ( res[k-i]*num[i]%pow(10,k-i+1) + res[k-i-1]*num[i]/10)
num3[k-i] += num2[k-i];
}
num2[k] = res[k-i-1]*num[i]/10;
num3[k] += num2[k];
}

for( i = 0 ; num3[i] > 0; i++)
res[i]=num3[i];
}

zuzaka

строковое представление чисел, вроде, есть в разных готовых библиотеках
Оставить комментарий
Имя или ник:
Комментарий: