Em Produção · ICPC · Fundamentos
Fibonacci de 10¹⁸ em 84 multiplicações
Toda recorrência linear pode ser escrita como multiplicação de matrizes. E matrizes podem ser elevadas a uma potência rápido.
Qual é o 10¹⁸-ésimo número de Fibonacci, módulo algo razoável? Um loop ainda estaria rodando muito depois do fim da maratona. Dá para chegar lá com 84 multiplicações.
Uma recorrência linear é uma sequência em que cada termo é uma combinação linear dos anteriores, e Fibonacci é o exemplo famoso. Qualquer passo assim pode ser escrito como uma matriz T vezes um vetor com os termos recentes. Aplicar T uma vez anda a sequência um passo. Aplicar duas, T², anda dois. E T^(n−1), aplicada a f(0) e f(1), que você já conhece, chega em f(n).
Então a pergunta vira: quão rápido dá para elevar uma matriz a uma potência? Você não precisa de n multiplicações para chegar a xⁿ. De x sai x², de x² sai x⁴, de x⁴ sai x⁸. Qualquer expoente é uma soma dessas potências de dois, lida direto dos seus dígitos binários. Elevar ao quadrado transforma n passos em uns log n.
Carregando a figura interativa…
Versão estática: f(10¹⁸) sai com 84 multiplicações de matrizes 2×2, contra 10¹⁸ somas no laço simples.
O loop precisa de 10¹⁸ passos; a matriz precisa de 84 multiplicações. Quando algo cresce um passo de cada vez, procure a forma que dobra. Quase sempre existe uma.