Arquivo para novembro \01\UTC 2010

Os Bonacci’s

Não consigo entender o motivo de todo professor de computação inventar de mostrar a série de Fibonacci ao começar um curso ou apresentar uma nova linguagem.

O problema não é a série, mas sim a aberração recursiva (não dá para chamar de algoritmo) que calcula o n-ésimo termo da sequência em tempo O(2n).

Para quem não se lembra,

def fibonacci(num):
    if num == 0: return 0
    if num == 1: return 1
    return fibonacci(num-1) + fibonacci(num-2)

Se for para calcular apenas uma vez e até o vigésimo termo num computador que rode a uns 2GHz não vai dar para notar as mais de 10 milhões de chamadas recursivas pois isso pode ser feito em poucos milissegundos.

Se quiser ir mais longe e calcular o Fibonacci de 47, último que cabe num inteiro unsigned de 4 bytes, você vai levar uns bons 40 ou 50 segundos usando uma linguagem compilada como C, C++ ou até vários minutos com o algoritmo acima em python.

Minha grande dúvida é: Por que usar um algoritmo com essa complexidade se existe um em O(n), fazendo as somas até chegar no n-ésimo elemento e outro em O(log2(n)) usando a proporção áurea, também conhecido como número de ouro?

Encontramos o elemento fazendo:

Onde

Assim, para calcular o n-ésimo termo da série de Fibonacci, basta arrendondar o valor de F(n).

A complexidade desse algoritmo é log2(n) pois a exponenciação não é feita em apenas uma operação.

Obviamente, esse algoritmo está limitado à representação em ponto flutuante da máquina. Utilizando um double, é possível ter um número que varia de 10-308 até 10308, mas a precisão só vai até 15 algarismos. Assim, para elementos acima de F(70), o computador vai começar a errar o valor de da série a partir do 15º algarismo.

Se a ideia é fazer um gerador da série de Fibonacci, o melhor algoritmo é o que seria usado para encontrar o valor em O(n), mas, como vamos sempre ter os valores anteriores, encontrar o próximo elemento será em O(1):

#Exemplo de gerador
def geraFibonacci(num):
    ultimos = [0,1]
    for i in range(num):
        if i <= 1:
            yield i
        else:
            ultimos = [ ultimos[-1], sum(ultimos) ]
            yield ultimos[-1]
    return

OBS: Para Python 2.x, sempre usar xrange() no lugar de range()

O legal da série de Fibonacci é que ela é mais que “a soma dos dois elementos anteriores”. Mais elegante é dizer que o termo seguinte é o anterior vezes o número de ouro.

Definido isso, podemos até colocar números na base φ, pois, como fazemos na base 2, cada número da série é o anterior vezes 2.

O número 101002 vale 24 + 22 = 20
O numero 10100φ vale F(4) + F(2) = 4.

Na representação escolhida para a base φ, os dois últimos “bits” devem sempre valer zero, pois a série começa em 0, 1, 1, 2, 3, 5… e teríamos um número 1 repetido e um número 0 que não acrescenta nada.

Para entender melhor o porquê desses algarismos serem zero, ao escolher dois termos consecutivos da série de Fibonacci para representar um número na base φ, seria o mesmo que pegar o seguinte já que ele é a soma dos outros dois. Assim , 100110000 = 101000000. Da mesma forma, 100011 = 100100.

Num exemplo mais prático, 27 = 21+5+1+0 = F(8) + F(5) + F(1) + F(0) = F(8) + F(5) + F(2) = 100100100φ.

Visto isso, podemos variar um pouco a série de Fibonacci para encontrar outras, como a Negafibonacci onde é definido F(n) para n < 0, sendo F(-n) = (-1)n F(n).

Mais interessante ainda são as séries que generalizam a quantidade de termos anteriores para formar o atual. A mais conhecida é a de Tribonacci, mas você pode fazer “Quadrinacci”, “Hexanacci”, etc.

A série de Tribonacci define os três primeiros termos como [0, 1, 1] e calcula os seguintes com a soma dos 3 anteriores. Com ela, teríamos uma razão dada pela raiz real da equação t3-t2-t-1 = 0 que vale aproximadamente 1.839287.

É possível ver que a razão da série vai aumentando ao usar mais termos para calcular o seguinte. Assim, poderíamos generalizar e encontrar a série de N-nacci que pegaria os N termos anteriores para achar o atual. Apenas temos que definir os primeiros N elementos.

Para ficar coerente, sempre começamos com 0 e 1 e depois colocamos os seguintes imaginando que antes do 0 teríamos mais zeros. Para N = 8, por exemplo, definimos 0, 1, 1, 2, 4, 8, 16, 32.

Já deu para perceber que fora os dois primeiros termos definimos os seguintes são da forma 2k, k variando de 0 a N-2. Assim, para N tendendo a infinito, a Série de “Infinitonacci” irá ter uma razão de 2 e teremos chegado à representação na base 2!

# N-nacci
def Nnacci(num, N=2):
    if N < 2: N=2
    lista = [0,1]
    lista += [2**i for i in range(0,N-2)]

    if num <= N-1:
        return lista[num]
    for i in range(num-(N-1)):
        lista = lista[1:] + [sum(lista)]
    return lista[-1]

Exemplos:
Para N = 2 : φ ~ 1.618034
Para N = 3 : φ3 ~ 1.839287
Para N = 4 : φ4 ~ 1.927562
Para N = 5 : φ5 ~ 1.965948
Para N = 8 : φ8 ~ 1.996031
Para N = 10 : φ10 ~ 1.999019
Para N = 20 : φ20 ~ 1.999999

Se olhar com calma, é bem simples de entender que a série de “Infinitonacci” tem razão 2, pois

Ou seja, o próximo termo vale a soma de todos os anteriores + 1.

Qual a utilidade disso tudo?
Bem, ainda não sei.