Вычисление факториала больших количеств в C

Ни один стандартный тип данных C не сможет точно обрабатывать числа размером до 100 !. Ваш единственный вариант - использовать целочисленную арифметику произвольной точности , либо через библиотеку, либо самостоятельно.

Если это просто какой-то хобби-проект, я бы посоветовал попробовать его самостоятельно. Это забавное упражнение. Если это связано с работой, используйте уже существующую библиотеку.

Самый большой тип данных C, который вы обычно получаете, - это 64-битное целое число. 100! имеет порядок 10 ¹⁵⁷ , что требует большей части 500 бит для точного сохранения в виде целого числа.

Не используйте рекурсивный алгоритм. Я думаю, он очень медленный, даже если он кэширован, он будет медленным. Это просто то, что вы должны учитывать.

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

double print_solution(int n)
{
    double rval = 1;
    unsigned int i;

    for( i = 1; i <= n; i++ ) {
        rval *= i;
    }

    return rval;

}

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

В дополнение к советам других я бы посоветовал ознакомиться с ограничениями хранилища основных типов (int, long, long long, ...) для любого компьютера / платформы, на которой вы Использую. («Если сомневаетесь, распечатайте больше!»)

На одном из предыдущих плакатов говорилось о 80-битном пределе точности, но это характерно для ЦП x86.

Другой человек несколько раз цитировал ISO C90, хотя C99 является последним стандартом; даже если многие компиляторы не полностью реализовали C99, вы, вероятно, обнаружите, что они, очень-очень вероятно, по крайней мере, имеют поддержку long long, что должно соответствовать> = 64-битной точности.

100! = 933262154439441526816992388562667004907159682643816214685929 6389521759999322991560894146397156518286253697920827223758251185210 916864000000000000000000000000

Вы не можете представить такое большое число с помощью int или long.

Я думаю, это потому, что вы выходите за пределы диапазона int, который составляет прибл. 2 миллиарда. Вы можете получить до 4 миллиардов, если используете unsigned int, но помимо этого вы должны использовать библиотеку bigint .

вы можете попробовать использовать тип "unsigned long long", но это максимум, который вы можете получить с помощью встроенных типов. Я бы предложил (как уже упоминал Клетус) либо использовать известную реализацию больших чисел, либо написать ее самостоятельно. "Хорошее упражнение" x 2.

вот что я сделал, чтобы разгадать загадку Google несколько лет назад он использовал библиотеку GMP http://gmplib.org/ :

#include <stdio.h>
#include "gmp.h"

void fact(mpz_t r,int n){
    unsigned int i;
    mpz_t temp;
    mpz_init(temp);
    mpz_set_ui(r,1);
    for(i=1;i<=n;i++){
        mpz_set_ui(temp,i);
        mpz_mul(r,r,temp);
    }
    mpz_clear(temp);
}
int main(void) {
    mpz_t r;
    mpz_init(r);
    fact(r,188315);
    /* fact(r,100); */
    gmp_printf("%Zd\n",r);
    mpz_clear(r);
    return(0);
}

gcc -lgmp -o fact fact.c

./ fact

Однако все говорят вам правильный ответ еще пара моментов.

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

2. Я знаю, что это, вероятно, пример из учебника или сайта примеров, но выполнение неограниченной рекурсии в какой-то момент вас укусит. У вас есть рекурсивное решение для того, что по сути является итеративным процессом. Вы поймете, почему этот сайт назван именно так, когда вы попытаетесь запустить свою программу с большими значениями (попробуйте 10000).

Простой итерационный подход выглядит следующим образом

  int answer, idx;

  for (answer = 1, idx = 1; idx <= no_of_inputs; idx++ ) {
    answer = answer * idx;
  }
  printf("Factorial of %3d =  %d\n", no_of_inputs, answer);

Факториал 100 огромен, если быть точным, это 93326215443944152681699238856266700490715968264381621468592963895217 59999322991560894146397615651828625369792082722375825118521091686400 00000000000000000000.

Возможно, вам стоит использовать библиотеку bignum, например GMP . У него хорошая документация, довольно последовательный интерфейс, скорость и, если вы используете Linux, в вашем дистрибутиве, вероятно, есть пакет (я думаю, что мой устанавливает его по умолчанию)

Чтобы приблизительно вычислить факториалы больших чисел вы можете использовать следующим образом:

n! =  n * (n-1)!
so log(n!) = log(n) + log(n-1!)

Теперь вы можете использовать динамическое программирование для вычисления журнала (n!) и вычисления
п! как (основание) ^ (логарифм)

Если вы хотите использовать только стандартные типы данных и вам не нужен точный ответ, вычислите логарифм n! вместо n! сам. Логарифм n! легко помещается в двойной (если n не велико).

Если вы не хотите использовать библиотеку bigint, лучшее, что вы можете сделать с stdlib, - это использовать long double и tgammal () из math.h :

long double fact(unsigned n)
{
    return tgammal(n + 1);
}

Это даст вам 100! с точностью до 18 десятичных знаков на x86 (то есть 80-битное long double ).

Точная реализация тоже не такая уж сложная:

#include <math.h>
#include <stdio.h>
#include <string.h>

void multd(char * s, size_t len, unsigned n)
{
    unsigned values[len];
    memset(values, 0, sizeof(unsigned) * len);
    for(size_t i = len; i--; )
    {
        unsigned x = values[i] + (s[i] - '0') * n;
        s[i] = '0' + x % 10;
        if(i) values[i - 1] += x / 10;
    }
}

void factd(char * s, size_t len, unsigned n)
{
    memset(s, '0', len - 1);
    s[len - 1] = '1';
    for(; n > 1; --n) multd(s, len, n);
}

int main(void)
{
    unsigned n = 100;
    size_t len = ceill(log10l(tgammal(n + 1)));
    char dstr[len + 1];
    dstr[len] = 0;
    factd(dstr, len, n);
    puts(dstr);
}

Скорее всего, это связано с переполнением. Вам нужен способ представления больших чисел ( unsigned long long не покрывает даже 25!).