Older blog entries for acs (starting at number 47)

Caramba…

Não sei se todos os leitores sabem, porém, o NIST esta fazendo um campeonato para promover um novo algoritmo de hash para incorporar o padrão SHA-3 e já temos algumas submissões de algoritmos de hash, para ser mais exato, 64 submissões ate o presente momento, sendo que algumas das submissões podem ser encontradas aqui.

Bizarro isso, em 2 papers/prototipos postados para o novo padrão SHA-3, 2 já foram quebrados… isso mesmo!! Colisões já foram encontradas… no Sgàil e no WaMM e o mais engraçado é que no caso do Sgàil, foi o próprio autor que conseguiu detectar a colisão no hash.

Seguem os links para quem estiver interessado em mais detalhes:

WaMM Collision e Sgàil Collision e as respectivas propostas do WaMM e do Sgàil.

Para quem curte, vale a pena dar uma olhada nas propostas, até mesmo nas que já foram quebradas e em seus protótipos de implementação.

Ate a próxima…

      

Hail pessoas,

Conforme prometido, estou voltando a postar aqui novamente

Dessa vez o post vem para abrir uma nova seção em meu blogue, que e a seção apple e vem com algo que acredito que assim como tem enorme utilidade para mim, também vai ter para outras pessoas.

Bem, vamos ao que interessa, todos que mexemos constantemente com o computador, adoramos atalhos de teclado, pois eles otimizam e facilitam muito a vida da gente quando aprendemos, correto??? Enfim… estarei aqui postando alguns atalhos que acredito que sejam uteis no MacOS (sistema que eu utilizo no dia-a-dia)

Enfim, vamos as explicações básicas, e que tinha muitas duvidas no comeco de tudo

⌘ = Command, e como se fosse a tecla windows do seu PC, sim… aquela com o desenho da janelinha.
⌥ = Option ou Alt.
⇧ = Shift
^ = Control

E agora segue a lista com os atalhos básicos e que eu frequentemente utilizo no meu dia-a-dia.

⌘ + Q = Sai da aplicação

⌘ + W = Fecha a janela
⌘ + O = Abre um arquivo

⌘ + P = Imprime

⌘ + C = Copia (o CTRL+C do mac)

⌘ + V = Cola (o CTRL+V do mac)

⌘ + X = Recorta

⌘ + S = Salva

⌘ + Z = Desfaz a ultima alteração
⌘ + A = Seleciona todo o texto

⌘ + Y or Space = Quicklook

⌘ + Tab = Alterna entre as janelas

E para completar esse post, criei uma lista simples, porem usual em pdf a partir desse post que estarei disponibilizando aqui no rapidshare

Ate a próxima!!!

      

Olá pessoas,

Após muito tempo ausente, resolvi atualizar esse blogue…

Bem… posso dizer que foi uma ausência significativa, afinal de contas, aconteceram diversas coisas que não me deixaram ter mais tempo para atualizar esse blogue…

Enfim… vamos deixar de “chorumelas” (será que e assim que escreve isso???) e vamos ao que interessa…

Ontem tive um dia bem divertido, ao lado de grandes amigos programadores de C e C++, sim… fui em um evento muito legal na Microsoft, onde só tinham caras muito bons e pessoas de altíssimo nível palestrando e nesse post irei fazer um pequeno resumo do que foi o nosso encontro.

Logo pela manha, tivemos a abertura com o Otavio Pecego da Microsoft que deu uma boa introdução sobre a sua experiência e seu contato inicial com C e C++ e foi ilustrando toda a sua caminhada com os livros que foram importantes na jornada… inclusive, ate peguei algumas sugestões como o livro do John Lakos e o livro do Plauger de STL que eu não conhecia, tenho o C Standard Library que gosto muito…

Em seguida, foi a vez do Rodrigo Strauss, um velho conhecido da comunidade falar sobre as ferramentas utilizadas por ele para facilitar o processo de programação e detecção de problemas, ele comentou desde as ferramentas da sysinternals ate o windbg, tirando os problemas que ocorreram com o microfone (dizem que foi sabotagem dos programadores C#) a palestra foi muito produtiva, principalmente para o pessoal que era mais iniciante.

Depois tivemos uma verdadeira aula de Concepts com o Leandro, enfim, posso dizer que já havia tentado ler o livro do Alexandrescu e quando vi isso, fiquei meio aterrorizado, porem, como o tempo era curto, não deu para o palestrante demonstrar tudo o que sabia sobre o assunto, enfim, percebi que preciso ler e dar uma pesquisada melhor nisso.

Well… hora do almoço… e logo apos o mesmo, tivemos uma palestra bem diferente e interessante com o Felipe Almeida, que nos falou sobre Linguagens Embutidas em C++, confesso que a palestra foi bem interessante, porem, achei o exemplo meio que inusitado para a ferramenta especificada, mais enfim… e bom saber que existe esse tipo de coisa na boost…

Depois foi a vez do “meu irmão” a.k.a. Fabio Galuppo dar uma palestra sobre C++ Nativo no Windows Vista e Server 2008 e mostrar coisas bem legais como NTFS Transacional e Thread Pools… e claro, se tratando do nosso amigo Galuppo, não poderia terminar sem o interop de C++, porem, um assunto que muito me interessa e que ele tratou na palestra e que me fez correr atrás das palestras do Gamefest, afinal, já tinha guardado o link aqui e não tinha visto, foi o lance do PPL (Parallel Pattern Library) que e a nova lib de paralelismo que substitui a antiga TPL. Isso pareceu ser bem interessante…

E para terminar o set de palestras com chave de ouro, foi a vez do nosso amigo e grande colaborador do grupo, Basílio Miranda falar sobre File Mapping no Windows em C++ e demonstrar exemplos interessantes sobre o assunto…

Em seguida, foi a vez dos lighting talks onde o Andre e o Lamarão falaram sobre os seus respectivos projetos em conjunto com a comunidade, sendo que o foco principal foi a otimização da pixman pelo André e a convocação ao publico para trabalharmos em conjunto.

Logo após, houveram os sorteios e dessa vez quem levou a premiação de ajuda a comunidade foi o Pedro Lamarão que ganhou o livro autografado do Sutter

E apos isso, fomos ao bar para poder dialogar sobre o que mais gostamos e um fato curioso foi que pela primeira vez, apareceu uma garota na nossa ida ao bar… sim!!! Para mostrar que nessa comunidade também existem mulheres!!! Porem, o fato mais interessante foi que compareceram varias pessoas novas e as mulheres dessa vez estavam em um numero bem admirável no evento, espero que aumente ainda mais e que as mulheres realmente mostrem a sua forca e parem com esses bla-bla-bla e autopromoções…

Enfim, que venha o próximo encontro… que vai ser o encontro de Embarcados…

See ya in the next event!!!

      

Há alguns dias atrás, novamente em uma discussão em um dos coffeetime que normalmente ocorrem na empresa, que por sinal são muito produtivas, estávamos eu e mais dois amigos programadores discutindo sobre a técnica de tail recursion, que ajuda bastante na otimização de funções recursivas, porem, estava matutando e me lembrei que existe uma outra técnica, também muito utilizada, principalmente em programas que exigem recursividade e implementam Programação Dinâmica, que é a técnica do “Memoization”.

Mais, resumindo, o que seria esse tal de memoization??? como a própria palavra diz, memoize e um termo que deriva do latim memorandum, ou seja, relembrando, exatamente como essa técnica faz, ela armazena em cache as chamadas de função que são repetidas em varias vezes, economizando assim um tempo precioso no acesso dessas informações.

Exemplos clássicos de demonstração dessa técnica são as implementações recursivas de Fibonacci e calculo de fatorial, no nosso caso, iremos utilizar Fibonacci, por estarmos mais familiarizados com essa função nesse humilde blog.

Suponha, que temos uma implementação recursiva de Fibonacci:

int fib( int n )
{
   if ( n <2 )
     return 1;
   else
     return fib( n - 1 ) + fib( n - 2 );
}

Implementaremos o memoization nessa função, utilizando uma implementação com map da seguinte maneira:

std::map<int,int> resultado;
int fib( int n )
{
  if ( n == 0 || n == 1 )
    return 1;
  std::hash_map<int,int>::iterator it = resultado.find( n );
  if ( it != resultado.end() )
    return it.second;
  else
    return resultado[ n ] = fib( n -1 ) + fib( n - 2 );
}

Ou seja, na primeira vez que esse código for executado, por exemplo, para um fib(4), ele vai ter que calcular respectivamente o fib(2) e fib(3), porem, quando eu chamar um fib(5), como os resultados anteriores ja estarão armazenados no map e o valor será retornado sem nenhum calculo adicional, e com isso, teremos um bom ganho no tempo de execução.

Esse pode ser um recurso muito útil quando estamos lidando com algoritmos que lidam com recursividade, onde a programação dinâmica pode ser aplicada, como por exemplo, uma multiplicação de cadeia de matrizes, um alinhamento de sequência ou ate mesmo um algoritmo de otimização para busca em arvores binárias.

Continuando a saga de Fibonacci, eu e meu amigo Marcio fizemos algumas correções e tcharam… devo reconhecer… o script python quando faz chamada de função consegue ser incrivelmente mais rápido que o script perl, também fazendo chamada de função. Porem descobrimos uma coisa muito bizarra e que nos chamou a atenção enquanto realizávamos os testes e por isso foco a minha atenção em relação ao teste feito com python…

Rodando o seguinte código, feito inline em python:

#!/usr/bin/python
for i in range(1000000):
a, b = 0, 1
for j in range(71):
a, b = b, a+b
return b


Profiling do código com chamada de função:


alan@desenv:~$ python -m cProfile fibo.py
1000005 function calls in 86.083 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 86.083 86.083 :1()
1 57.280 57.280 86.083 86.083 fibo.py:7()
1 0.000 0.000 86.083 86.083 {execfile}
1 0.000 0.000 0.000 0.000 {method ‘disable’ of ‘_lsprof.Profiler’ objects}
1000001 28.802 0.000 28.802 0.000 {range}


E agora o mesmo código, só que realizando chamada de função:


#!/usr/bin/python
import sys
#import psyco
def fib(n):
a, b = 0, 1
for j in range(n):
a, b = b, a+b
return b


x = int(sys.argv[1])
y = int(sys.argv[2])
for i in range(x):
fib(y)


Profiling do código com chamada de função:


alan@desenv:~$ python -m cProfile fibo.py
2000005 function calls in 35.174 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 35.174 35.174 :1()
1 4.785 4.785 35.173 35.173 fibo.py:6()
1000000 25.671 0.000 30.327 0.000 fibo.py:6(fib)
1 0.000 0.000 35.174 35.174 {execfile}
1 0.000 0.000 0.000 0.000 {method ‘disable’ of ‘_lsprof.Profiler’ objects}
1000001 4.718 0.000 4.718 0.000 {range}


Ou seja, tirando o tempo de overhead do profile, o programa que realiza a chamada de função, consegue ser incrivelmente mais rápido que o programa inline, mesmo efetuando mais chamadas.

Bem… achei isso muito bizarro, sendo que, teoricamente o esperado era que o inline fosse mais rápido. Bem, se alguém puder me explicar isso eu agradeço bastante, pois a única conclusão que consegui tirar ate aqui, e que o python, mesmo sem usar otimizadores, vide psyco, já tem uma otimização natural de funções, o que torna as chamadas de função extremamente rápidas, porem eu queria entender essa otimização de chamada de funções, pois gostei bastante e fiquei interessado em saber como tal feature funciona.

E agora a minha conclusão em relação ao que eu aprendi com esse teste ate aqui, se você precisa fazer um programa bem rápido para testar qualquer coisa, use perl, resolve na maioria dos casos, agora se você precisa de um teste mais elaborado, com chamada de função, vou começar a pensar em usar o python…

Post in portuguese about my tests with Fibonacci Series using perl and python…

Esses dias, para ser mais exato, na segunda-feira, o meu colega de trabalho marcio a.k.a. tio estava falando sobre a sua escolha para criar um projeto de site que ele esta fazendo e para testar ele implementou o algorítimo de Fibonacci usando C, C++, Ruby e Python e mediu o tempo utilizando o comando time… C e C++ entraram na lista so para ele poder criar um parâmetro. E então ele decidiu escolher pelo python devido ao tempo, porem, ele esqueceu do nosso velho amigo Perl e eu disse a ele que perl executava o mesmo teste mais rápido que python e ele me desafiou, ou seja, estou fazendo esse teste para demonstrar que o nosso velho amigo perl pode ser bom, lembrando que não sou um bom programador python, mais tentei deixar o código o mais próximo possível entre ambas as linguagens para que nenhum boi-corneta (como diria o meu amigo Caloni, gostei da expressão, por isso a utilizei aqui também) venha se espantar aqui…

Bem… para a realização desse teste, utilizei o meu laptop, um macbook com perl 5.8.8 e python 2.5.1 como podem ver abaixo:

[jumpi@Painkiller]~/Sources: perl -v

This is perl, v5.8.8 built for darwin-thread-multi-2level (with 1 registered patch, see perl -V for more detail)

Copyright 1987-2006, Larry Wall

[jumpi@Painkiller]~/Sources: python -V Python 2.5.1

Para fazer os testes, utilizei uma versão iterativa do algorítimo de Fibonacci (afinal de contas, poderia apelar para a recursiva, porem achei melhor utilizar essa para o teste), segue abaixo o código:

Em perl:

#!/usr/bin/perl  use strict; my $n = shift; my ($a,$b)=(1,2);

print "$a\n$b\n";

for(1..$n-2) {

  ($a,$b) = ($b,$a+$b);

  print "$b\n"

}

Em python:

#!/usr/bin/python import sys def fib(n):

 a, b = 0, 1

 for i in range(n):

 	print b

 	a, b = b, a+b n = int(sys.argv[1])

fib(n)

E executei ambos os códigos, fazendo 10000 iterações e medindo o tempo usando o comando time, onde obtive o seguinte resultado:

Em perl:

real	0m0.188s

user	0m0.054s

sys	0m0.047s

Em python:

real	0m10.778s

user	0m8.104s

sys	0m0.231s

Well… ai esta a prova, pelo que posso ver o nosso velho amigo rabugento perl terminou a sua tarefa em um tempo menor que o python, pelo que posso enxergar, 10x mais rápido???

Brincadeiras a parte, através desse teste simples, podemos perceber que o perl, mesmo estando ultrapassado na visão de muitos, ainda executa muito bem o serviço, logico que poderíamos utilizar n técnicas em ambas as linguagens. Porem, como eu disse no principio, tentei simplificar ao máximo para não criar vantagens para nenhum dos lados.

Hey tio, esse post vai em sua homenagem… se quiser, te ajudo a utilizar perl com catalyst para criar o site…

Brincadeirinha… ;D

Upon requesting made and continuing my posts about perl practicality, show here a very elaborated code, extract from classic book that I have reading again, Pike & Kerninghan Practice of Programming.

Yes, this book have a very interesting example of Markov Chains in perl.

For those that dont knowing about Markov Chains, this is a particular case in stochastic process, where previous states are irrelevant for prediction of following states, since that actual state is knowing. This technique is very used for generate random text, as in the book example, but, the author uses only cases that envolve two-word prefixes, for test effects.

The code used in the example, written in perl language:

$MAXGEN = 10000;
$NONWORD = “\n”;
$wl = $w2 = $NONWORD;
while (<>) {
foreach (split) {
push(@{$statetab{$w1}{$w2}}, $_);
($w1, $w2) = ($w2, $_);
}
}
push(@($statetab{$w1}{$w2}}, $NONWORD);
$w1 = $w2 = $NONWORD;
for ($i = 0; $i < $MAXGEN; $i++) {
$suf = $statetab{$w1}{$w2};
$r = int(rand @$suf);
exit if(($t = $suf->[$r]) eq $NONWORD);
print “$t\n”;
($w1, $w2) = ($w2, $t);
}

And more impressive is what the result is make of simple and rapid form, very rapid, in the final of chapter has a performance table where perl losing only for C implementation, other implementations are written in Java, C++/STL/Deque, C++/STL/List and AWK, being that have 150 lines of code in C versus only 18 in perl.

Well, I dont make apologies to perl, because I love C too, but, as the author says and define in the final of paragraph, scripting languages (perl, in this case) are a good choice for experimental programming and making prototypes, and I conclude, for rapid tasks and tests, perl is again language of my choice.

Um dos exemplos mais didáticos que eu ja vi sobre tratamento de exceções foi dado hoje aqui na empresa onde trabalho, estávamos na cozinha, no coffee time, quando começamos a discutir sobre tratamento de exceções e eis que o meu colega de trabalho, Marcio Andrey a.k.a. tio nos faz a demonstração de como ele explicou tratamento de exceções a outro colega aqui da empresa que estava com duvidas no entendimento do tratamento de exceções e precisava de ajuda para fazer a sua prova.

Segue abaixo o exemplo de código (com permissão do autor, e algumas correções para nao divulgar nomes, of course…):

Pessoa individuo = new Pessoa(”individuo”);

Pessoa gostosa = new Pessoa(”uma gbr gostosa”);

Cerveja cerveja = new Cerveja(”Skol”); //variável antes do try que precisei

individuo.tomaBreja(cerveja);

try {

individuo.pegaNaCintura(gostosa);

individuo.pegaNoPeitinho(gostosa);

individuo.chupaPeitinho(gostosa);

Camisinha johnson = new Camisinha(”Lubrificada”); // precisei de uma variável local aqui.

individuo.poeCamisinha(johnson); // usei a variável local aqui.

individuo.comeASafada(gostosa);

}
catch(TapaNaCaraException e) {
System.out.println(”a gbr tentou te dar um tapa na cara e te deu uma escroteada”);
}
catch(TeEmpurrouException e) {
System.out.println(”a gbr te empurrou e te deu uma escroteada”);
}

catch(TeEmpurrouException e) {
System.out.println(”a gbr te deu uma escroteada”);
}
finally {
individuo.vaiEmbora();
}

Quer exemplo mais didático que esse??? Depois dessa o individuo nunca mais vai se esquecer como fazer uso correto do try/catch….

Meus sinceros agradecimentos ao tio por contribuir com esse post tao instrutivo e ao mesmo tempo engraçado!!!

Sorry for Advogato’s people by wrote this in portuguese, I need wrote this and any questions about I wrote, send me a message and I explain

About the bug that affected Excel 2007, I think that is very hard to work with floating point calculations and approximation is very complex and find a problem in logic of this is a true nightmare!!!!

The summary of problem: Excel 2007 store six floating point numbers using binary representation between 65534.99999999995 and 65535, and dont store six between 65535.99999999995 and 65536 and this numbers are the cause of this problem.

I work with arbitrary precision in my scientific intiation and using libraries for care of this part for me, because of difficulties that involve the manipulation of calculate numbers that need arbitrary precision. IMHO, working with type of development demands very attention and very pacience.

The two links have a good explanation of this problem… Its a good lecture!!!

The Excel Bug Explanation by Good Math, Bad Math Blog
The Excel Bug Explanation for Mathematica Developers Blog

See ya people and have a good fun!!!

In play: Emerson, Lake and Palmer - Works (Black) Vol. 1 - 07: The Enemy God

Really, Code::Blocks Rocks!!!

Well… after a long time I post here again, because of this IDE… yeah… a many time that I try to test it and after tests of my friend Marcio that use and talk about the tool I decided test too. I’m very surprise with this IDE, the installation is very easy and work with this IDE is very easy too… I install it in my VM with WinXP and I testing the OpenGL app and it works very fine… The OpenGL app works fine in my VM too, in considerable time… I decided now use the Code::Blocks for developing my personal project at this time!!! Its convinced me!!!

Today, after reading some pages of the Programming Challenges Book I’m trying applying some memoization and dynamic programming techniques for solve some problems in SPOJs and UVA’s online-judge of life. Its a very utility tool for solving many problems. But I need more training for good application of this. I like this…

In play: Bruce Dickinson - The Very Best Of (CD 1) - 02: Tattooed Millionarie