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

(p₀)[m₀ o₀] -> ... -> (p_i)[m_i o_i] -> ... -> (p_n)[m_n o_n] -> λ

Onde p_i é a i-ésima parte, m_i é o i-ésimo módulo e o_i é 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 = 1x10² + 2x10¹ + 3x10⁰
   Dessa forma, na representação Expanded Number será:
   (p₀)[3 0] -> (p₁)[2 1] -> (p₂)[1 2] -> λ

2. Se 10023 é um número real. Então, pode ser escrito como:
   10023 = 1x10⁴ + 2x10¹ + 3x10⁰
   Dessa forma, na representação Expanded Number será:
   (p₀)[3 0] -> (p₁)[2 1] -> (p₂)[1 4] -> λ

3. Se 100,23 é um número real. Então, pode ser escrito como:
   100,23 = 1x10⁴ + 2x10^-1 + 3x10^-2
   Dessa forma, na representação Expanded Number será:
   (p₀)[3 -2] -> (p₁)[2 -1] -> (p₂)[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!