Executando verificação de segurança...
3
Pab
3 min de leitura ·

Você sabe qual é exatamente o fatorial de 100? Não se preocupe, vamos descobrir nesse artigo!

Por que fazer algo assim?

Desde o meu primeiro contato com a lógica de programação, especificamente quando falamos de recursão, sempre há esse tal de fatorial. Toda vez que falamos dele, é mostrado para nós que a memória do computador tem limite e não consiguimos calcular esse fatorial de número grandes. Por exemplo: a calculadora que tenho em mãos, uma Benko BK-82MS, só calcula fatorial até o fatorial de 70. Em relação aos algoritmos que normalmente fazemos, em c, só é possível calcular até o fatorial de 65. Valores acima de 65 são retornados imediatamente com 0. Veja o código a seguir:

#include <stdio.h>

long long unsigned int factorial(unsigned int n) {
    long long unsigned int acumulator = 1;

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

    return acumulator;
}

int main() {

    printf("%llu\n", factorial(3)); // 6
    printf("%llu\n", factorial(6)); // 720
    printf("%llu\n", factorial(65)); // 9223372036854775808
    printf("%llu\n", factorial(66)); // 0

}

Em algum momento, enquanto estava no trono das ideias, surgiu-me a inquietante pergunta: Qual é o fatorial de 100?

O que é o fatorial de um número?

O fatorial de um número nada mais é que a multiplicação dos antecessores de um número inteiro positivo a até 1. Ou seja, se n é um número inteiro positivo, então: n! = n(n-1)(n-2)(n-3)...1

Bem simples, né?

E agora? Como calculariamos 100!?

Após muitos rabiscos, projeitei um algoritmo e uma estrutura de dados que capacitaria um computador o poder de calcular o fatorial de 100. Veja o repositório aqui

Aqui está um pouco de como foi feito:

A estrutura de dados

A estrura de dados definida para esse projeto é baseada em como fazemos operações com os número. Mas, em outro pronto de vista com uma pitada de notação cientifica. Denominamos essa estrutura de dados de Expanded Number

Em outras palavras,

Um Expanded Number é a representação computacional de um número real expandido em suas somas multiplicadas por dez elevado a suas respectivas ordens.

Representação visual

(p0)[m0 o0] -> ... -> (pi)[mi oi] -> ... -> (pn)[mn on] -> λ

Onde pi é a i-ésima parte, mi é o i-ésimo módulo e oi é a i-ésima ordem de um Expanded Number.

Uma parte é formada pelo seu módulo e a sua ordem.

Exemplos

  1. Se 123 é um número real. Então, pode ser escrito como:
    123 = 1x102 + 2x101 + 3x100
    Dessa forma, na representação Expanded Number será:
    (p0)[3 0] -> (p1)[2 1] -> (p2)[1 2] -> λ

  2. Se 10023 é um número real. Então, pode ser escrito como:
    10023 = 1x104 + 2x101 + 3x100
    Dessa forma, na representação Expanded Number será:
    (p0)[3 0] -> (p1)[2 1] -> (p2)[1 4] -> λ

  3. Se 100,23 é um número real. Então, pode ser escrito como:
    100,23 = 1x104 + 2x10-1 + 3x10-2
    Dessa forma, na representação Expanded Number será:
    (p0)[3 -2] -> (p1)[2 -1] -> (p2)[1 4] -> λ

Após fazemos essas definições, a parte mais trabalhosa, que custou dias de dor mental, foi definir as operações ariméticas nessa estrutura de dados. Confesso que essa é a parte mais bela de todo o projeto. Vou deixar para imaginação e análise de vocês, usuários do TabNews, para imaginarem como são feita essas operações. Bem, você pode dar uma olhada no repositório. Mas, pessoalmente, vale a penar quebrar um pouco a cabeça com isso.

Finalmete, o fatorial de 100 é igual a

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Assustador.

Últimas considerações

Esse algoritmo com certeza não está em seu estado ótimo. Eu sinto, em meu teclado, que é possível otimiza-lo e adicionar novas operaçãos nas quais não pensei. Sintam-se a vontade para sugerir mudanças tanto nessa publicação quanto no próprio projeto. Um abraço!

Carregando publicação patrocinada...
1
1

Aqui estão algumas referências:

  • Matemática
    • Pré-Cálculo coleção schaum, ótimo livro para fortalecer a base em matemática, direto ao ponto.
  • Algoritmos e Estruturas de Dados
    • Estruturas de Dados e Seus Algoritmos, tem uma gama satisfatória de estruturas de dados. Além disso, há bastante exercícios para você praticar.
1

Muito bom!

Uma pequena melhoria é que multiplicar por 1 é redundante, então o loop pode começar do 2.

Outra sugestão é ter uma função auxiliar que já cria e inicializa - ou seja, recebe uma lista de valores, chama create e depois append para cada valor da lista.

1
1

Criei um pull request, veja lá.

Basicamente, adicionei a função create_from_int, que permite criar um número expandido a partir de um valor inteiro - assim não precisa usar create seguido de vários append (acho que é melhor do que a minha primeira ideia de ter a lista de valores).

Criei também um Makefile, que facilita o build do projeto (veja instruções no README).

1

Opa! Desculpa a demora. Muito obrigado pela a contribuição de melhoria. É a primeira vez que recebo um pull request em projeto meu. Confesso: saiu uma lágrima de felicidade em meus olhos!

Uma dúvida, onde posso encontrar material de qualidade sobre Makefile?

1