Candidatos a primos

Quem sair a procurar primos não se dará ao trabalho de inspecionar os inteiros pares. Então, começando pelo primeiro inteiro não múltiplo de 2, basta ir somando 2 para encontrar aqueles que não são múltiplos de 2. Ou seja, há aí uma pequena série (2).

Resolvi investigar o que apareceria se eu quisesse eliminar também os múltiplos de 3. Começando com 5 (o primeiro inteiro que não é múltiplo nem de 2 nem de 3), descobri que basta somar 2, depois 4, depois 2, depois 4 e assim por diante. Então, a nova série é (2, 4).

Confiante com o sucesso, busquei, com a ajuda de um script em Perl, as séries para os primos seguintes. O que facilita a busca é que a soma dos elementos tem que ser igual ao produto dos primos que queremos excluir. Então, para 2 e 3 a nossa série é (2, 4), cuja soma é igual e 2*3.

A série para 2, 3 e 5 é (4, 2, 4, 2, 4, 6, 2, 6). A partir daí, as séries crescem seriamente. A tabela abaixo mostra a quantidade de elementos para cada uma:

Primos	Elementos na série
2	1
2, 3	2
2, 3, 5	8
2, 3, 5, 7	48
2, 3, 5, 7, 11	480
2, 3, 5, 7, 11, 13	5.760
2, 3, 5, 7, 11, 13, 17	92.160
2, 3, 5, 7, 11, 13, 17, 19	1.658.880
2, 3, 5, 7, 11, 13, 17, 19, 23	36.495.360

Quando tentei calcular a série para os primos até 29, a memória acabou. Cada série tem o número de elementos da série anterior vezes o novo primo menos um. A série dos 4 primeiros primos, por exemplo, tem 6 vezes mais elementos que a série para os 3 primeiros primos, porque adicionou o 7. A próxima série da minha tabela, portanto, deve ter 1.021.870.080 elementos (28 vezes mais que a anterior).

Usando a primeira série, reduz-se o domínio de busca pela metade (inspecionam-se apenas os ímpares). Com a segunda, resta apenas um terço (a série cobre 1/2+1/3-1/6 dos inteiros). Usando a série dos quatro primeiros primos, é preciso inspecionar apenas cerca de 22,8% dos inteiros. Logo, vê-se que a vantagem de usar séries que cobrem mais primos vai diminuindo rapidamente.

Diversões numéricas com SQL III

Todos os inteiros são produzidos por uma combinação única de potências de primos. O que interessa-me saber é quais números têm uma quantidade maior de primos na sua composição.

Comecei com uma pequena consulta para fatorar um único inteiro.

with integers as (select rownum as n from all_tables where rownum<100)
select n
from integers i1
where mod(168, n)=0 
      and n between 2 and 168-1 
      and not exists (select 1 
                      from integers i2 
                      where i2.n>1 
                            and i2.n<i1.n 
                            and mod(i1.n, i2.n)=0)

Parece Lisp, não? E 168 tem três primos na sua composição: 2, 3 e 7. Adicionando uma tabela, posso procurar os inteiros que tenham o maior número de fatores primos. Aproveitei também para acelerar a busca usando a raiz quadrada de cada inteiro como limitador.

with integers as (select rownum as n from all_tables where rownum<10000)
select count(i1.n), i3.n
from integers i1, integers i3
where mod(i3.n, i1.n)=0 
      and i1.n between 2 and sqrt(i3.n)
      and not exists (select 1 
                      from integers i2 
                      where i2.n>1 
                            and i2.n<=sqrt(i1.n)
                            and mod(i1.n, i2.n)=0)
group by i3.n
order by 1 desc

Nenhum inteiro menor que 10.000 tem mais que 5 fatores primos. O inteiro 7770, por exemplo, tem os fatores 2, 3, 5, 7 e 37.

Como os priminhos baixinhos estavam aparecendo muito, resolvi procurar apenas os inteiros cujos fatores primos sejam maiores que 10. Descobri, então, que apenas 1059 inteiros menores que 10.000 têm todos os fatores primos maiores que 10. O 7429, por exemplo, tem os fatores primos 17, 19 e 23. Além disso, nenhum desses 1059 tem mais que 3 fatores primos.

Diversões numéricas com SQL II

Nenhuma diversão numérica seria completa se os primos não aparecessem. Então, resolvi logo descobrir se é possível selecioná-los.

with integers as (select rownum as n 
                  from all_tables 
                  where rownum<100)
select n 
from integers i1
where i1.n>1 
      and not exists (select 1 
                      from integers i2 
                      where i2.n>1 
                            and i2.n<sqrt(i1.n) 
      and mod(i1.n,i2.n)=0)

Parece bom. E com isso podemos procurar relações interessantes, como primos gêmeos.

select n, previous from (
  with integers as (select rownum as n 
                    from all_tables 
                    where rownum<100)
  select n, lag(n, 1, n) over (order by n) previous 
  from integers i1
  where i1.n>1 
        and not exists (select 1 
                        from integers i2 
                        where i2.n>1 
                              and i2.n<sqrt(i1.n) 
        and mod(i1.n,i2.n)=0)
) where n=previous+2

Usando a função lag(), podemos selecionar todas as duplas de primos separados por apenas um inteiro. Com isso, descobri que 3001 e 2999 são primos gêmeos, assim como 9001 e 8999.

Diversões numéricas com SQL

Contar com SQL é fácil; achar uma utilidade custou-me um pouco. Comecei com uma consulta bastante simples para contar em base 2.

with bits as (select rownum-1 as bit from all_tables where rownum<3)
select b1.bit, b2.bit
from bits b1, bits b2

O resultado é uma tabela bastante simples, com os quatro números possíveis de dois dígitos binários.

A primeira aplicação (embora redundante, porque o Oracle já me oferece alternativa) é a de converter números para a base 16 (que é uma tarefa bastante comum na minha ponta da internet).

Minha nem tão elegante solução é esta:

select byte1||byte2 from (
  with bytes as (select decode(rownum-1, 
                        least(rownum-1,9), to_char(rownum-1), 
                        chr(rownum-1+65-10)) as byte 
                 from all_tables where rownum<17)
  select b1.byte byte1, b2.byte byte2, rownum-1 valor
  from bytes b1, bytes b2
) where valor=68

A consulta produz, conforme esperado, o valor 44.

Terceira volta

Educação, disse Einstein, é o que nos resta após termos esquecido tudo o que nos ensinaram na escola. Tendo me formado há mais anos do que eu gostaria de mencionar, posso agora seguramente estimar o que terá sobrado das cadeiras que cursei no Instituto de Informática da UFRGS.

Há muito tempo eu tinha a certeza de que algo faltava no curso e após ler um texto de Richard Feynman sobre a educação no Brasil, pude perceber claramente que era a realidade. Alguns exemplos estão claros na minha memória. Em primeiro lugar, a insistência no modelo OSI e nos detalhes da sintaxe do ASN.1 nas aulas de redes. Em segundo, as aulas de autômatos sem nenhuma menção às expressões regulares (lendo o Mastering Regular Expressions, finalmente compreendi o papel de NFAs e DFAs). Em terceiro, o professor de Sistemas Operacionais que nos propôs escrever um montador antes mesmo de mencionar o Lex e o Yacc (e no ano anterior à cadeira de compiladores). Nem preciso entrar no mérito de cadeiras como "Computador e Sociedade".

Obviamente, o propósito do curso não era ensinar informática. No entanto, algum mérito deve ter tido o curso, porque eu dificilmente o trocaria por outro no estado (não descarto a possibilidade de que seja apenas empáfia acadêmica). E o que restou após quatro anos de matérias e tarefas abstratas e aparentemente sem benefícios práticos foi a habilidade de enfrentar problemas novos e em áreas que não domino. Normalmente, a isso dar-se-ia o nome técnico de picaretagem, mas garanto que os egressos da UFRGS o fazem com muita propriedade e com as devidas referências bibliográficas.

Mesmo assim, acho que o currículo deveria ser reformado radicalmente. É preciso tirar a ilusão de que as matérias têm algum valor prático. Nos meus anos de faculdade, brincava-se sobre a cadeira de Corte e Costura para Processamento de Dados. Ela não serve, porque tem valor prático.

Acho que o Instituto de Informática precisa de cadeiras verdadeiramente abstratas, inúteis e arbitrariamente complicadas. Proponho estudos como Lacumetria Antropométrica (medição de lagos usando partes do corpo humano como unidade). Ou então Filatelia Computacional (estudo de selos com referências à informática). Finalmente, a minha favorita, a Kleroterionologia (estudo dos aparelhos usados pelos gregos antigos em suas eleições). Tenho certeza que a SBC compreenderá!

Quantum Countdown Sort

O Countdown Sort já foi otimizado e agora entra para o reino quântico!

O módulo Quantum::Superpositions agrega dois operadores ao Perl: all e any. Eles recebem como parâmetro uma lista que é comprimida para um único valor que é a sobreposição de todos os valores da lista original. Então, magicamente, podemos realizar operações e comparações simultâneas sobre todos os valores de uma lista.

Fundamentalmente, o Countdown Sort é simples. Ele percorre uma lista de números positivos, subtraindo 1 de cada valor; cada vez que a subtração resultar em 0, o elemento original correspondente é adicionado à lista ordenada.

Com a sobreposição quântica, podemos simplificar substancialmente o código. Quanto a melhorar o desempenho, teremos que esperar um computador quântico.

use Quantum::Superpositions;

sub quantum_countdown_sort {
  my @unsorted=@_;
  my @sorted=();
  my $d=0;
  
  while($#sorted<$#unsorted) {
    push(@sorted, $d) if any(@unsorted)-$d==0;
    $d++;
  }
  
  return @sorted;
}

E um pequeno teste confirma que a rotina realmente funciona:

print join ',', quantum_countdown_sort 10,25,2,30,0,1,11;
0,1,2,10,11,25,30

O nome do método já garante a seriedade do pesquisador!

IIN

Os economistas têm uma infinidade de índices para avaliar as economias, mas eu quero propor um novo. Creio que o melhor medidor do potencial econômico de uma nação seria o Índice da Incompetência Nacional.

Há um bom tempo eu venho elaborando esta idéia; recentemente mudei-me e precisei de vários prestadores de serviços e graças à incompetência generalizada deles, pude completar a idéia para o meu índice.

Em primeiro lugar, há a dimensão da pontualidade. Não é que tenham dificuldade em acertar o horário, é que muitos não conseguem sequer chegar no dia combinado!

Em segundo lugar (e acho que essa é uma das dimensões mais importantes do IIN) está a espetacular dificuldade de comunicação. Eles não são capazes de avisar que vão atrasar-se dois dias. Tampouco são capazes de enumerar as peças que devemos comprar ou as ações que devemos tomar com 48h de antecedência. Tampouco são capazes de compreender frases simples, como "pinte esta parede de azul" ou "não vou estar aqui à tarde".

E a incompetência não está restrita ao aspecto gerencial de suas profissões. Os prestadores de serviços esquecem suas ferramentas (tanto de trazê-las como de levá-las), deixam obras inacabadas (e perigosas, como vazamentos de gás) e danificam tudo que está ao redor do seu ponto focal. A sujeira que deixam para trás é insignificante perto da má qualidade da execução.

Se olharmos aos países vizinhos, veremos que há países com economias menos diversificadas e com menor produção de tecnologia, mas cujos padrões de vida são significativamente melhores. Refiro-me ao Chile, ao Uruguai e à Argentina. A única explicação que tenho a dar é que o IIN deles deve ser muito menor.

Epidemia

Eu vasculho os logs do meu sistema e encontro ocorrências sempre em grupos de duas ou três. De quando em vez, são quatro ou cinco. Minha primeira conclusão é que as pessoas estão premindo os botões duas vezes, mas os intervalos de tempo são relativativamente grandes entre os registros repetidos (trinta segundos ou dois minutos).

Pode ser uma epidemia de transtorno obsessivo-compulsivo. Aparentemente, o transtorno está relacionado a um QI mais alto e, curiosamente, nosso país tem uma incidência alta. Infelizmente, os argentinos têm mais ainda. Talvez seja sobre esse tipo de coisa que Gödel quebrava a cabeça: ter muito TOC é bom ou ruim? Definitivamente, não consigo decidir.

Além disso, não há nada para fazer. Se meus usuários estivessem abusando do duplo-clique (já vi quem fizesse um quádruplo clique), eu poderia desabilitar o botão depois do primeiro clique. Talvez eu possa adicionar um contador à página: você já fez isso 9 vezes. Mas não quero que fiquem, ademais, paranoicos.

Por enquanto, vou lavar as mãos.

Métodos frágeis

Uma das práticas mais desastrosas que eu já vi é a de nomear artefatos com os códigos dos casos de uso. A motivação é boa (relacionar os casos de uso ao código que os implementa), mas, como geralmente acontece quando os primeiros princípios são levados adiante por muito tempo antes de se dar uma espiadinha na realidade, o resultado é terrível.

Por exemplo, há quem dê aos JSPs de um projeto Java nomes como "UC123.jsp". Já vi até classes com esse tipo de nome.

Em primeiro lugar, poucos artefatos relacionam-se a apenas um caso de uso. O que o programador vai fazer para resolver isso? Não podemos chamar um JSP de "UC123,127,201.jsp". Em segundo lugar, fica muito difícil ler e encontrar o código que queremos em projetos grandes.

Em terceiro lugar (e este é o motivo mais importante), essas tentativas de burocratizar o código alienam todos os programadores que amam seu trabalho e que preocupam-se com a qualidade do que escrevem. Código bom tem qualidades estéticas para quem sabe apreciá-lo e esse tipo de nome obscurece qualquer tentativa de prover elegância a uma arquitetura.

Ramais rebeldes

Descobrir o ramal de uma pessoa é muito fácil. A intranet os tem todos. Mas algumas pessoas mais antigas (mesmo que de espírito) gostam do velho hábito de usar a telefonista. Como elas não existem mais, alguém vai cumprir o papel, mesmo que involuntariamente!

Então, em nome da paz no ambiente de trabalho, uma técnica pavloviana e pacífica deve ser usada para treinar os preguiçosos chamadores.

A técnica é simples e consiste em, inicialmente, fazer o chamador pensar que a chamada será redirecionada para o alvo pretendido. O treinador deve dizer que "vou passar a ligação para o ramal XYZ", mas deve colocar ênfase e repetir o número com "se a ligação cair, o ramal é XYZ". Então, aperta-se o botão para transferir e coloca-se o telefone no gancho, para que a ligação caia.

Se o chamador insistir, basta repetir a operação. É garantido o resultado em, no máximo, três chamadas (exceto para alguns casos extremos, geralmente restritos a peixes dourados).

Força superior

O usuário aproximou-se com um ar otimista e afirmou que "precisamos disponibilizar este software na intranet". A prática me levou a temer esses arroubos dos usuários. Fiz uma cara amigável e perguntei se o programa era para desktop ou para web.

Era desktop, claro. Mas isso é ruim? O diretor autorizou a publicação do sistema na intranet. Já está tudo aprovado.

Ah bom! Se o diretor aprovou a publicação na intranet, então não temos nada a temer. Vou retornar o workflow com um pedido de esclarecimentos.

Jangada de pasto

Numa bela manhã, um vivente levantou-se ao inusitado som do mar. Sim, porque ele havia ido dormir com a certeza inabalável de que, assim como o havia sido por toda sua vida, acordaria com o silêncio do campo. Achou que seria brincadeira do piá e pôs-se de pé já de mau humor. Esquentou água, preparou a cuia e foi olhar o sol nascer sobre o Alegrete.

Os butiás saltaram um a um dos bolsos do gaudério! Ao abrir a porta, avistou a praia de Mostardas e o Rio Grande a afastar-se. Desta vez, o piá fora longe demais!

Algumas semanas depois, mesmo sob os protestos do prefeito e das ligações constantes ao Palácio do Piratini e ao Palácio da Alvorada, o Alegrete continuava à deriva. Embretado entre a França e a Inglaterra, todos acharam que nunca mais veriam o céu celeste sobre o campo.

Mas, como o leitor já deve ter percebido, essa história não está limitada pela realidade física. Nos dias que se seguiram, o Alegrete  despertou-se nos lugares menos esperados.

Os pobres paisanos tiveram que suportar frio, calor, secura e umidade. Ou seja, um dia normal no Rio Grande do Sul.

O código dessa brincadeira é simples, como se pode ver abaixo. Entretanto, as coordenadas ocupam muito espaço. Então, se alguém quiser replicar o experimento com seu próprio município, basta pedi-las!

<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="initial-scale=1.0, user-scalable=no" />
<style type="text/css">
  html { height: 100% }
  body { height: 100%; margin: 0px; padding: 0px }
  div { float: left }
</style>
<script type="text/javascript"
    src="http://maps.google.com/maps/api/js?sensor=true">
</script>
<script type="text/javascript">
  var coordenadas=[...];

  function getCoords() {
    var coords=new Array();
    var bounds = new google.maps.LatLngBounds();
    for(var i=0; i<coordenadas.length; i+=2) {
      var c=new google.maps.LatLng(-coordenadas[i+1],-coordenadas[i]);
      coords.push(c);
      bounds.extend(c);
    }
    coords.bounds=bounds;
    coords.center=bounds.getCenter();
    return coords;
  }
  
  var lat=-29.7640;
  var lng=-55.8861;
      
  function init() {
    var map = new google.maps.Map(document.getElementById("map"),  { 
      zoom: 6, 
      center: new google.maps.LatLng(lat, lng),
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });
    
    var alegrete = new google.maps.Polygon({paths: getCoords(), 
      strokeColor: '#000000', strokeWeight: 1, strokeOpacity: 1, 
      fillColor: '#00AA00', fillOpacity: 0.4,  clickable: false });
    alegrete.setMap(map);
    
    google.maps.event.addListener(map, 'center_changed', function() {
      var point=map.getCenter();
      alegrete.setMap(null);
      var path=alegrete.getPath();
      path.forEach(function(p,i) {
        path.setAt(i, new google.maps.LatLng(p.lat()-(lat-point.lat()), 
                                             p.lng()-(lng-point.lng())));
      });
      lat=point.lat();
      lng=point.lng();
      alegrete.setPath(path);
      alegrete.setMap(map);
    });
  }

</script>
</head>
<body onload="init()">
  <div id="map" style="width:400px; height:400px"></div>
</body>
</html>

A navegação é a original do Google Maps. A cada mudança de centro do mapa (indicada pelo evento center_changed), o código corrige as coordenadas do Alegrete. Pode-se notar claramente que a forma distorce-se nas aproximações aos polos; é defeito da projeção.

Segundas intenções

Um amigo, passeando por Portugal, achou-se perdido e resolveu pedir ajuda a um paisano. Com a obtusidade típica dos brasileiros, disse "Eu queria ir a Braga". Luso-descendentes, como eu, logo compreendem o erro do pobre tupiniquim e não têm muita dificuldade para imaginar a resposta: "Pois vá".

Essa forma direta de dialogar dos portugueses gera uma infinitude de piadas no Brasil, muitas das quais são baseadas em fatos. Creio que seja uma injustiça e que engraçados sejamos nós, os brasileiros. Nossa forma indireta de perguntar e responder gera muitas confusões. Já que as pessoas perguntam por segunda intenção, os interrogados passam a interpretar os questionamentos e daí só podem surgir dificuldades.

Há pouco tempo, pedi a um pintor que pintasse uma parede em azul até 123cm e em azul celeste dali até o teto. A ordem não podia ser mais clara. No entanto, ele deu-se ao trabalho de interpretar a minha ordem, já que sabia que eu queria colocar uma faixa ornamentada com bichinhos para meu filho. Ele colocou a faixa com a base em 123cm, quando a metade dela deveria estar nessa altura. Se o pintor fosse português, tenho certeza que minha ordem, mais que clara, não seria (mal) interpretada.

Noutro incidente recente, atendi uma ligação para uma colega. A pessoa que chamou disse "Fulano, a Beltrana...". Fiquei suspenso por uns segundos esperando um verbo. A Beltrana morreu? A Beltrana esqueceu de vir para a reunião? A Beltrana está? A Beltrana pediu para avisar que vai chegar tarde? A Beltrana pediu alguma coisa? Enquanto o analisador sintático esperava pelo complemento, o subsistema de previsão de intenções lançou um aviso: essa criatura provavelmente quer falar com a Beltrana. Encaminhei a ligação e torci pelo melhor.

Imagino o horror se os programadores brasileiros levassem essa filosofia para seu código. Por exemplo, um método para indicar se há fundos necessários para efetuar uma retirada poderia ser escrito da seguinte forma:

public Status podeRetirar(double valor) throws FundosInsuficientesException {
  if(saldo-valor<0) {
    throw new FundosInsuficientesException();
  }
  return getStatus();
}

Ou seja, o método, se houver fundos, retorna o status da conta (encerrada ou bloqueada, por exemplo), mas se não houver fundos, lança uma exceção para indicá-lo. Não dá para complicar mais uma coisa tão simples.

Outro defeito grave da comunicação tupiniquim é a falta de cortesia básica. É comum caminhar pela rua e ser surpreendido com um "Que horas são?" ou "Onde fica a rua da Ladeira?". Faltam "Bom dia", "Por favor" e "Com licença", cujos propósitos, antes de mais nada, são os de permitir ao cidadão mudar de contexto e preparar-se para iniciar um diálogo.

Se o TCP/IP tivesse sido projetado por um brasileiro, não haveria o handshake (SYN, SYN-ACK, ACK), mas surgiria a necessidade de uma mensagem HEIN, para quando o servidor não estiver preparado para iniciar uma conexão.

Os mal-entendidos cotidianos devem custar um bocado ao Brasil, então é de se espantar que os personagens principais das piadas ainda sejam o Manoel e o Joaquim.

Coundown Sort II

O Countdown Sort foi otimizado! Infelizmente, a melhoria custou um if adicional. Mesmo assim, como o algoritmo agora está quatro vezes mais rápido, acho que valeu a pena.

O algoritmo original percorria todo o array subtraindo 1 de cada elemento e anexando os que chegavam a 0 a um array ordenado. Evidentemente, não é preciso percorrer os elementos que já chegaram a 0, então resolvi tirá-los da jogada.

  public static short[] countdownSort(short in[]) {
    short[] order=new short[in.length];
    int index=0;
    short delta=0;
    int last=in.length-1;
    do {
      for(int i=last; i>=0; i--) {
        if(in[i]-delta==0) {
          order[index]=in[i];
          index++;
          if(i<last) {
            in[i]=in[last];
          }
          last--;
        }
      }
      delta++;
    } while(last>=0);
    return order;
  }

Agora, sempre que encontrar um 0, o algoritmo o troca pelo último elemento do array original e diminui em uma posição a abrangência da busca. Se justamente o último elemento é que chegou a 0, então basta subtrair 1 do índice que aponta para o fim do array (representado no código pela variável last).

Isso significa que o array original será destruído, mas, como o método retorna uma versão ordenada dos números, o problema não é grave.

Paira ainda no ar a dúvida sobre se algo realmente útil pode advir deste algoritmo.

Chocolate e Jurupiga

O chocolate é a bebida sagrada do Novo Mundo, enquanto a Jurupiga é o vinho vira-latas da Europa. São opostos que combinam muito bem. O álcool traz o otimismo para a criação e o amargo do chocolate ajuda na concetração. A combinação é divina. Com a ajuda deles, escrevi um pouco de Javascript para juntar dois mapas antípodas do Google Maps numa só tela. Quando se muda a posição ou a ampliação do mapa da esquerda, o da direita ajusta-se automaticamente para que seu centro seja o antípoda do centro do outro.

Infelizmente, o antípoda do Rio Grande do Sul está no meio do mar entre o Japão e a China. Por outro lado, esta deve ser a única região da Ásia tão despovoada quanto o Pampa.

<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="initial-scale=1.0, user-scalable=no" />
<style type="text/css">
  html { height: 100% }
  body { height: 100%; margin: 0px; padding: 0px }
  div { float: left }
</style>
<script type="text/javascript"
    src="http://maps.google.com/maps/api/js?sensor=true">
</script>
<script type="text/javascript">
  function init() {
    var lat=-29.683889;
    var lng=-53.806944;

    var here = new google.maps.Map(document.getElementById("here"),  { 
      zoom: 8, 
      center: new google.maps.LatLng(lat, lng),
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });

    var there = new google.maps.Map(document.getElementById("there"), { 
      zoom: 8, 
      center: new google.maps.LatLng(-lat, 180-Math.abs(lng)),
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });
    
    google.maps.event.addListener(here, 'zoom_changed', function() {
      there.setZoom(here.getZoom());
    });
    
    google.maps.event.addListener(here, 'center_changed', function() {
      var point=here.getCenter();
      var sign=point.lng()<0?1:-1;
      there.setCenter(new google.maps.LatLng(-point.lat(), 
        sign*(180-(Math.abs(point.lng())))));
    });
  }

</script>
</head>
<body onload="init()">
  <div id="here" style="width:400px; height:400px"></div>
  <div id="there" style="width:400px; height:400px"></div>
</body>
</html>

O código foi testado no Chrome, no Firefox e no IE. Em todos funciona, mas é no Chrome que ele roda mais rápido.

Countdown Sort

Resolvi tentar melhorar o Sleep Sort contando alguma coisa diferente e mais rápida que o tempo. A minha primeira idéia foi contar números e usar os próprios elementos desordenados como medida. Então, cheguei ao Countdown Sort.

A idéia é muito simples: subtraio 1 de cada elemento e a ordenação ocorre naturalmente ao passo que os números forem alcançando o zero. O desempenho é terrível, mas o algoritmo é meu e está pago. Além disso, ele não faz nem comparações nem trocas de elementos e isso já é interessante por si só.

Eis o código em Java:

  public static short[] countdownSort(short in[]) {
    short[] order=new short[in.length];
    int index=0;
    short delta=0;
    do {
      for(int i=in.length-1; i>=0; i--) {
        if(in[i]-delta==0) {
          order[index]=in[i];
          index++;
        }
      }
      delta++;
    } while(index<in.length);
    return order;
  }

Um possibilidade interessante é a de implementá-lo em código de máquina, já que todas as CPUs têm instruções para subtrair 1 e comparar com 0. Parece-me que o código seria bem pequeno.

Um pequeno teste mostra que o algoritmo funciona mesmo com elementos repetidos:

  public static void main(String... args) {
    short[] ordered=countdownSort(new short[] {
       2, 40, 33, 1, 100, 4, 2, 0, 0, 1024
    });
    for(short v: ordered) {
      System.out.printf("%d,", v);
    }
  }

%java CountdownSort
0,0,1,2,2,4,33,40,100,1024,

Agora, tenho que achar uma maneira de acelerar a contagem.

Sleep Sort

Alguns algoritmos têm pouco valor prático, mas grande valor didático. Há poucas horas foi criado mais um destes (vale ouro presenciar o nascimento de um novo algoritmo de ordenação!): o Sleep Sort. Ele é tão novo, que não tem página na Wikipédia ainda.

O algoritmo é simples: para cada número x, deixam-se passar x unidades de tempo para adicioná-lo à lista ordenada. Quanto maior o valor de x, mais tempo ele precisará esperar e, portanto, mais para o fim da lista ficará posicionado.

Minha solução em Javascript é esta:

function sleepSort(n,callback) {
  var out=new Array();
  for(i in n) {
    var x=n[i];
    var pusher=function(x) {
      return function() { 
        out.push(x); 
        if(out.length==n.length) {
          callback(out);
        }
      };
    }(x);
    setTimeout(pusher, x*100);
  }
}

Como o método setTimeout() usa milissegundos como unidade, multiplico o valor de cada elemento por 100, para ter certeza que haverá tempo suficiente entre eles para não haver confusão.

Quando o último elemento for adicionado, a nova lista estará tão grande quanto a original e a função de callback será chamada. Dada a natureza do algoritmo, não é possível retornar imediatamente o resultado a partir de sleepSort().

O lado didático desse exercício é que ele ajuda a esclarecer como funcionam as closures do Javascript. Eu uso uma função que cria outra função, porque as closures têm referências às variáveis do contexto que as circunda. Logo, sem a função anônima intermediária, todas as chamadas usariam o último valor atribuído a x. Como a função intermediária recebe o x como parâmetro e os parâmetros são passados por cópia, o x da função mais aninhada é cópia e não referência do x original. Logo antes da chamada a setTimeout() está a chamada à função intermediária.

Segue um teste simples:

sleepSort([19,48,61,3,10,20,45,33],
  function(result) { 
    alert(result.join(",")); 
  }
);

Só falta nessa função uma maneira de tirar aquele if intrometido.

P.S. No dia 17/06/2011 surgiu uma entrada na Wikipédia sobre o Sleep Sort.

Transformando colunas em linhas

Um problema que de tempos em tempos surge é o de transformar colunas em linhas no SQL. Os bancos que têm facilidades de XML, como o DB2 e o Oracle, oferecem a possibilidade de resolver isso através do SQL/XML, que é uma extensão padronizada do SQL.

A consulta abaixo mostra como é simples usar essa extensão:

SELECT *
FROM XMLTABLE ('ROWSET/ROW/*' PASSING
     DBMS_XMLGEN.GETXMLTYPE('select 17,25,39 from dual') 
     COLUMNS val VARCHAR2(8) PATH '.'
) X


 17 
 25 
 39 
 

A rotina DBMS_XMLGEN.GETXMLTYPE recebe uma consulta e retorna um XML com a seguinte forma:

<ROWSET>
 <ROW>
  <_x0031_7>17</_x0031_7>
  <_x0032_5>25</_x0032_5>
  <_x0033_9>39</_x0033_9>
 </ROW>
</ROWSET>

Com XMLTABLE, realiza-se o caminho inverso. A expressão 'ROWSET/ROW/*' nos indica que queremos todos os nodos filhos de nodos do tipo ROW. Depois da chamada a DBMS_XMLGEN.GETXMLTYPE há uma descrição dos tipos para os quais as colunas devem ser convertidas.

O primeiro select retornava linhas de apenas uma coluna. Para extrair o nome de cada coluna, é preciso fazer o seguinte:

SELECT x.column_value.getrootelement(), x.column_value.extract('//./text()')
FROM XMLTABLE ('ROWSET/ROW/*' PASSING
     DBMS_XMLGEN.GETXMLTYPE('select 17 as A,25 as B,39 as C from dual')
) X


 A 
 17 
 B 
 25 
 C 
 39 
 

Essa consulta funciona no Oracle 10g. O DB2 e o Oracle 11g tem suporte melhor para o XPath e, portanto, permitem maiores estrepolias.

A língua sabe de si

A língua está na boca dos gaúchos. Antes de discutirmos as dificuldades de viver sem estrangeirismos, havíamos sido atormentados pela polêmica dos livros escolares que ensinam que não é errado falar mal o português.

Nossa mídia nos confunde. Ora é ridículo traduzir estrangeirismos, ora é importante apontar o erro na língua alheia. Mas a confusão é mais antiga que essas duas discussões, alimentadas, sem dúvida, com o objetivo de vender mais escândalos.

Há décadas os jornais ignoram a ortografia. Os erros, há inúmeros deles todos os dias em todos os jornais (poucos jornalistas parecem saber que o verbo implicar é transitivo direto, por exemplo), mas o que realmente salta aos olhos são os nomes.

Segundo Marcos de Castro (no livro A Imprensa e o Caos na Ortografia), até o fim dos anos 1970, os jornais brasileiros respeitavam a língua portuguesa. Os nomes eram escritos como manda a regra. Ulisses e não Ulysses; Luís e não Luiz; Ademar e não Adhemar. Então, o general Golberi, afeito apenas a suas próprias regras, cismou que seu nome tinha que ser grafado conforme o equivocado progenitor o havia rabiscado: Golbery.

Desde então, a criatividade na grafia dos nomes próprios só tem aumentado. A cidade de Parati agora é Paraty e o Itamarati virou Itamaraty. Por sorte, o limite parece ser o teclado do escrivão; sem esse entrave, logo estaríamos sujeitos a símbolos, caracteres estrangeiros e logogramas asiáticos. Ai se descobrem o mapa de caracteres do Windows!

Há o seguinte parágrafo no polêmico livro "Por uma vida  melhor", do MEC:

'Os livro ilustrado mais interessante estão emprestado'. Você pode estar se perguntando: 'Mas eu posso falar ‘os livro?’.’ Claro que pode. Mas fique atento porque, dependendo da situação, você corre o risco de ser vítima de preconceito linguístico. Muita gente diz o que se deve e o que não se deve falar e escrever, tomando as regras estabelecidas para a norma culta como padrão de correção de todas as formas linguísticas. O falante, portanto, tem de ser capaz de usar a variante adequada da língua para cada ocasião

É prova inconteste da infiltração esquerdista no governo, porque, todos sabemos, não existe preconceito no Brasil. A imprensa, provado está, toma de braços abertos todas as formas de grafia. Com erros de concordância, não sei bem dizer o motivo, ela não tem tanta compreensão. Arrisco-me a conjecturar que a gravidade dos erros seja proporcional ao nivel sócio-econômico do errado. Eu devo ser comunista enrustido.

Antes mesmo dos jornais esquecerem essa história toda, um deputado comunista (a que ponto chegamos!) propõe que sejam traduzidos os estrangeirismos. A mídia regozijou-se. Um jornalista (provavelmente muito ocupado transcrevendo os textos da Reuters para procurar um dicionário) lançou uma lista de palavras únicas que, por sorte, seus leitores ajudaram a traduzir. O coitado não sabia como traduzir tsunami, mas logo apontaram para maremoto e vagalhão. Agora ele tem até escolha (parece que seu patrão não tinha muitas ao contratá-lo).

Então, vou propor umas adições ao livro do MEC. Sugiro o seguinte parágrafo:

Nos jornais, frequentemente encontramos erros como 'Ulysses Guimarães não estava presente no impeachment de Fernando Collor de Mello, porque havia morrido poucas semanas antes'. O correto seria 'Ulisses Guimarães não estava presente ao impedimento de Fernando Collor de Melo, porque havia morrido poucas semanas antes'. No entanto, não devemos mostrar preconceito contra trabalhadores que, tendo pouco tempo para preparar a edição do dia seguinte, não corrigem seus textos, mesmo com todas as facilidades oferecidas pelos computadores modernos.

Os erros do texto são meus e não da língua. Ela sabe de si e eu cuido de mim. Fernando Pessoa, que disso tudo entende muito mais que eu, mas que, tristeza nossa, está morto há muito tempo, escreveu e basta para terminar meu argumento:

Obedeça à gramática quem sabe pensar o que sente. Sirva-se dela quem sabe mandar nas suas expressões. Conta-se de Sigismundo, Rei de Roma, que tendo, num discurso público, cometido um erro de gramática, respondeu a quem dele lhe falou, "Sou Rei de Roma, e acima da gramática". E a história narra que ficou sendo conhecido nela como Sigismundo "super-grammaticam". Maravilhoso símbolo! Cada homem que sabe dizer o que diz é, em seu modo, Rei de Roma. O título não é mau, e a alma é ser-se.

Pérolas dos usuários IV

Os usuários são surpreendentemente criativos, não há dúvida. Com todos os anos de enfrentamento, eles ainda produzem feitos embasbacantes. A última, eu nunca esperaria acontecer.

Um usuário, quando deveria preencher o formulário e premir o botão "Enviar", imprimou-o vazio e o completou à mão. Creio que seja uma manifestação pós-moderna contra a intrusão das máquinhas nas relações interpessoais.

Por sorte, o CSS está aí para nos salvar. Com uma pequena adição à página, estão impedidos os usuários de imprimir o formulário.

@media print { body { display: none;} }

Fico em dúvida se não vou receber reclamações de que a impressão não está funcionando. Então, penso em adicionar algo como:


Calma! Nada deu errado. No entanto, o sistema detectou que tu não leste o manual.Para podermos prosseguir, é necessário que leias as instruções cuidadosamente.

Power Sort em Java II

Tendo percebido (e logo relevado) que Power Sort é um caso especial do Counting Sort, decidi continuar investindo neste ramo da tecnologia ifless.

Começando pelo caso mais simples (ordenar apenas números inteiros sem repetições), encontrei uma solução muito simples com a classe BigInteger.

public static void psort(int[] in) {
    BigInteger TWO=new BigInteger("2");
    BigInteger pp=BigInteger.ZERO;
    for(int i=0; i<in.length; i++) {
     pp=pp.add(TWO.pow(in[i]));
    }    
    
    for(int i=0; i<in.length; i++) {
     in[i]=pp.getLowestSetBit();
     pp=pp.flipBit(in[i]);
    }
}

O código funciona em duas etapas. Na primeira, o número pp recebe cada elemento do array in como uma potência de 2. Ou seja, pp+=2^in[i]. Na segunda parte, a posição do i-ésimo bit indica o valor da i-ésima casa do array já ordenado. Como não há um método para percorrer os bits 1, uso o método flipBit() para negar o primeiro e fazer do próximo o primeiro.

O código abaixo mostra um teste com um pequeno array de 200 posições.

import java.math.BigInteger;

public class PowerSort {

  public static void psort(int[] in) {
    BigInteger TWO=new BigInteger("2");
    BigInteger pp=BigInteger.ZERO;
    for(int i=0; i<in.length; i++) {
     pp=pp.add(TWO.pow(in[i]));
    }    
    
    System.out.println(pp);
    
    for(int i=0; i<in.length; i++) {
     in[i]=pp.getLowestSetBit();
     pp=pp.flipBit(in[i]);
    }
  }
  
  public static void main(String... args) {
    int[] test=new int[200];
    for(int i=0;i<200;i++) {
      test[i]=200-i;
    }    
    psort(test);
    for(int i : test) {
      System.out.printf("%d ", i);
    }
    System.out.println();
  }

}

O array começa com os valores 200 a 1 e os ordena para a ordem crescente. O valor final de pp é o respeitável e impronunciável

3213876088517980551083924184682325205044405987565585670602750

Quanto maiores os números, tanto maior ficará pp e, portanto, mais memória será usada para executar a ordenação. Se os valores forem conhecidos de antemão, será muito mais econômico usar um mapa de bits.

As vantagens de contratar pais

Os pais, através de árduo treinamento, ganham habilidades que são preciosas. Os pais programadores e analistas de sistemas podem orgulhar-se de:

• Trabalhar sob muita pressão e pouco sono;
• Manter-se calmo mesmo frente à furia do chefe (ou à do cliente);
• Seguir o processo sem pestanejar;
• Manter-se otimista mesmo ante a impossibilidade de alento nos próximos dez anos;
• Alegrar-se com as menores coisas (um soriso ou um café com leite num dia frio);
• Não ter nem medo nem nojo de sujar as mãos (e a camisa e a calça).

Ficção contábil

Há muita reclamação sobre os impostos no Brasil, mas creio que o maior problema está na quantidade e complexidade deles. As alíquotas são o menor dos problemas.

Com relação aos encargos sociais, algumas pessoas aproveitam-se da complexidade dos cálculos para criar problemas que não existem. O número mais citado nessas discussões é o de 102%. Argumenta-se que sobre um salário incidem 102% de encargos sociais.

O cálculo envolve o seguinte (dados do DIEESE):

• A - Obrigações sociais 35,80%
  
  • Previdência Social 20,0%
    
  • FGTS 8,0%
    
  • Salário-educação 2,5%
    
  • Acidentes do trabalho (média) 2,0%
    
  • Sesi 1,5%
    
  • Senai 1,0%
    
  • Sebrae 0,6%
    
  • Incra 0,2%
    
• B - Tempo não trabalhado 38,23%
  
  • Repouso semanal 18,91%
    
  • Férias 9,45%
    
  • Feriados 4,36%
    
  • Abono de férias 3,64%
    
  • Aviso prévio 1,32%
    
  • Auxílio-enfermidade 0,55%
    
• C - Tempo não-trabalhado 13,48%
  
  • 13º salário 10,91
    
  • Despesa de rescisão contratual 2,57%
    
• D - Reflexos dos itens anteriores 14,55%
  
  • Incidência cumulativa do grupo A sobre o B 13,68%
    
  • Incidência do FGTS sobre o 13º salário 0,87%
    

O item mais caro é a contribuição de 20% à Previdência Social. Não há dúvida de que seja um encargo social, mas também é difícil argumentar por seu fim.

Os problemas começam mesmo com o décimo-terceiro salário, o repouso semanal e o adicional de férias. Em primeiro lugar, décimo-terceiro e adicional de férias são salário, porque vão para o bolso do empregado. No momento em que negociam o salário, tanto o empregador como o empregado sabem que esses valores compõem o salário anual. Não se pode alegar que o valor é cobrado injustamente pelo governo a posteriori, justamente porque o empregador pode negociar um valor mais baixo para compensá-lo (o menor salário que o empregador pode oferecer é o salário mínimo, ou R$7.248 anuais ou cerca de R$3,43 por cada hora efetivamente trabalhada).

No entanto, nos detalhes encontramos cálculos reveladores. Os contracheques costumam ter um número mágico de 220h de trabalho, mas não há mês com tantos dias de trabalho. Convencionou-se um mês comercial de 5 semanas (com 44h semanais, esse mês tem 220h). Alguns usam esse número como prova de que pagam-se mais horas do que são trabalhadas, mas a verdade é que ele é vantajoso para o empregador, porque significa que as horas extras são mais baratas. Se em um mês um trabalhador ganhou R$1.000 por 176h de trabalho, isso significa que ele ganhou R$5,68 por hora efetivamente trabalhada. Mas as horas extras são calculadas sobre 220h e, portanto, elas são remuneradas por R$4,54 a hora (com os devidos adicionais).

Ademais, não se pode alegar que o descanso remunerado seja um encargo, porque ele não é adicionado ao salário. Se o salário acordado é X, então X será o salário mensal e uma conta convencionará o quanto vale o fim-de-semana.

O décimo-terceiro é também uma criatura interessante. Um salário mensal de R$1.000 indica um salário semanal de R$250. Há 52 semana num ano e portanto, o salário anual deveria ser de 52 vezes R$250 ou R$13.000; sem o décimo-terceiro, ele seria de apenas R$12.000. Ou seja, o décimo-terceiro devolve ao empregado as horas que ele trabalhou a mais nos meses com mais de 22 dias úteis. Se descontássemos o mês de férias, teríamos novamente R$12.000 (48*R$250), mas então as férias não seriam remuneradas. Isto é, em um ano, o empregado trabalha 48 semanas (47 descontando os feriados) e recebe por 53,3 (um bônus de 13%), enquanto há quem queira fazer creer que sejam 11 meses trabalhados por 13,3 salários (um bônus de 21%).

Se trabalhasse 220h todo mês, um empregado acumularia 2420h nos 11 meses trabalhados do ano. Na verdade ele trabalha menos de 2112 (44h por 48 semanas). Então, as 220h ajudam a diminuir o valor da hora-extra em cerca de 14%.

Logo, os números acima só reforçam o fato de que itens importantes do salário não devem ser confundidos com encargos sociais. Outros itens não são tão claros, como FGTS e multa por rescisão e outros claramente são encargos, como as contribuições.

Finalmente, para tornar o processo mais claro, deveríamos fazer como os americanos, que negociam o salário anual, mas pagam/recebem semanalmente.

Realidade fantástica

Um ser humano adulto gasta algo como 100W apenas para manter-se dormindo (metabolismo basal). Esse número por si só já é impressionante, mas quando o comparamos ao sol é que algo surpreendente aparece.

O sol tem uma massa na ordem de 10³⁰kg e uma luminosidade na ordem de 10²⁶W. Isso significa que ele produz algo na redondeza de 10^-4W/kg, enquanto os seres humanos estão mais perto de 1W/Kg.

A conclusão simples é a de que um ser humano irradia cerca de 10 mil vezes mais calor que uma massa equivalente do sol irradia.

Para nos diferenciar dos outros seres vivos, criamos muitos objetos, utilizamos veículos, iluminamos as noites e aclimatamos nossas casas. De acordo com segunda lei da termodinâmica, os sistemas fechados tendem ao equilíbrio. Isto é, as diferenças de temperatura desaparecem e o sistema torna-se homogêneo com o tempo. A vida acelera esse processo e o ser humano o industrializa!

Para criar um pouco de ordem em nossos lares, exportamos muito caos para o meio-ambiente. E como há cada vez mais gente no planeta, há cada vez menos espaço para o caos que criamos. Se os pólos estão derretendo é porque o homem está cumprindo seu papel de quebrar os gradientes e homogeneizar a temperatura no sistema (mais ou menos) fechado que é a terra.

Só precisamos agora decidir se isso nos convém.

Power Sort em Java

Pesquisando uma maneira de ordenar números sem usar ifs, acabei tropeçando no Power Sort (e aqui e aqui).

Quando finalmente resolvi escrevê-lo em Java, percebi que era uma variação do Counting Sort. Com quase sete bilhões de pessoas na terra, é difícil ter uma idéia original. De qualquer forma, o Power Sort é um caso especial muito interessante do Counting Sort, porque:

• Usa pouquíssima memória;
• É ainda mais rápido e
• Não precisa de ifs!

O Counting Sort usa um array enquanto o Power Sort usa uma ou duas variáveis numéricas. Por isso, o Power Sort fica restrito a conjuntos menores de dados (para não provocar um overflow).

O código abaixo é o de um Counting Sort muito simples. Ele não considera números negativos e faz a ordenação no mesmo array que recebe.

public class CountingSort {

  public static short[] sort(short[] in) {
    int[] order=new int[32768];
    for(int i=0;i<in.length;i++) {
      order[in[i]]++;
    }
    int index=0;
    int n=0;
    while(n<in.length) {
      while(order[index]==0) {
        index++;
      }
      for(int i=0; i<order[index]; i++) {
        in[n+i]=(short)index;
      }
      n+=order[index];
      index++;
    }
    return in;
  }

}

A idéia é simples. Os shorts positivos vão de 0 a 32767, então o array order representa quantas vezes cada número apareceu em in. Como o índice de order já representa a posição de cada número, só preciso copiar as casas maiores que zero de volta para o array original (as que tem zero representam números que não estão em in).

O interessante desse algorítmo é que ele só precisa olhar para os dados uma vez; ele não precisa de comparações; e tampouco faz trocas. O que ele produz é uma espécie de transformada dos dados.

E o desempenho é excelente. O gráfico abaixo mostra uma comparação com o Quick Sort (através do método Arrays.sort())

No eixo vertical estão os tempos em milissegundos e no eixo horizontal estão as quantidades de elementos ordenados. Testei de um em um milhão até quarenta milhões.

Quatro dimensões em duas

O gráfico do último artigo tinha três dimensões (população, renda e longevidade) comprimidas nas duas dimensões de uma imagem. Neste, vou adicionar mais uma: educação.

O eixo horizontal representa as populações. Portanto, as maiores cidades estão mais à direita. O eixo vertical representa a renda. Logo, as cidades mais ricas estão mais altas que as mais pobres. A longevidade apareceu como cor: quanto mais claro o círculo, mais experiente a população.

Como todas as cidades foram representadas por círculos com o mesmo raio (6 pontos), resolvi usar o tamanho de cada círculo para indicar o índice de educação. A diferença entre o maior e o menor índices é de 0,188. Para simplificar, simplesmente multiplico a diferença entre cada índice e o menor (0,763) por 100. O resultado são raios entre 4 e 18 que, não sendo proporcionais, pelo menos realçam as diferenças.

A consulta é a seguinte:

select 'fill(0,'||w||',0);ellipse('||x||','||y||','||d||','||d||');' 
from (  
  select trunc(log(10,habitantes)*100)-300 x,
         500-trunc(avg(renda)*500) y,
         trunc(avg(longevidade-0.651)*1000) w,
         trunc(avg(educacao-0.763)*100) d
  from municipios
  group by trunc(log(10,habitantes)*100)-300
)
order by d desc

Usei verde para tornar o gráfico mais interessante. Além disso, ordenei os índices em ordem descendente para que os círculos maiores não fossem desenhados sobre os menores.

O resultado é a imagem abaixo:

Aparentemente, a educação melhora a renda. Ou talvez seja o contrário.

Renda e longevidade

Depois de gerar um gráfico para relacionar renda com população das cidades gaúchas, resolvi adicionar mais uma dimensão: a longevidade.

Para demonstrar a longevidade, resolvi usar cor. No gráfico anterior, usei linhas para mostrar o nível de renda. Neste, usei círculos. As alturas refletem a renda, como no gráfico anterior, e a cor indica a longevidade da população.

select 'fill('||w||');ellipse('||x||','||y||',6,6);' from (  
  select trunc(log(10,habitantes)*100)-300 x,
         500-trunc(avg(renda)*500) y,
         trunc(avg(longevidade-0.651)*1000) w
  from municipios
  group by trunc(log(10,habitantes)*100)-300
)

Como a longevidade varia de 0,651 a 0,879, usei a diferença entre cada índice e o mínimo para realçar as diferenças. Caso contrário, todas sairiam com um cinza parecido e o gráfico não seria nada interessante.

A consulta produz linhas com o seguinte formato:

fill(117);ellipse(72,176,6,6);

E o resultado é a imagem que segue:

 

Parece-me que quanto maior a cidade, maior deve ser a renda para que aumente a longevidade.

Processando...

Nos anos 1980, Logo era usada para ensinar matemática e programação para crianças. As que tomaram gosto pela coisa devem agora estar brincando com Processing, caso não tenham crescido nessas três décadas.

Graças a uma exibição interessantísima, resolvi provar um pouco desse novo brinquedo. Construída sobre Java, a linguagem aparentemente não acrescenta grandes coisas. Mas as aparências enganam muito!

Comecei buscando um conjunto de dados interessantes. Encontrei uma tabela de desenvolvimento social dos municípios do Rio Grande do Sul. A consulta abaixo gera comandos que uso no Processing para criar um gráfico.

select 'line('||x||',500,'||x||','||y||');' from (
  select trunc(log(10,habitantes)*100)-300 x, 500-trunc(avg(renda)*500) y
  from municipios
  group by trunc(log(10,habitantes)*100)-300
)

Para que a imagem não ficasse muito grande, comprimi os índices de renda (que variam de 0 a 1 com 3 casas de precisão) em 500 valores. O gráfico que quero gerar relaciona renda per capita com número de habitantes. Para gerar o eixo dos habitantes tirei o logarítmo do número de habitantes e o multipliquei por 100. Assim, tenho coordenadas que variam de 300 (para cidades com milhares de habitantes) até 600 (para cidades com milhões de habitantes). Eu tiro a média da renda e agrupo por ela porque pode haver mais de uma cidade com uma determinada ordem de grandeza de habitantes.

O objetivo da consulta é gerar uma lista de comandos desse tipo:

line(55,500,55,211);
line(108,500,108,174);
line(100,500,100,192);
line(35,500,35,231);
line(123,500,123,195);

Claro, preciso de um pouco mais. Mas Processing facilita tanto a brincadeira, que só preciso do seguinte para completar o meu programa:

size(350,400, JAVA2D);
background(#ffffff);
fill(0);
//Comandos do select
saveFrame("/tmp/idh.png");

O resultado é a imagem abaixo.

Tudo indica que quem quer ficar rico deve procurar uma cidade maior e que quem quer se divertir deve aprender Processing.

Alíquotas contínuas para o Imposto de Renda

A tabela do Imposto de Renda é uma criatura estranha. Em nome da curiosidade matemática, bem que a Receita Federal poderia esclarecer os cálculos que amparam os números.

A tabela abaixo mostra as bases, as alíquotas e as diferenças entre as faixas.

Base (R$)	Diferença para base anterior (R$)	Alíquota (%)	Diferença para alíquota anterior (%)
0	0	0	0
1.499,15	1.499,15	7,5	7,5
2.246,75	747,60	15	7,5
2.995,70	748,95	22,5	7,5
3.743,19	747,49	27,5	5

Então, exceto pela  diferença entre as bases primeira e zerésima, há uma diferença de cerca de R$750 entre elas. E exceto pelas última e pela penúltima alíquotas, há uma diferença de 7,5% entre elas.

A regressão linear mostra que a reta que melhor descreve o crescimento das alíquotas é a de inclinação 0,007 (a cada real, a alíquota cresce 0,007%). Para o primeiro real da última base, por exemplo, essa reta produziria uma alíquota de 26,20% (3743,19*0,007).

O gráfico mostra as alíquotas e a tendência delas (em preto). Porque a escala não é igual nos dois eixos, a linha preta parece muito mais inclinada do que de fato é (eis uma preciosa lição sobre como mentir com gráficos).

O problema de usar essa reta, evidentemente, é que as pessoas pagariam mais impostos e não haveria faixa de isenção. Mas é possível usar a reta a partir de um valor máximo de isenção e até um limite razovável de alíquota. Sem uma alíquota máxima, as pessoas começariam a pagar mais de 100% sobre os valores acima de R$14.285,71.

E como seria calculado esse imposto? Com triângulos, claro!

Ganhando x, calcula-se o imposto assim:

(x²*0,00007)/2.

Considerando uma faixa de isenção f, o cálculo seria:

 (x²*0,00007)/2-(f²*0,00007)/2 ou [(x²-f²)*0,00007]/2.

Um valor hipotético de R$4.000,00 seria tributado em R$407,22 pelas alíquotas normais e em R$486,50 pela alíquota contínua. O valor é maior, porque enquanto as alíquotas permanecem estáveis entre bases no cálculo normal, com a alíquota contínua ela é sempre um pouco maior para cada real adicional (ou mesmo a cada centavo).

Com uma alíquota máxima, o cálculo seria um pouco mais complicado. Se a alíquota máxima for fixada em 40%, o primeiro valor a atingi-la será R$5.714,28 (chamarei isso de M). Então, quem ganhar um salário S acima disso, pagará:

[(M²-f²)*0,00007]/2 + (S-M)*0,40

A primeira parte é constante e podemos reduzir a conta a uma expressão mais simples:

R$1.069,35 + (S - R$5.714,28)*0,40

Para um valor hipotético de R$10.000,00, o imposto seria de R$2.783,64 e, como esperado, um tanto maior que os R$2.057,22 do cálculo normal (se limitássemos a alíquota em 27,5%, então o imposto devido seria de R$2.149,71 e muito mais próximo ao cálculo normal).

Adotando uma alíquota contínua, seria preciso reduzir o ângulo de ataque, já que o próprio fato de ser contínua compensaria as alíquotas menores nos salários mais baixos. Além disso, se há justiça no fato das alíquotas serem progressivas (eu acho que sim, mas isso é tema para outro debate!), uma alíquota contínua seria ainda mais justa.

Claro, alguém pode achar que uma alíquota logarítma seria ainda mais justa, mas isso merece seu próprio artigo!

Trânsito gaúcho II

Sem muito esforço, é possível perceber que ter um carro é muito caro. Baratinho mesmo é andar de táxi.

Eu, por exemplo, estou a 6km do meu trabalho, uso o transporte coletivo e deixo o carro em casa. Todos os dias, portanto, percorro 12km. Em um ano de trabalho, devo percorrer algo como 2.760km (estimo umas 46 semanas de trabalho). Consumindo cerca de 10km/l (o carro não rende muito no centro) a R$2,60 o litro, eu gastaria R$717,60 em combustível.

O seguro adiciona cerca de R$1.600 ao custo de passear de auto. Os impostos, mais uns R$600. Já se foram R$2.917 antes mesmo que eu considerasse a manutenção. Por sorte, o carro é dos bons. Mesmo assim, já precisei trocar os pneus e a bateria em 2 anos de uso (comprei o carro usado). Em manutenção, ele deve consumir uns R$600 por ano, por enquanto. Já são R$3.517 e eu estou sendo otimista nas minhas contas.

Andando de lotação, gasto R$1.840 por ano. A diferença pode parecer razoável, mas eu ainda nem considerei a depreciação e os juros perdidos!

Investindo o preço do carro na poupança, eu ganharia uns R$1.850 em juros por ano. Isso já pagaria a lotação e o principal se manteria igual. Mas ter carro é muito pior que guardar o dinheiro sob o colchão. Em dois anos, ele se desvalorizou cerca de R$3.500 (ante o valor inicial de R$30.000).

Então, a diferença entre manter o meu carro e guardar o dinheiro na poupança é de mais de R$14.200 em dois anos! Isso significa que cada viagem para o trabalho custaria, na realidade, R$15. Dá para ir de táxi. Indo de lotação, eu embolsaria R$22 todos os dias sem fazer nada. Percebe-se logo que um casal, no lugar de ter dois carros, pode considerar ter um motorista e um único veículo.

Deve ser por isso que os motoristas gaúchos estão tão nervosos!

Trânsito gaúcho

O problema do trânsito no Rio Grande do Sul lançou-se na mídia mundial da pior forma possível. Um cidadão sem qualquer senso de civilidade, sem empatia e simplesmente carente de bom senso atropelou um grupo de ciclistas na cidade baixa.

O estado, com apenas 38 habitantes/km², tem uma densidade populacional baixa. No entanto, a mesorregião metropolitana tem mais de 5 milhões dos 10.695.532 de gaúchos. Sua densidade é de 173/km². Já a região metropolitana tem quase 4 milhões desses 5 milhões e uma densidade de 394/km². Finalmente, a cidade de Porto Alegre tem 1,4 milhão e uma densidade de 2.815/km².

Considerando que há, em média, 1,6 pessoas em cada automóvel transitando pelo cidade, é fácil ver como seria impossível adotar o carro como solução universal.  Em São Paulo, a taxa média de ocupação de veículo é inferior a 1,5.

A concentração urbana deveria ser encarada como uma oportunidade, mas o transporte de massa foi ultrapassado pelo automóvel. Os carros fazem o centro de Porto Alegre parar nos horários de pico. Parece óbvio que o carro não é solução, mas as autoridades preferem dar cada vez mais espaço justamente para quem gera o problema.

A infraestrutura viária é paga com o dinheiro de todos os cidadãos, mas apropriada em grande parte pelos condutores de automóveis que, de maneira crescente, estão tornando-se intolerantes com outras formas de transporte. Até mesmo os ônibus são vistos como problema, uma vez que têm faixas exclusivas em algumas avenidas.

É estranho este comportamento dos nossos motoristas, porque o transporte alternativo seria vantajoso para quem continuar sobre quatro rodas. Os engarrafamentos são provocadas por automóveis, não por bicicletas. É um egoísmo cego. Levanta-se até a bandeira do direito de ir e vir, como se houvesse o direito de ir e vir de carro. Dirigir um automóvel é um privilégio que a sociedade outorga a quem ela julga capaz (obviamente, a sociedade tem sido muito leniente).

Tendo presenciado a civilidade do motorista europeu e como ele compartilha o espaço urbano com multidões de bicicletas, não posso compreender por que muitos motoristas gaúchos tenham tanta dificuldade em admitir que seja possível conviver com outros meios de transporte. Não são os carros que são perigosos para os ciclistas, é a forma de agir dos motoristas que coloca os mais fracos em perigo.

Dada a falta de transporte de massa (como um metrô efetivo), o centro de Porto Alegre deveria dar oportunidade a formas alternativas de locomoção e diminuir o incentivo para o carro. Veículos grandes, como caminhões, deveriam ser proíbidos, assim como acontece em muitas cidades européias. Carros com apenas o motorista dentro deveriam ser impedidos de entrar no centro. Um pedágio urbano e menos vagas de estacionamento também poderiam diminuir o incentivo do motorista solitário.

O terrível atropelamento dos ciclistas é um momento crítico. Agora, a sociedade pode escolher se continua no atual caminho, ou se decide que quer realmente resolver os problemas urbanos e melhorar a qualidade de vida da capital.

Sopa celular

O primeiro autômato celular que conheci foi o Hodge-podge. Ele tem as seguintes regras:

1. Cada célula tem N estados (0 a N-1);
2. O próximo estado de cada célula é dado pela média dos estados dos vizinhos mais uma constante k;
3. Quando uma célula chega ao estado N-1, ela volta a zero no próximo passo.

Em geral, inicia-se com ruído e observa-se a ordem que surge. Decidi experimentar com fotografias e, como cada ponto tem três valores (um para cada cor), aproveitei para descobrir que influência isso teria na imagens geradas.

Então, cada célula (ponto da imagem) tem três valores que podem variar de 0 a 255 (256 estados, portanto). No meu experimento, a célula 0 é vizinha da célula 511 (a imagem tem 512 x 512 pontos) tanto no eixo horizontal, como no eixo vertical.

Para não quebrar a tradição, usei a Lena como modelo:

O código foi escrito em Javascript. Inicialmente, testei 27 para a constante k.

Depois, experimentei um k diferente para cada componente da cor: 27 para o vermelho; 37 para o verde; 14 para o azul.

A próxima imagem foi gerada com k=33 igual para os três componentes.

Os desenhos evoluem com o tempo e quanto maior o valor de k, mais rápidas são as transformações.

Se o Brasil...

Se o Brasil tivesse a densidade populacional da Itália, teria 1.707.415.311 habitantes (um terço a mais que a China). Mas se tivesse a densidade populacional da Mongólia, teria apenas 14.898.850 (um pouco mais que a cidade de São Paulo).

Se o Brasil tivesse a renda per capita de Portugal (US$22.027), seria a quarta maior economia do mundo com cerca de US$4,2 trilhões (atrás dos EUA, da China e do Japão, mas à frente da Índia).

Se o Brasil, em relação a sua população, tivesse tantos servidores públicos quantos tem o Reino Unido, teria 18 milhões. Os britânicos têm 6 milhões de trabalhadores no setor público (para uma população de 62 milhões), enquanto o Brasil tem 8 milhões (nas três esferas) para 190 milhões de habitantes.

Se o Brasil, em relação a sua população, tivesse tantos estados quantos têm os alemães, teríamos 37 (eles têm 16, nós temos 27). Se tivéssemos tantos municípios quantos distritos os alemães têm, teríamos 1.150 (eles têm 493 distritos e nós temos 5.564 municípios). Em média, os municípios do Brasil têm 34 mil habitantes, enquanto cada distrito alemão tem 186 mil. O excesso de burocracia no Brasil está concentrado na esfera municipal.

Se o salário mínimo do Brasil, em relação ao seu PIB per capita, fosse igual ao dos Estêites, ele valeria cerca de R$334. Lá, o salário mínimo federal é de US$7,25 por hora, enquanto aqui pagam-se cerca de R$3 por hora.

Se as regiões brasileiras tivessem que manter a relação entre seus salários mínimos e seus PIBs per capita conforme o salário mínimo federal (R$545 sobre R$14.700), no nordeste (a região mais pobre) ele seria de R$250, enquanto no sudeste (a região mais rica) ele seria de R$714.

Absenteísmo

É engraçado como essas pessoas que abordam na rua para evangelizar não deixam em paz quem responde ser ateu. Quem disser que é Judeu ou Budista pode seguir seu caminho tranquilamente, mas, se for ateu, vai ter que ouvir a mensagem até o fim.

Eu conheci um sujeito particularmente perturbado que ia até a parada de ônibus e gritava que "o anjo negro está vindo". Talvez o anjo negro fosse um motorista daquela linha e nunca descobri se isso era bom ou ruim.

Pois bem, ateus costumam ser bastante convictos de sua escolha, ao contrário dos religiosos em geral. Conheço muitos católicos que frequentam centros espíritas ou casas de umbanda. Ateus também gostam muito de discutir suas crenças, enquanto pessoas religiosas costumam ficar ofendidas.

No entanto, discutir religião (ou falta dela) com profetas de esquina não é lá muito divertido. Portanto, a melhor opção é apenas indicar uma religião e evitar confrontos. A minha opção é o Absenteísmo.

Em poucas palavras, o Absenteísmo prega que Deus existe, mas que não está. Não temos sequer certeza sobre se Ele sobreviveu à criação. Pode ser que Ele tenha morrido no Big Bang. Pode ser que a mãe d'Ele o tenha colocado de castigo por ter bagunçado a cozinha. De uma forma ou outra, Ele não está aqui ou nas redondezas. Se estivesse, certamente daria sinais claros de sua presença e teria uma conta no Facebook, pelo menos.

Criei uma divisão sectária como forma de dar mais veracidade à crença. Os absenteístas cômicos formam um grupo fudamentalista que alega que Deus não aguentou a falta de humor da humanidade e foi embora. Enquanto as pessoas gastarem seu tempo em atividades sérias, como ir ao culto ou participar de romarias, Ele não voltará. Levantar a questão da óbvia falta de esportividade de Deus neste ponto causa grande estresse (que eles insistem não constituir mau humor) aos seguidores dessa linha. Assim como noutras religiões, os absenteístas fundamentalistas não percebem as contradições em seus dogmas.

Seja qual for a linha do absenteísta, ele não é compelido a comparecer a nenhum culto (quem vai ouvir as preces??). A corrente fundamentalista, porém, sugere ler Douglas Adams e assistir The Big Bang Theory ao menos uma vez por semana por se Ele resolver dar uma incerta.

Os absenteístas devem pagar o Písimo que, obviamente, é 3,141592% do rendimento anual do fiel (os valores podem ser creditados na minha conta do PayPal). Gastos com educação e diversão podem ser deduzidos. A beleza do Písimo é que a precisão pode ser aumentada para acomodar os fiéis muito ricos ou que ganham salário em dólares do Zimbábue.

O Absenteísmo vem com uma licença GPL. Logo, qualquer um pode criar sua crença derivada. Já antevejo que alguém vai lançar o Absenteísmo Orientado a Objetos, por exemplo. No entanto, reservo-me todos os direitos sobre adesivos de para-choques.

Eu não mantenho registro dos fiéis, mas tenho notícias de que no Congresso Nacional a bancada absenteísta já é bastante numerosa.

Estilos de gerência

Já li bastante sobre gerência (de pessoas, de projetos, etc) e gostaria de dar minha contribuição para a taxonomia de estilos gerenciais.

Vou apresentar dois: britânico e tupiniquim. Os nomes têm origem nas histórias (breves) que relatarei a seguir e não significam que uma empresa britânica não possa ter um estilo tupiniquim de gerência ou vice-versa. As duas histórias são da segunda grande guerra e são verdadeiras.

A primeira é a de dois canadenses no dia D. Eles desembarcaram na praia de Juno. Os nomes franceses da localidade são Courseulles-sur-Mer, Saint-Aubin-sur-Mer e Bernières-sur-Mer. É muito biquinho para fazer no meio de uma batalha, então os anglo-saxões as renomearam por praticidade.

Logo ao desembarcar, Jim levou um tiro que atravessou seu torso logo acima da cintura. Por sorte, a bala não acertou nada importante. Seu colega Kenny, logo adiante, levou um tiro na perna, também sem maiores conseqüências. Mas a situação não estava nada boa e outros soldados estavam morrendo ao redor de Kenny e Jim.

Um pouco mais à frente, Kenny gritou para que Jim andasse mais depressa. Logo a seguir, Jim levou um tiro que quebrou sua perna. Ambos feridos, os dois procuraram abrigo.

Após esperar um bom tempo e serem atendidos por um médico, mas ainda no calor da batalha, surgiram dois soldados ingleses com cinco galões de chá (misturado meio-a-meio com rum). Sim, os ingleses não esquecem do chá nem quando estão lutando contra os nazistas.

A segunda história é sucinta. A FEB foi à Itália sem um batalhão de sepultamento. Sim, um soldado brasileiro morto teria que enterrar-se a si próprio se quisesse ir com dignidade.

Então, as duas escolas são a britânica, na qual as pessoas são importantes e a tupiniquim, na qual são dispensáveis. Em geral, os gerentes terão muitas desculpas por adotar o estilo tupiniquim (a sinceridade não é bem-vista no mundo corporativo), mas a verdade é que não custa muito propiciar um ambiente agradável para trabalhar: ar condicionado, uma cadeira confortável e café (ou chá) bastam.

Já trabalhei numa empresa com certificação CMM (que é muito cara), mas que não limpava os filtros do ar-condicionado (que são baratos). Certa vez, ao entrar no banheiro, descobri que o fundador da empresa não puxava a descarga. Pode ser que ele tenha muito orgulho de seus feitos, mas é mais provável que ele simplesmente não tenha nenhuma consideração pelos outros.

Eu recomendo trabalhar em empresas da escola britânica, mas se algum espartano realmente preferir a escola tupiniquim, eu sugiro que ao menos leve uma pá.

Janela para a alma

Meu nick é forinti e eu uso Windows. Estou sóbrio há um mês.

Eu comecei na adolescência, por pressão dos mais velhos. Comecei de leve com DOS. Eu nem curtia aqueles monitores de fósforo verde, mas todo mundo achava que os PCs é que eram máquinas para pessoas descoladas. As outras máquinas só serviam para joguinhos de criança.

Eu resisti muito a usar o Windows 3.11. Meu 286 nem mouse tinha e eu podia seguir dando meus tecos com Turbo C e Turbo Pascal. Mas quando chegou o Windows 95, não teve mais jeito.

Fui levando até o 2000. Eu não queria gastar mais dinheiro com o XP. E depois o Vista. E depois o 7. Não tem fim! Eles te pegam com um DOS inocente e quando a gente menos espera, não consegue fazer nada sem a próxima versão. E cada vez fica mais caro manter o hábito.

Eu agora faço tratamento com Ubuntu. Ele reconheceu minha rede wireless antes que eu percebesse e até com minha impressora multifuncional ele conversa.

Os dias bons são quando o meu cunhado vem visitar e pede para usar o micro. Ele não conseguiu largar o vício. Agora ele não consegue infectar minha casa com porcarias que ele encontra nos sítios da vida. Me orgulho de agora poder proteger minha família.

Os dias ruins são quando tem conta para pagar e tenho que sair para procurar um caixa automático. Dá uma vontade danada de instalar um Windowzinho. Tenho que ser forte e pensar nos meus filhos.

É difícil, porque tem muita tentação. Os bancos não me deixam entrar sem Internet Explorer. Um banco usa OS/2 nos caixas automáticos; outro usa Linux. Os dois, mesmo assim, querem me fazer usar o Internet Explorer para poder ver minha grana desde meu micro. No trabalho ainda tenho que usar o XP, mas eu abro um putty para um servidor e isso me ajuda a manter a cabeça no lugar.

Meu querido Trackmania, eu não jogo mais, mas pelo menos eu tenho um futuro agora. Vou levando um dia por vez.

Explorações fractais VII

Potências de números complexos eram um problema até que descobri a fórmula de de Moivre. Acontece que é muito mais fácil calcular potências de números complexos usando coordenadas polares. Então, a solução é converter cada ponto para coordenadas polares, calcular a potência e voltar para as coordenadas originais.

O código que segue mostra minha implementação.

var POWER=2.666;
var NEGATIVE=false;

function mandel(x,y) {
  var c=1;
  var r=0;
  var i=0;
  var MAXITER=512;
  while(r*r+i*i<4 && c<MAXITER) {
    var t=POWER*Math.atan2(i,r);
    var d=Math.pow(Math.sqrt(r*r+i*i),POWER);
    var nr=d*Math.cos(t)+x;
    var ni=d*Math.sin(t)+y;
    if(NEGATIVE) {
      r=nr/(nr*nr+ni*ni);
      i=-ni/(nr*nr+ni*ni);
    } else {
      r=nr;
      i=ni;
    }
    c+=1;
  }
  return c;
}

Deixei a função mandel() pronta para receber potências negativas e positivas: basta alterar o valores de POWER e NEGATIVE.

Experimentei com -3,7 e o resultado se parece com lâminas de patologia.



Depois, tentei 2,666 e descobri que essa potência também gera detalhes com aparência orgânica.

Explorações fractais VI

Depois de levar o Mandelbrot à ducentésima potência, resolvi percorrer o caminho oposto e investigar as potências negativas. Comecei com -2.

Para separar os componentes de um número imaginário da forma 1/(a+bi), multipliquei por (a-bi)/(a-bi) para encontrar (a/(a²+b²))-(bi/(a²+b²)).

Em código, isso significa trocar a função mandel() por:

function mandel(x,y) {
  var c=0;
  var r=0;
  var i=0;
  var MAXITER=1000;
  while(r*r+i*i<4 && c<MAXITER) {
    var nr=r*r-i*i+x;
    var ni=2*r*i+y;
    r=nr/(nr*nr+ni*ni);
    i=-ni/(nr*nr+ni*ni);
    c+=1;
  }
  return c;
}

O resultado foi espetacular, como se pode ver na imagem abaixo (clique sobre ela para vê-la na resolução original).

A recursão nova é, na verdade, z=1/(z²+c), porque z=z^-2+c não produz nada interessante.