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.

Anúncios
    • Pedro Paulo
    • 1 de novembro de 2010

    Puxa, o blogueiro escreve pouco, mas quando escreve são bons os textos.

    Não sei o que inspirou o blogueiro

      • João Bernardo
      • 1 de novembro de 2010

      São as provas da faculdade que atrapalham… 🙂
      Devo escrever mais alguma coisa até o fim do mês, provavelmente sobre um transmissor FM que pretendo montar.

  1. No trackbacks yet.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

w

Conectando a %s

Anúncios
%d blogueiros gostam disto: