Calcular Fatorial de Números Gigantes em C

Breve solução para cálculo do fatorial para um inteiro positivo dado utilizando um código em C e a aproximação de Stirling.

O fatorial n! é definido para um inteiro positivo n como

$$n! = n (n - 1) · ... · 2 · 1.$$

Assim, por exemplo, $3! = 3 · 2 · 1 = 6$. O caso especial $0!$ é definido para ter valor $0! = 1$, consistente com a interpretação combinatória de haver exatamente uma maneira de organizar zero objetos (ou seja, há uma única permutação de zero elementos, ou seja, o conjunto vazio Ø).

Agora, tem-se a pergunta - como calcular o fatorial de 100 utilizando um código escrito em C/C++?

Note que o resultado de 100 fatorial possui cerca de 158 dígitos e, mesmo utilizando a variável long long int, não é possível armazenar seu resultado.

Portanto, a seguir tem-se uma possível solução simples, onde fazemos uso de um vetor para armazenar cada um dos dígitos do resultado e utiliza-se a técnica de "dividir para conquistar" para realizar a multiplicação de cada um dos fatores. Mas, antes, vejamos uma técnica para verificar o número de dígitos e prever o "tamanho" do número a ser calculado.

Calculando o Número de Dígitos do Resultado

Pode-se utilizar a seguinte fórmula para encontrar-se o número de algarismos de um valor inteiro qualquer.

$$\textrm{Número de dígitos de }n = (\textrm{Parte inteira positiva de }\log n) + 1$$.

Dessa forma, utilizando-se da teoria de logaritmos, pode-se reescrever a fórmula acima da seguinte forma:

$$\textrm{Número de dígitos de }n = (\textrm{Parte inteira positiva de }\frac{\ln n}{\ln 10}) + 1$$.

Por outro lado, fazendo-se uso da aproximação de Stirling, tem-se

$$n! \approx \sqrt{2\pi n } \left(\frac{n}{e} \right)^n$$,

ou seja,

$$ \ln{n!} \approx \ln\left[\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right] = \frac{\ln(2\pi n)}{2} + n(\ln{n} - 1) =\frac{\ln{2\pi} + (1 + 2n)\ln{n} - 2n}{2}.$$

Portanto, sabendo-se que n! corresponde a um número inteiro positivo, vem

$$\textrm{Número de dígitos de }n! = \left[\textrm{Parte inteira positiva de }\displaystyle\frac{\displaystyle\frac{\ln{2\pi} + (1 + 2n)\ln{n} - 2n}{2}}{\ln{10}}\right] + 1. $$

isto é,

$$\textrm{Número de dígitos de }n! = \left[\textrm{Parte inteira positiva de }\displaystyle\frac{1}{2}\log{2\pi n} + n \log\left(\displaystyle\frac{n}{e}\right] \right) + 1.$$

Portanto, supondo-se, por exemplo, n = 9 (onde 9! = 362880), tem-se

$$\textrm{Número de dígitos de }9!$$

$$\textrm{Número de dígitos de }9! = \left[\textrm{Parte inteira positiva de }\displaystyle\frac{1}{2}\log{(2 \cdot \pi \cdot 9)} + 9 \log\left(\displaystyle\frac{9}{e}\right] \right) + 1 = 6.$$

Algoritmo & Código em C

A seguir, tem-se uma breve descrição do algoritmo utilizado para encontrar a solução em C.

1. Recebe-se o número e armazena numa variável "number".
2. Calcula utilizando a fórmula acima o número de dígitos do resultado (estimado).
3. Cria-se um vetor "result[MAX_DIGITS_NUMBER]", onde MAX_DIGITS_NUMBER corresponde ao número calculado acima de dígitos do resultado a serem armazenados.
4. Inicializa-se o vetor acima com um único digito, isto é, o número 1. E, portanto, também se inicia com dcounter = 1 e carry = 0.
5. Faça o seguinte para todos os números inteiros positivos "i", onde i = 1 até "number".
1. ...Faça o seguinte para todos os números inteiros positivos "j", onde j = 0 até "dcounter".
1. ......Multiplique "i" por "result[j]" e some com "carry", em seguida, atualize "result[j]" e "dcounter", de modo a armazenar o resultado calculado acima.

Observe, que para calcular o número "i" com o número armazenado em result[j], faz-se uso da ideia de multiplicação bastante conhecida e que aprendemos na escola. Começa-se multiplicando-se "i" com cada dígito de result[j], onde tais dígitos são multiplicados a partir do dígito mais à direita par ao dígito mais à esquerda, e calcula-se o número de transporte ("o que vai") que é adicionado à próxima multiplicação. E assim por diante. Dessa forma, organiza-se o número em result[j] da forma inversa, de modo que ao exibir o resultado do número calculado, faz-se necessário apresentá-lo na ordem inversa, conforme melhor exemplificado no código em C a seguir.

/*************************************************************************
 * big-fac.c
 * 
 * Project:	Big-Positive-Numbers Factorial Simple Calculator
 * Author:	@jndgomes
 * 
 * THIS SOFTWARE IS PROVIDED BY AUTHORS "AS IS" AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE. 
 * 
 ************************************************************************/
 
#include <stdio.h>
#include <math.h>

int main()    
{
	// Variável indicativa do número máximo de digitos do resultado
	int MAX_DIGITS_NUMBER;
	
	// Variáveis auxiliares
	int i, j, number, dcounter, carry, tmp;
		
	// Realiza a leitura do número
	printf("Calculadora de Fatorial\n\n");
	printf("Digite um numero (Exemplo: 1993): ");
	scanf("%d", &number);

	// Calcula o numero de digitos do resultado
	MAX_DIGITS_NUMBER = (int)(
		(log(2 * 3.141592653) + log(number) + 2 * number * ((log(number)) - 1)) / (2 * log(10))
		) + 1;	

	// Vetor com capacidade de armazenar "MAX_DIGITS_NUMBER" digitos.
	char result[MAX_DIGITS_NUMBER]; 
		
	// Inicializa o vetor com apenas 1 digito, o digito 1
	result[0] = 1;
		
	// Inicializa o contador de digitos do resultado, isto é,
	// o resultado já contém um digito - o digito 1 acima.
	dcounter = 1;
	
	// Inicializa a variável de transporte com o valor zero
	carry = 0;
		
	// Imprime uma linha em branco
	puts("");
	
	for (i = 1; i <= number; i++)
	{
		for (j = 0; j < dcounter; j++)
		{
			// tmp contém o produto "digito * digito"
			tmp = result[j] * i + carry;
			// result[j] contém o digito armazenado na posição j
			result[j] = tmp % 10;			
			// carry contém o valor de transporte que será armazenado
			// nos últimos índices
			carry = tmp / 10;
		}
			
		// Laço de repetição que armazena o valor de transporte no vetor
		while(carry > 0)
		{
			result[dcounter] = carry % 10;
			carry /= 10;
			dcounter++;
		}
		
		// Imprime uma mensagem informando quantos digitos foram 
		// calculados até o momento
		printf("\r%d digitos calculados...", dcounter);
	}
		
	// Imprime uma linha em branco
	puts("");
		
	// Imprime o resultado da operação
	printf("\nFatorial de %d e igual a:\n\n", number);
	for (i = dcounter - 1; i >= 0; i--)
	{
		printf("%d", result[i]);
	}
	
	// finaliza a função principal corretamente
	return(0);
}

Exemplo

A seguir, tem-se o resultado para o cálculo de 1993!, como exemplo.