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

BRTOS

Para quem se interessa por microcontroladores e sistemas embarcados, aqui vai uma série de artigos sobre como construir um RTOS (Sistema operacional em tempo real) com código fonte para MSP430.

A série é escrita pelo Marcelo Barros no seu blog Jedizone e é bastante explicativa. Inclusive me deu algumas ideias para fazer o Projeto Integrado da faculdade.

Links:

Parte 1

Parte 2

Parte 3

Parte 4

Parte 5

Parte 6

Parte 7

Código fonte: http://code.google.com/p/basicrtos/

A motivação da série é fazer com que um microcontrolador possa executar diversas tarefas simultaneamente. Pode ser aplicado à qualquer uC desde que se tenha uma quantidade razoável de memória RAM.

Varchar ou Char?

Quando as pessoas criam as tabelas num banco de dados, parece unânime a escolha de ‘varchar’ para representar strings e texto curto em geral. Em pouquíssimos lugares vê-se o uso de ‘char’.

Para coisas maiores, acabam usando algo como ‘text’ ou ‘longtext’ (nomenclatura do MySQL, pode variar), que permite, em geral, até 64KB e até 2GB de texto, respectivamente.

– Por que isso é feito assim?

O varchar é um tipo existente em, possivelmente, todo banco de dados, e guarda apenas a quantidade de caracteres do texto armazenado, sem adicionar espaços em branco. Por exemplo, se temos um campo varchar(40), ele vai armazenar fisicamente de 0 a 40 bytes, dependendo do tamanho do texto inserido.

Já o tipo ‘char’, aloca espaço para todos os caracteres, deixando bytes vazios. No caso de char(40), o banco de dados vai ter exatamente 40 bytes por linha naquela coluna.

O tipo ‘text’, assim como suas variações, usa a mesma ideia do ‘varchar’, mas é feito para quantidades maiores de texto.

Veja como é o design da tabela de posts de um blog WordPress:

Veja que os tipos usados para armazenar texto são 'varchar', 'text' e 'longtext'.

Parece meio óbvio que usar um campo variável para armazenar texto é mais interessante que um campo fixo, já que poupa espaço desnecessário, no entanto, em termos de performance usar varchar pode transformar sua aplicação numa carroça.

Um banco de dados armazena seus dados em páginas de tamanho fixo, sendo que os bancos modernos usam páginas de 16KB (maioria) ou 32KB (IBM DB2). Alguns ainda usam páginas menores, como o Microsoft Access (4KB) ou o Microsoft SQL 2000 (8KB).

Desta forma, quando você adiciona uma linha numa tabela de um Banco, ele vai procurar a próxima página que tenha espaço suficiente e vai escrever seus dados lá.

Abaixo temos um exemplo de uma linha sendo adicionada à uma página que estava vazia. O ponto azul é para mostrar que naquele ponto tem um ‘varchar’ que foi criado vazio.

Quando usamos um tipo de dados como ‘varchar’, a linha adicionada numa tabela pode crescer se um dia resolvermos colocar mais dados. Imagine que você está fazendo o cadastro de usuários e o campo de endereço da pessoa (varchar(200), por exemplo) foi criado sem nada escrito.

Antes que o usuário resolva adicionar seu endereço ao cadastro, outros usuários se inscreveram no sistema e, como seus dados cabiam na mesma página anterior, foram colocados juntos:

Assim, quando o primeiro usuário adiciona seu endereço ao cadastro, a página onde os dados dele estavam já não tem mais espaço.

A solução que o banco dá é de colocar o novo dado no lugar certo e empurrar o excedente para a próxima página que tenha espaço livre. Além disso, ele cria um ponteiro da primeira página para a segunda, mostrando que, sempre que for preciso ler os dados do último usuário, ele tenha que acessar duas páginas:

– Qual o problema disso?

Para entender o porquê disso ser algo ruim é preciso saber que o banco de dados, por mais que armazene tudo em disco, ele precisa fazer o mínimo possível de acessos ao disco, para manter uma performance boa.

Tempos de acesso em Processador 32-bit rodando à 2.0GHz

Pela tabela acima, vemos que o tempo que o processador precisa esperar para que um dado do HD chegue à ele é mais de 140.000 vezes maior que pegar um dado da memória. Assim, usando uma página de 32KB e lendo em blocos de 512B (No final de 2009, HDs de blocos de 2KB começaram a ser padrão), o tempo gasto para fazer essa leitura pode ser muito grande, ainda mais se as duas páginas não estiverem fisicamente próximas.

– Então, vale a pena economizar espaço e depois ficar com um banco lento?

Algumas vezes esse problema não vai ser percebido, talvez pela aplicação não ser grande o suficiente ou talvez por não haver atualização nos dados.

Se for sabido de antemão que não haverá mudança numa linha após a sua criação, então não há problema algum em usar Varchar.

– Mas vale a pena correr o risco?

Vamos ver: Digamos que eu tenha uma tabela com 10 campos do tipo varchar(40) e a previsão é de que essa tabela receba até 10 milhões de linhas.

Dependendo dos dados, o tamanho da minha tabela pode variar de 10MB até 410MB, já que o Varchar armazena 1 byte para sinalizar o tamanho utilizado, que é menor ou igual a 40.

Isso quer dizer que, mesmo com uma tabela ENORME, eu só vou economizar uns 100 ou 200MB de espaço em disco!

Quanto custa um terabyte hoje? 2000 Reais? 1000 Reais?
Não, 200 Reais ou menos.

Por outro lado, se o seu texto for grande (> 255B) ou tiver uma grande variação de tamanho (desde 1 ou 2KB até 100 ou 200KB), é interessante utilizar um campo variável, como é o ‘text’ e o ‘longtext’ do MySQL.

Monitores atuais

Ultimamente eu tenho notado que os monitores de LCD estão crescendo e as resoluções diminuindo.

Na época em que os CRT’s ainda eram populares, as pessoas tinham ou monitores de 17″ de resolução 1280×1024 ou tinham aqueles de 14/15″ de 1024×768. O primeiro com formato 5:4 ‘quadradão’ e os outros com 4:3 (um pouco menos ‘quadradão’). Era raro ver qualquer coisa diferente disso.

As primeiras telas finas a ficarem populares foram as de plasma, mas, por conta da dificuldade de fazer pixels pequenos, elas eram comumente de baixa resolução 854×480 – algo que temos em LCDs de celular – e eram enormes (40″, 50″ ou maior). Seu formato é 16:9, que é bem mais esticado que o 4:3.

Em comparação com as TVs CRT de 500 linhas verticais, essas telas de plasma são até boas, mas para usar com um computador não dá muito certo.

Logo após, começaram a surgir monitores de LCD com o formato dos CRTs. Aqueles da Samsung e LG, entre outras, de 17″ e resolução 1280×1024 são ainda bem comuns, mas praticamente não são mais fabricados.

Talvez por causa dos notebooks serem bem mais compridos que largos, painéis de LCD começaram a ficar alongados.

A primeira safra foram dos monitores 15,6″ de resolução 1280×800 (16:10), que tem exatamente a mesma largura do monitor 5:4 de 17″, mas com menos pixels verticais. Para notebooks esse monitores aprecem em tamanhos de 15,6″, 14″ e 13,3″, normalmente.

Praticamente junto da resolução 1280×800, surgiram os monitores de 17″ 1440×900 e um pouco depois os 1680×1050, ambos também 16:10. Essas versões foram destinadas basicamente à monitores de Desktop.

Durante esse tempo, as TVs de Plasma já começaram a apresentar resoluções maiores e passaram a competir com os LCDs que estavam barateando. Apareceu no mercado mais um padrão de resolução que era o 1366×768, um formato 16:9, o mesmo usado no cinema. Ele é um pouco maior que o 720p, que é 1280×720, que também começou a ficar famoso. Ambos são considerados HD (High Definition).

Nas TVs, ainda, surgiu o Full HD (ainda maior que o HD) também conhecido como 1080p e é um formato 16:9 de resolução 1920×1080. Nos monitores surgiu o 1920×1200, que é 16:10 (Normalmente para telas de 22″ e 24″).

Para assistir filmes, nada melhor que ter a tela inteira preenchida com a imagem, sem aquelas barras pretas em cima e embaixo. Já no uso do computador, qualquer quantidade de pixels verticais já ajuda, por causa das barras de programas, título das janelas, barra de abas, barra de ferramentas, etc.


Firefox no Windows 7 em resolução 1280×720. Apenas 540 pixels verticais estão disponíveis para o conteúdo.

Claro que, usando uma tela Full HD, mesmo sendo 16:9, o problema desaparece, mas veja que 1080px verticais são quase os mesmos 1024px dos monitores CRT de 17″.

Mesmo assim, por causa desse apelo do formato de cinema, a nova safra de monitores parece estar seguindo essa tendência. Olhando em sites de compras, praticamente só se vê monitores de 18,5″ (18 é o novo 17) com 1366×768, monitores de 19″ com 1600×900 e monitores de 21,5″ com 1920×1080 de resolução. Todas no formato 16:9.

Para monitores de notebook menores, também começaram a aparecer resoluções como 1280×720 e 1024×576, ambas 16:9, como se alguém comprasse um aparelho com tela de 10″ para assitir filmes.

Mudando de 1024×600 (16:10) para 1024×576 num netbook, você perde 24 pixels, que é exatamente o tamanho de uma barra como a de programas do Windows!

Veja abaixo uma comparação de monitores comuns:

Abaixo uma lista ordenando as resoluções pelo total de megapixels:

É interessante ver como um monitor de CRT antigo de 17″ tem mais pixels que os monitores de 17″ e 18,5″ vendidos atualmente. A diferença é quase inexistente para os monitores de 17″ 1440×900, mas para os de 18,5″ atuais de 1366×768, temos uma grande perda de pixels e mais ainda de espaço vertical.

É claro que existem exceções, mas os monitores estão ficando maiores e as resoluções menores, tudo isso para adaptar as telas ao formato de cinema.

Minha opinião:
Telas alongadas são mais agradáveis, pois nossos olhos estão na horizontal e conseguem captar mais informação sem ter que subir e descer a cabeça. Ao mesmo tempo, temos que conseguir conciliar o problema do espaço vertical disponível.

Para televisão: Não há dúvidas que o formato 16:9 é a melhor opção, desde que os programas exibidos também sejam nesse formato. Eu vejo muita gente com TV Full HD assistindo rede Globo com a imagem 4:3 esticada num telão de 50″ em 16:9.
Para computador: Depende. Entre um monitor 16:10 e um 16:9, primeiro eu escolheria pelo número de pixels e depois pelo formato.

Dando nome aos Cores

Ao contrário da AMD, a Intel resolveu nomear seus processadores das novas linhas Core i7, i5 e i3 de um modo muito confuso, fazendo com que alguns processadores pareçam muito melhores que outros, quando na verdade não são.

A AMD, assim como a Intel na época do Core2, nomeia seus processadores Phenom, com a versão, o número de núcleos e um número que normalmente cresce de acordo com o clock, além de eventuais letras para dizer que o processador tem o multiplicador destravado. Exemplo: AMD Phenom II X4 940 BE.

Como o marketing geralmente fala mais alto, a Intel fez uma salada de nomes que deixa qualquer um confuso. Assim, quando o consumidor vai comprar seu novo computador ele acaba escolhendo aleatoriamente.

Por isso, coloquei aqui uma lista para ajudar os leitores do Rot-13 a não se enganarem mais ao escolher seu próximo Desktop ou Notebook.

Toda a linha Core iN é baseada na arquitetura Nehalem, que trouxe diversas melhorias em relação à anterior do Core2, incluindo o Turbo Boost (aumenta o clock de um ou dois núcleos enquanto outros são desativados), QuickPath Interconnect (Barramento ponto a ponto para substituir o FSB. Semelhante ao HyperTransport da AMD), Simultaneous Multi-Threading (Possibilidade de rodar duas Threads por núcleo – Nem sempre é algo bom), entre outras coisas.

Essa arquitetura deu origem à todas as outras usadas nos processadores. Abaixo temos um comparativo delas:

Abaixo temos a lista de nomes de processadores com as características que variam. No lugar dos sublinhados podem aparecer quaisquer números, normalmente relacionado ao clock do processador na série:

Nas versões de Notebook a confusão é ainda maior por causa das versões de baixo consumo energético (UM):

Olhando as nomenclaturas e as características dos processadores, dá para perceber que se, por exemplo, você comprar um Core i7 8xx você vai ter uma solução melhor que um Core i7 9xx de mesmo clock quando usados apenas 2 canais de memória. Isso sem contar que o Lynnfield tem um Turbo Boost de 266MHz enquanto no Bloomfield é só de 133MHz.

Assim, se você for um cara esperto (e sem muito dinheiro) dá pra gastar menos com uma solução melhor.

Desbalanceamento de Bancos replicados

Já tem uns 8 meses que esse problema que tive foi resolvido, mas, como não tinha blog na época, não escrevi nada.

Essa solução se aplica ao Microsoft SQL Server.

Quando você tem bancos de dados numa replicação do tipo Merge (ou Mesclagem, para quem usa em português), qualquer alteração feita no publicador ou no assinante é replicada, fazendo com que as tabelas afetadas dos dois lados fiquem sempre com o mesmo conteúdo.

O problema que eu tinha se devia ao fato de ter 3 assinantes colocando dados numa tabela replicada no banco de dados do Servidor Central. Assim, como o volume de dados era grande (50 linhas, com imagens, por assinante sendo criadas por minuto, 24 hs por dia), a única opção era mesmo usar uma replicação do tipo Merge, já que Snapshot e Trasacional seriam inviáveis.

Chegou um momento, depois de vários meses com o sistema rodando, que o espaço físico do HD dos assinantes começou a ficar pequeno e, como o Servidor Central já guardava todos os dados, surgiu a idéia de limpar os bancos dos assinantes mensalmente para não ter problemas de falta de espaço.

Num mundo ideal, compraríamos HDs maiores, mas a realidade é outra.

Depois de muita procura, vários sites diziam que “O MICROSOFT SQL SERVER NÃO PERMITE QUE OS BANCOS DE DADOS NUMA REPLICAÇÃO DO TIPO MERGE FIQUEM DESBALANCEADOS!”.

Como assim, ele agora diz o que eu posso e não posso colocar no meu banco de dados?

Lendo a documentação da Microsoft sobre o funcionamento da replicão Merge, vemos que sempre que há uma mudança numa tabela a partir de um INSERT, UPDATE ou DELETE, um trigger é disparado para que esse dado seja replicado.

Bem, aí está a solução!

Olhando os triggers da tabela replicada estavam lá os três códigos SQL que garantiam o que os sites diziam sobre o desbalanceamento! O código relacionado à ação de deletar só precisava ser eliminado.

Para garantir que nenhum erro acontecesse, caso o trigger de DELETE fosse apagado, tomamos uma providência bem simples que consistia em colocar um ‘return‘ logo no início do código, fazendo com que o trigger seja executado quando uma linha é deletada, mas não replicando a ação.

[Update] O SQL Server 2008 permite desabilitar um trigger ao clicar com o botão direito nele. É uma solução mais limpa e inteligente.

Problema resolvido, bancos desbalanceados, mais espaço no HD e outro cliente feliz.

Enquanto isso, no país do BBB

Tenho pena dos bons advogados, se é que eles existem.

Parece que um ser dessa espécie fez uma grande besteira, envolvendo uma grande marca de aparelhos eletrônicos e um blog sobre a mesma.

Coitado, quando ele fez isso devia estar desatento assistindo sobre os escolhidos Big brother. Cabeças vão rolar!

Que belo modo de começar o ano! Feliz 2010.

Bem, não vou colocar lenha na fogueira, então visitem o www.zeletron.com.br, o novo melhor blog brasileiro.