factorial-1.2.1.c

/* ############  Fábio Perez - fabio.perez [a] students.ic.unicamp.br - Unicamp 2010 ############ */
/* Este programa calcula fatoriais de grandes números. Neste caso, até 1800, mas alterando os     */
/* valores de MAX, podemos chegar a números maiores, com perda no tempo de cálculo. Para o cálculo*/
/* de N!, devemos estar cientes de que N * MAX < 18446744073709551615 para que o algoritmo        */
/* funcione. Caso contrário, estouraria o valor de um 'unsigned long long int'. Ao reduzirmos o   */
/* valor de MAX, podemos aumentar o valor de N, mas com uma certa perda na velocidade de execução */
/* e na memória consumida. */

#include <stdio.h>

#define MEM 4000                             /* Tamanho do vetor de LLU (unsigned long long int). */
#define TOKEN 18446744073709551615LLU      /* Valor máximo assumido por um LLU. Necessário para o */
                                           /*      programa saber quando chegou ao fim da matriz. */
#define MAX 10000000000000LLU                        /* Para MAX = 10^Y, use '%0Yd.' na linha 62. */

typedef unsigned long long int NUMERO;

void Normalize(NUMERO * num) {
  short int i;
  NUMERO tmp;

  for (i = 0 ; ; i++) {
    tmp = num[i];
    if (tmp < MAX) continue;                        /* Verifica se é necessário normalizar a casa.*/
    if (num[i] / MAX  == 0 && num[i+1] == TOKEN) break;   /* Verifica se chegou ao fim da matriz. */

    num[i] = tmp % MAX;
    if (tmp / MAX != 0 && num[i+1] == TOKEN) { /* Se a casa a ser normalizada é a última do número*/
      num[i+1] = 0;                                                         /* Zera a última casa */
      num[i+2] = TOKEN;                  /* Atribui a próxima casa como sendo o final do número.  */
    }
    num[i+1] += tmp / MAX;
  }
}

void Factorial (int n, NUMERO * num) {
  int i, size;

  for(size = -1; n != 1 && n != 0; n--) {
    if (n == 1 || n == 0) return;                                                    /* Caso base */
    for (i = 0 ; num[i] != TOKEN ; size++, i++);                   /* Determina tamanho do número */
    for (i = 0; size >= 0; size--, i++) {
      num[size] *= n;
      if (num[size] >= MAX) Normalize(num);
    }
  }
}

int main () {
  NUMERO num[MEM];
  int n, i, m;

  scanf("%d", &m);                                       /* Lê o número de valores a serem lidos. */
  for (; m > 0; m--) {
    for (i = 0; i < MEM; i++) num[i] = 0;                                         /* Zera matriz. */
    num[0] = 1;                           /* Atribui 1 ao valor inicial à matriz (matriz padrão). */
    num[1] = TOKEN;                  /* Define o segundo campo da matriz como sendo o final dela. */
    scanf(" %d", &n);                                                  /* Lê n, para calcular n!. */
    Factorial(n, num);                                                /* Chama a função fatorial. */
    for (n = -1, i = 0; num[i] != TOKEN; n++,i++);        /* Verifica número de campos do número. */
    printf("%llu", num[n]);     /* Imprime primeira parte do número, omitindo os primeiros zeros. */
    for (n--; n >= 0; n--)             /* Percorre todo campo do número, imprimindo seus valores. */
                  printf("%013llu", num[n]); /* %0Yd imprime Y dígitos do campo, incluindo zeros. */
    printf("\n");
  }
return 0;
}