quarta-feira, 18 de junho de 2008

Um cientista em minha vida


Eu li lá no blog do Kentaro que o meme da semana era "Um Cientista em minha vida", onde deveríamos falar sobre algum cientista que fez a diferença pra você. Como eu adoro constrained writing, resolvi participar (na verdade, eu adoro constrained anything, por isso que vivo criando programas em uma linha, programas que rodam em computadores de 8 bits, e assim por diante).

Eu já falo de cientistas aqui todo o tempo. Olhando no histórico, eu já falei do Knuth, do Erdös, do prof. Routo, do prof. Henrique, e de vários outros. Em comum, todos eles foram cientistas que eu conheci depois de adulto. Achei apropriado então que eu falasse de um cientista que fez a diferença quando eu era criança, e pra isso vamos ter que rebobinar até a década de 80.

Se você perguntar pra alguém sobre revistas de computador na década de 80, invariavelmente irá ouvir sobre a Micro Sistemas ("a primeira revista brasileira sobre microcomputadores"). A Micro Sistemas era muito legal, mas o que eu gostava mesmo era de outra revista, menos conhecida, chamada Microhobby.

A diferença da Micro Sistemas pra Microhobby era mais ou menos a diferença de Informática pra Computação. Na primeira, nós ficávamos encantados com as notícias da maravilhosa terra além da reserva de mercado (onde aprendíamos que a Apple planejava lançar um novo computador chamado McIntosh, que vinha com um periférico estranho e esquisito chamado mouse), enquanto que na segunda aprendíamos a calcular geodésicas e a usar o método de Bolzano para achar raízes de uma equação.

Mas o diferencial mesmo da Microhobby eram as colunas escritas pelo Renato da Silva Oliveira. Uma googlada rápida revela que o Renato é formado em Física, trabalhou nos planetários de São Paulo, Campinas, Vitória e Tatuí, e atualmente trabalha em uma empresa que vende planetários infláveis (how cool is that?!). Mas é claro que eu não sabia disso na época, o que eu sabia era que ele contava historinhas!

Foi lendo as historinhas do Renato que eu descobri que era possível escrever sobre ciência e computação, com clareza e bom humor. Pena que isso ainda não é muito difundido, a julgar pela quantidade de crianças que ainda acham que ciência é uma coisa chata :(

As historinhas que ele escrevia sempre tinham o mesmo formato: um certo sr. Nabor Rosenthal, em suas viagens pelo mundo, deparava-se com alguma situação que sugeria uma análise matemática (os tópicos eram os mais variados e iam de teoria dos grafos até contatos com extraterrestres). Depois de ponderar sobre o problema sem conseguir resolvê-lo, o Nabor tomava uma dose do raro Suco de Ramanujan, que o colocava num transe que ampliava suas capacidades analíticas, e conseguia solucionar o problema.

Mas a coluna sempre acabava antes que o Nabor mostrasse qual a solução! Ao invés disso, o leitor tinha um mês pra conseguir resolver o problema, e só no mês seguinte a solução era apresentada. Na década de 80 ainda não tinha spoj, então as colunas do Renato eram o que bombava pra quem gostava de puzzles computacionais.

Um dos puzzles apresentados foi o segundo puzzle mais difícil da minha vida, eu levei mais de dez anos pra conseguir resolver. Em uma das Microhobby, o Nabor entrou em transe após tomar o Suco de Ramanujan, e durante o transe ele sonhou "com um método para calcular o número pi, usando apenas o gerador de números aleatórios de seu micro" (essa era a época onde o micro mais avançado era o TK-82C, com 2kb de RAM).

Na época eu pensei muito e não consegui solucionar, achando que ia precisar de alguma matemática que eu ainda não tinha aprendido. Eu nunca consegui achar a revista seguinte com a solução, tive que passar pelo primário, pelo colégio técnico, e só no meio da faculdade é que caiu a ficha (e eu percebi que poderia ter solucionado ainda no primário, se tivesse insistido o suficiente :)

O truque é o seguinte: você vai fazer N experimentos, cada um consistindo no sorteio de dois números aleatórios escolhidos uniformemente entre 0 e 1. Se soma dos quadrados dos números for menor ou igual a 1, incremente um contador (digamos, M). Ao final dos experimentos, pi=4*M/N. O script abaixo implementa esse algoritmo:

Script em python para calcular pi usando números aleatórios

O funcionamento é bem simples e baseia-se na figura ao lado. Você começa inscrevendo um quarto de círculo num quadrado de lado 1. Os dois números que você sorteia a cada iteração podem ser interpretados como um ponto dentro do quadrado, e o teste feito é equivalente a testar se o ponto está dentro do círculo ou não. Como a distribuição dos pontos é uniforme, espera-se que a razão M/N seja igual à razão entre as áreas da figura. A área do quadrado é 1, a área do círculo é pi*r2. Como o raio é unitário, então a área do quarto de círculo é pi/4. Isolando pi, chega-se em pi=4*M/N, QED.

A pergunta que deve ser feita ao encontrar qualquer algoritmo novo é: qual é sua complexidade? Infelizmente, esse método aleatório é bem ruim. No fundo, o que estamos fazendo é aproximar pi por uma fração, cujo denominador é N. Então a precisão máxima que podemos obter é 1/N, e se você quer calcular n dígitos de pi, esse método converge, no melhor caso, em O(10n), e na prática em bem menos que isso, porque os seus geradores de números aleatórios não são perfeitamente uniformes.

Eu nunca soube qual o método que o Nabor usou pra calcular o pi. Como ele tinha o Suco de Ramanujan e eu não, espero que tenha sido um método melhor que o meu :)

Update!

Em março de 2011 comemoram-se os 30 anos do ZX81, então decidi revisar esse post com o conteúdo original da época. Esse aqui era o enunciado original da Microhobby, clique para ampliar:


Eu implementei a solução usando o BASIC de um TK85 (real, não é emulador):


Se não der para ler na foto, o programa em BASIC é o abaixo:
1 FAST
4 LET I=0
5 LET M=5000
6 LET T=0
10 FOR N=0 TO M
20 LET X=RND
30 LET Y=RND
40 LET T=T+1
50 IF X*X+Y*Y<1 THEN LET I=I+1
60 NEXT N
70 PRINT 4*I/T
O resultado, após 5000 iterações, foi 3.1137773. Conseguimos duas casas de precisão, após dez minutos de processamento de uma tecnologia de 30 anos atrás :)


Outro update!

O Leonardo Roman da Rosa achou a solução original da revista, saiu na Microhobby #25. No final, a solução original é exatamente a mesma que descobri! Até as constantes foram coincidemente iguais :)


21 comentários:

  1. Eu (minha mãe, na verdade) tinha um TK-90X e lembro de ter visto umas revistas dessas por aqui quando era jovem.
    Talvez, se elas tiverem resistido a décadas de umidade e calor natalenses eu tenha essa edição.
    O computador eu ainda tenho (e se todos os teclados fossem emborrachados como aquele, talvez minha tendinite não estivesse tão avançada)!

    ResponderExcluir
  2. No site do datacassete tem um monte de Microhobbys scaneadas, mas justo o número do pi não tem :(

    ResponderExcluir
  3. Nunca ouvi falar desta revista. Ela era famosa entre os computeiros da época?

    ResponderExcluir
  4. Ela era razoavelmente conhecida na época dos TKs (por volta de 84). Mas até então computação pessoal era coisa pra engenheiro e filho de engenheiro; a coisa só popularizou mesmo depois do MSX, e nessa época (por volta de 87) a Microhobby já tinha acabado.

    ResponderExcluir
  5. Eu tenho aqui em casa algumas Microsistemas e a coleção Input (também tenho essa coleção em PDF).

    É *impressionante* como era alta a qualidade dessas revistas de informática na era da 'microinformática'.

    Em tempo eu comecei com MSX mas tive acesso à computadores da linha Sinclair e Apple na época.

    Uma outra informação: Um dos sócios do Renato Oliveira na AsterDomus é o Pierluigi Piazzi, autor de alguns livros famosos de MSX que foram publicados pela editora Aleph.

    ResponderExcluir
  6. >na verdade, eu adoro constrained anything

    Eu *tento* não ler essa frase com maldade, mas é difícil...

    ResponderExcluir
  7. Oi, tudo bem?

    Esse não é o método Monte Carlo? Muito bacana! Isso mostra como, com pouco "poder" computacional, soluções simples aparecem. E realmente a eficácia do método é questionável nesse caso. Por isso ele é usado para obter integrais de funções, entre outras aplicações. Abraços

    ResponderExcluir
  8. Ah sim, o mesmo algoritmo pode ter duas interpretações diferentes, a minha interpretação original foi geométrica, mas você também pode interpretar como sendo um estimador monte carlo da integral definida de 0 a 1 da função sqrt(1-x*x). Analiticamente, isso vai dar pi/4 também.

    ResponderExcluir
  9. Sempre que explico método de Monte Carlo eu uso uma interpretação geométrica, feito a sua pro Pi: calcular a área de uma ilha (você sorteia pontos no mapa e conta quantos caíram na ilha e quantos caíram na água).

    ResponderExcluir
  10. Aqui Pierluigi Piazzi (do MSX e editor da Microhobby) amicíssimo do Renato e íntimo da Dinorah (amiga do Nabor). Existe outro método, usando a função de Gauss (o famoso sino, a função que é a transformada de Fourier de si mesma) mas que falha vergonhosamente com micros normais porque os números gerados não são verdadeiramente aleatórios.

    ResponderExcluir
  11. Mês passado eu fui no Exploratorium em San Francisco, e lá tinha um terceiro experimento pra achar o Pi, dessa vez atirando moedas em um grid circular e vendo qual a taxa de moedas que intercepta o grid. Vou tentar reproduzir e postar o resultado :)

    ResponderExcluir
  12. O experimento descrito acima lembra o das agulhas de Buffon...

    ResponderExcluir
  13. Eu tirei uma foto do experimento. O picasa é meio temperamental com links diretos pra fotos, pode ser que ele te leve pra primeira foto do álbum ao invés da foto correta.

    ResponderExcluir
  14. Via a foto do experimento e me parece mesmo uma reprodução mais segura d´"as agulhas de Buffon", tanto que as "moedas" têm uma diâmetro indicado. O link "http://pt.wikipedia.org/wiki/Agulha_de_Buffon" contém informações adicionais.

    ResponderExcluir
  15. O melhor é ver que ainda hoje eu aprendo coisas com vocês :)

    ResponderExcluir
  16. Desculpe comentar num post tão velho, mas eu não posso deixar de observar: sim, você tem razão que você precisa de algo tipo 10^n para que a média tenha n casas decimais de precisão. No entanto, o Teorema Central do Limite diz que a variância cresce com 1/sqrt(n) -- ou seja, se você fizer 10^6 experimentos, a variância é algo da ordem de 10^-3.

    Ou seja, mesmo com um milhão de lançamentos, você pode esperar um erro de um milésimo na sua conta. Para calcular π com precisão de n casas decimais, você precisa não de 10^n, mas sim de 10^2n lançamentos!

    ResponderExcluir
  17. Ricbit, tenho toda a coleção da MicroHobby e resolvi procurar a solução do quebra-cabeça, pois fiquei curioso para ver a versão dada pela revista. O quebra-cabeça foi publicado na edição nº 23 e na edição nº 24 veio a solução de um quebra-cabeça anterior (o "1, 2, 3, muitos" ). Procurei entre as ed. nº 25 a 38 e não encontrei. Ao que tudo indica, o quebra-cabeça do PI foi o último publicado e a solução nunca foi publicada, infelizmente.
    Kelly

    ResponderExcluir
  18. Ah, uma pena :(

    Mas agora fiquei com vontade de resolver os outros.

    ResponderExcluir
  19. Raridade absoluta! Eu também curtia muito a revista Microhobbys, principalmente as colunas do Renato Oliveira, mas é raro encontrar outras pessoas que a conheceram na época.

    Recentemente, na inauguração do Lab de Garagem, em São Paulo, tive o prazer de conhecer 3 ex-leitores da revista assim como um autor de livros da editora Aleph.
    Foi algo totalmente inusitado, eu disse que gostava desta revista, outro lembrou que havia o colunista que escrevia livros para a Aleph e os três falaram o nome do Renato num coro sincronizado.

    Foi surreal.

    ResponderExcluir
  20. É legal que no verso da página do quebra-cabeças está escrito "Nunca compre uma coisa que você não vai usar", rs. Isso não se aplica a nada aqui, mas resolvi comentar pelo desafio de ler através do que a foto permite ver.

    ResponderExcluir