Fibonacci Sequencia

Cálculo de Fibonacci na prática

A definição clássica é simples: cada termo é a soma dos dois anteriores, começando com F(0) = 0 e F(1) = 1. Isso soa fácil até você tentar implementar o algoritmo recursivo ingênuo e ver seu código travar em F(40). A recursão pura tem complexidade exponencial O(2^n) porque recalcula os mesmos valores repetidamente. F(35) aparece mais de um milhão de vezes na árvore de chamadas. O primeiro passo para qualquer implementação séria é memoização. Você guarda os resultados já calculados e consulta antes de recalcular. Isso transforma a complexidade em O(n) tempo e O(n) espaço. Em Python, um dicionário ou uma lista basta. Em linguagens mais baixas, um array com tamanho pré-alocado funciona melhor porque evita a sobrecarga de alocação dinâmica.

Por que a fibonacci sequencia é mais traiçoeira do que parece

Muita gente para na memoização e acha que resolveu. O problema real aparece quando você precisa calcular termos muito grandes, como F(100000). Mesmo com memoização, o número de bits cresce linearmente com n. F(100000) tem cerca de 20.900 dígitos decimais. Operações aritméticas com números dessa magnitude já não são mais O(1) — cada soma vira O(d) onde d é o número de dígitos. O tempo total de cálculo pode subir para algo próximo de O(n²) no pior caso, dependendo da biblioteca de BigInt que você usa. Um problema específico que encontrei na prática foi precisar gerar termos de Fibonacci para uma tabela de hash em um sistema de criptografia caseira. Eu usava memoização padrão e quando pedi F(500000) o processo simplesmente não terminava. A solução foi trocar para o método de fast doubling, que calcula F(n) e F(n+1) simultaneamente usando as identidades:

F(2k) = F(k) · [2·F(k+1) F(k)]
F(2k+1) = F(k+1)² + F(k)² Isso reduz a complexidade para O(log n) chamadas recursivas. Combinado com multiplicação de Karatsuba para os BigInts grandes, F(500000) saiu em segundos ao invés de horas. Sem esse ajuste, o código era funcional mas impraticável para produção.

Também vale saber que existe o período de Pisano. Para qualquer módulo m, a sequência de Fibonacci módulo m é periódica. O comprimento desse período, chamado (m), para m = 10^k é 15·10^(k-1). Isso significa que se você só precisa de F(n) mod 1000000, não precisa calcular o número inteiro gigante — basta seguir a sequência módulo 1000000 até encontrar o ciclo ou usar a propriedade de periodicidade para reduzir n. Isso é extremamente útil em competição de programação e em algoritmos onde o resultado final é sempre modulado.

Implementação direta

Se o objetivo é apenas obter o n-ésimo termo sem modular aritmética e com n moderado, a abordagem iterativa com memoização é suficiente e mais simples: ```python
def fib(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
```

Essa versão usa O(1) de espaço adicional e O(n) de tempo. Para n até alguns milhares, é rápida o bastante. A desvantagem é que cada chamada recalcula do zero. Se você chamar fib() múltiplas vezes com índices diferentes, a memoização com cache persistente compensa rapidamente. Já o fast doubling em Python fica assim:

```python
def fib_fast_doubling(n):
if n == 0:
return (0, 1)
a, b = fib_fast_doubling(n >> 1)
c = a * (2 * b - a)
d = a * a + b * b
if n & 1:
return (d, c + d)
return (c, d)
``` A função retorna a tupla (F(n), F(n+1)). O custo é O(log n) chamadas recursivas. O único ponto de atenção é que Python já lida com BigInt automaticamente, então para n muito grande o gargato passa a ser a própria aritmética de grandes inteiros, não a lógica do algoritmo.

Queda de produtividade e alternativas

Não recomendo Fibonacci para benchmarking de performance de linguagens. A razão é que os benchmarks mais comuns usam n pequeno o suficiente para caber em palavras de máquina, o que esconde diferenças reais de implementação de BigInt. Um benchmark mais honesto testa F(100000) ou mais, onde a diferença entre uma multiplicação O(n²) e Karatsuba O(n^1.585) se torna visível. Testes com n = 30 só mostram velocidade de recursão, não capacidade computacional real. Se você precisa de Fibonacci em produção para geração de números pseudoaleatórios ou estruturas de dados, considere bibliotecas como GMP ou Crypto++ em C++, ou sympy em Python, que já otimizam as operações de BigInt. Implementar do zero é interessante para aprendizado mas introduz riscos de segurança e performance que valem a pena evitar em código que vai para produção.

Um exemplo concreto: em um projeto onde eu precisava verificar primalidade de números da forma F(n) ± 1, calcular F(n) para n = 10000 com recursão pura levou cerca de 40 minutos. Com fast doubling e memoização, o mesmo cálculo levou 0,3 segundos. A diferença não é marginal, é a diferença entre rodar o teste uma vez ou abandoná-lo. O código completo com ambas as abordagens e suporte a entrada via linha de comando está disponível no repositório público. Basta buscar por "fibonacci sequencia python" que encontra os dois métodos implementados com exemplos de uso e medição de tempo.