Calcular o fatorial de números gigantes em linguagem C
date
Apr 3, 2022
slug
como-calcular-fatorial-numeros-grandes-em-c
status
Published
tags
Tecnologia
Matemática
Algoritmos
summary
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 para evitar estouro de memória.
type
Post
O fatorial é definido para um inteiro positivo n como
Assim, por exemplo, . O caso especial 0! é definido para ter valor , 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.
Dessa forma, utilizando-se da teoria de logaritmos, pode-se reescrever a fórmula acima da seguinte forma:
Por outro lado, fazendo-se uso da aproximação de Stirling, tem-se
ou seja,
Portanto, sabendo-se que n! corresponde a um número inteiro positivo, vem
isto é,
Portanto, supondo-se, por exemplo, (onde ), tem-se
Número de dígitos de
Algoritmo & Código em C
#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 de 1993!
A seguir, tem-se o resultado para o cálculo de , como exemplo.
Foto: cálculo de 1993! utilizando código em C e a aproximação de Stirling.