Cálculo fatorial de grandes números em C

No meu código C, eu quero calcular o fatorial para números no intervalo de 1 a 100. Para números pequenos, a function funciona, mas para números maiores, por exemplo, 100! ele retorna um resultado incorreto. Quaisquer maneiras de lidar fatorial de grandes números em C? O compilador que estou usando é o gcc v4.3.3. Meu código é o seguinte:

#include  #include  double print_solution(int); int main(void) { int no_of_inputs,n ; int ctr = 1; scanf("%d",&no_of_inputs); //Read no of inputs do { scanf("%d",&n); //Read the input printf("%.0f\n",print_solution(n)); ctr++; }while(ctr <= no_of_inputs); return 0; } double print_solution(int n) { if(n == 0 || n == 1) return 1; else return n*print_solution(n-1); } 

Nenhum tipo de dados C padrão manipulará com precisão números tão grandes quanto 100. Sua única opção se usar aritmética inteira de precisão arbitrária , seja por meio de uma biblioteca ou feita por você mesmo.

Se isso é apenas um projeto de hobby, sugiro tentar você mesmo. É uma espécie de exercício divertido. Se isso for relacionado ao trabalho, use uma biblioteca pré-existente.

O maior tipo de dados C que você normalmente obterá é um inteiro de 64 bits. 100! é da ordem de 10 157 , que leva a melhor parte de 500 bits para armazenar com precisão como um inteiro.

100 fatorial é enorme, para ser preciso é 93326215443944152681699238856266700490715968264381621468592963895217 59999322991560894146397615651828625369792082722375825118521091686400 00000000000000000000.

Talvez você deva usar uma biblioteca bignum como o GMP . Tem documentos legais, uma interface bastante consistente, velocidade e se você está no Linux sua distro provavelmente tem um pacote (eu acho que o meu instala por padrão)

Para calcular aproximadamente os fatoriais de números grandes, você pode seguir este caminho:

 n!  = n * (n-1)!
 então log (n!) = log (n) + log (n-1!)

Agora você pode usar a programação dinâmica para calcular log (n!) E calcular
n! como (base) ^ (log-value)

Se você não quiser usar uma biblioteca bigint, o melhor que você pode fazer com o stdlib é usar long double e tgammal() em math.h :

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

Isso vai te dar 100! com uma precisão de 18 casas decimais em x86 (ou seja, 80 bits de long double ).

Uma implementação exata não é tão complicada:

 #include  #include  #include  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); } 

Todo mundo está dizendo a resposta correta, no entanto, um par de outros pontos.

  1. Sua idéia inicial de usar um duplo para obter um intervalo mais amplo não está funcionando porque um duplo não pode armazenar esses dados com precisão. Pode fazer os cálculos, mas com muito arredondamento. É por isso que existem bibliotecas bigint.

  2. Eu sei que este é provavelmente um exemplo de um tutorial ou site de exemplos, mas fazer recursion ilimitada vai te morder em algum momento. Você tem uma solução recursiva para o que é essencialmente um processo iterativo. Você entenderá porque este site é nomeado como é quando você tenta executar seu programa com valores maiores (Tente 10000).

Uma abordagem iterativa simples é a seguinte

  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); 

isso é o que eu fiz para resolver um enigma do Google há alguns anos, ele usa a biblioteca GMP http://gmplib.org/ :

 #include  #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 fato fact.c

./facto

você pode tentar usar o tipo “long long unsigned”, mas isso é o máximo que você pode obter com os tipos incorporados. Eu sugeriria (como Cletus já mencionou) ir com uma implementação conhecida de grandes números, ou escrever um para você mesmo. “é um bom exercício” x 2.

Se você quiser usar apenas os tipos de dados padrão e não precisar da resposta exata, calcule o logaritmo de n! em vez de n! em si. O logaritmo de n! cabe facilmente em um double (a menos que n seja enorme).

Quaisquer maneiras de lidar fatorial de grandes números em C?

Como os fatoriais podem exceder rapidamente o intervalo de inteiros padrão de largura fixa e até mesmo os tipos de ponto flutuante como o double , o Código deve considerar um tipo de usuário que permita precisão inteira ilimitada para uma resposta exata .

Várias bibliotecas de precisão com números inteiros existem, mas se o código precisar de uma solução simples, considere o uso de uma string .

O abaixo não é rápido, nem consciente dos limites das matrizes, mas é ilustrativo da ideia. A conversão de '0'-'9' para / de 0-9 muito é um desperdício, mas isso permite uma debugging fácil passo a passo.

 #include  #include  #include  static char *strfact_mult(char *s, unsigned x) { unsigned sum = 0; size_t len = strlen(s); size_t i = len; while (i > 0) { sum += (s[--i] - '0') * x; s[i] = sum % 10 + '0'; sum /= 10; } while (sum) { len++; memmove(&s[1], s, len); s[i] = sum % 10 + '0'; sum /= 10; } return s; } char *str_fact(char *dest, unsigned n) { strcpy(dest, "1"); while (n > 1) { strfact_mult(dest, n--); } return dest; } void test_fact(unsigned n) { char s[1000]; printf("%3u %s\n", n, str_fact(s, n)); } int main(void) { test_fact(0); test_fact(4); test_fact(54); test_fact(100); } 

Saída

  0 1 4 24 54 230843697339241380472092742683027581083278564571807941132288000000000000 100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 

Eu acho que é porque você está transbordando o intervalo int, que é de aprox. 2 bilhões. Você pode obter até 4 bilhões se usar int não assinado, mas além disso você tem que usar a biblioteca bigint .

100! = 933262154439441526816992388562667004907159682643816214685929 6389521759999322991560894146397156518286253697920827223758251185210 916864000000000000000000000000

Você não pode representar um número tão grande com um int ou um longo.

Isto é certamente devido ao estouro. Você precisa de uma maneira de representar grandes números ( unsigned long long não cobrirá até 25!).

Além do conselho de outros, eu sugiro familiarizar-se com os limites de armazenamento dos tipos básicos (int, long, long long, …) para qualquer computador / plataforma que você esteja usando. (“Em caso de dúvida, imprima mais!”)

Um poster anterior se referia a um limite de precisão de 80 bits, mas isso é particular para uma CPU x86.

Outra pessoa citou várias vezes o ISO C90, embora o C99 seja o padrão mais recente; mesmo que muitos compiladores não tenham implementado completamente o C99, você provavelmente descobrirá que eles, muito provavelmente, pelo menos, terão suporte por muito tempo, o que deve corresponder a uma precisão de> = 64 bits.

Calcular grandes fatorials sem qualquer biblioteca externa

É realmente um problema antigo. Eu vejo a maioria das respostas sugerindo biblioteca externa ou resultado aproximado , mostrando limitação de memory. Mas, pense um pouco diferente – você nem sempre tem que usar integer ou double ou unsigned long long em programação para fazer matemática!


Eu usei int[] para calcular Big Factorials . Este pequeno código Java pode (teoricamente) descobrir fatorial de qualquer número

 public class BigFactorial { public static int[] calculateFactorial(int inputNumber) { int[] factorial = initializeFactorial(inputNumber); for(int i=inputNumber-1, j, k; i>0; i--){ for(j=factorial.length-1, k=0; factorial[j] >= 0; j--){ k += i*factorial[j]; factorial[j] = k%10; k /= 10; } factorial[j] = k%10; k /= 10; factorial[j-1] = k; for(j=0; factorial[j]<1; j++){ factorial[j] = -1; } } return factorial; } private static int[] initializeFactorial(int inputNumber){ int digits = (int) Math.ceil(inputNumber*Math.log10(inputNumber/2))+2; int[] factorial = new int[digits+1]; for(int i=0; i0; j--){ factorial[j] = i%10; i /= 10; } return factorial; } public static void showOutput(int[] factorial){ int i=0; while(factorial[i]<1){ i++; } for(; i 

Não use o algoritmo recursivo, eu acho, é super lento, mesmo que seja armazenado em cache, será lento. Isso é apenas algo que você deve considerar.

A razão para isso é que quando você chama fato (100) você não o executa 100 vezes, você realmente executa essa function 5050 vezes. O que é ruim, se for armazenado em cache, pode ser 100 vezes, no entanto, ainda é mais lento executar uma chamada de function com instruções if e executar um loop.

 double print_solution(int n) { double rval = 1; unsigned int i; for( i = 1; i < = n; i++ ) { rval *= i; } return rval; } 

Usando a aritmética de precisão arbitrária, você pode fazer com que ela seja muito alta; no entanto, você precisa usar uma biblioteca para fazer isso, ou pode criar sua própria biblioteca, mas isso levaria muito tempo para ser feito.