Ótimo livro: CODE do Charles Petzold

No início de janeiro eu estava pra sair de férias, e perguntei para os meus colegas que livros eles sugeriam para ler. Queria alguma coisa técnica porém leve, que fosse menos bit e mais história. A sugestão do mestre Rafael Aquini não poderia ter sido melhor: CODE, do Charles Petzold. Ao terminar de ler o livro eu cheguei à conclusão que lê-lo equivale a ter nascido na década de 70 e estudado computadores de 8 bits. Sério, é muito bom mesmo!

Vale muito a pena mesmo para quem já domina o lado técnico, pois a contextualização histórica que ele apresenta, na medida certa, enriquece a compreensão de qualquer um a cerca dos bits e seus significados. Não tem como ler este livro e não enxergar os bits. Eles estão lá, nus e crus, esperando que o leitor os apreenda, e de repente toda a computação digital faz sentido.

Você sabia que as raízes da computação binária remontam ao século 19? Os bits são os mesmos, só mudou o substrato. A grande sacada veio no início do século 20, com o Claude Shannon, usando tecnologia de telégrafos do século 19. Eu já tinha lido alguma coisa dele quando estudei algoritmos de compressão, mas agora compreendo o papel muito mais fundamental que ele teve na Grande Sacada de unir no sistema de numeração binário a aritmética, a lógica e a sua expressão automatizada por meio de circuitos elétricos (na época eletromecânicos). A partir daí a tecnologia só se miniaturizou e se tornou mais rápida, mas o princípio é o mesmo.

Claude Shannon agora figura entre Ken Thompson, Dennis Ritchie, Donald Knuth e muitos outros no meu panteão pessoal da Computação. :-)

Ótimo livro: Alex no País dos Números

Entre reuniões e horários de almoço, consegui hoje terminar de ler um ótimo livro para quem gosta, e também para quem ainda não gosta, de Matemática: Alex no País dos Números. Alex Bellos apresenta os mais variados e interessantes aspectos da evolução da Matemática ao longo dos séculos, sem tornar a narrativa chata nem pesada demais.

Eu já tinha lido (na verdade começado a ler e desistido) outros livros mais enciclopédicos como o História Universal dos Algarismos, mas depois de 50 páginas sobre as variações menos conhecidas dos algarismos cuneiformes realmente começa a ficar difícil manter a motivação. Já o livro do Alex Bellos é mais envolvente, e em vários capítulos dá vontade de sair correndo pro Python pra implementar alguns algoritmos e comprovar teorias divertidas (como a de que todo número par maior que 2 é a soma de dois números primos, que eu deixei o Python calculando algumas horas durante a noite).

Quem não gosta de Matemática deveria ler esse livro. Vale a pena desfazer a má impressão causada nas velhas e empoeiradas salas de aula do passado. :)

Números divertidos: 0xAAAAAAAA e seu irmão 0x55555555

Ontem estava começando a ler um livro, chamado Hacker's Delight (hacker no sentido original, fuçador e escovador de bits), meio desconfiado porque ele me foi indicado por um colega que é engenheiro de compiladores (bichos raros e bizarros). Ficava pensando se eu realmente iria gostar de ler sobre centenas de operações curiosas e micro-algoritmos otimizados em um assembly RISC hipotético e aritmética modular (claro que sim).

Eis que no prefácio o livro já me cativou, falando sobre as correções do Guy Steele e sobre os fatores do número hexadecimal 0xAAAAAAAA, que são 2, 5, 17, 257 e 65537. Quem fuça em bits desde pequeno já deve ter ficado intrigado pelo 65537 e pelo 257, e talvez também pelos outros (mas o 2 meio que sobra, veremos o porquê). Observando um pouco os números, e brincando com os comandos factor e bc, eis que percebi que realmente os números 0xAA... e 0x55... (em 8, 16 e 32 bits) são números muito bonitos e divertidos. :)

Comecemos pelo 0xAAAAAAAA mencionado no livro. Sua representação em binário é 10101010101010101010101010101010, e em octal é 25252525252 (que inclusive é um palíndromo). Em decimal dá um 2863311530 chato. Mas agora olhemos os seus fatores 2, 5, 17, 257 e 65537:

    2 = 4 ^ 0 + 1

    5 = 4 ^ 1 + 1

   17 = 4 ^ 2 + 1

  257 = 4 ^ 4 + 1

65537 = 4 ^ 8 + 1

Se não fosse pelo 2 (chato), dava ainda pra fazer outra série mais bonita:

    5 = 2 ^ 2 ^ 1 + 1

   17 = 2 ^ 2 ^ 2 + 1

  257 = 2 ^ 2 ^ 3 + 1

65537 = 2 ^ 2 ^ 4 + 1

Em binário, o 2 fica chato, mas os demais ficam bonitos:

    2 = 10

    5 = 101

   17 = 10001

  257 = 100000001

65537 = 10000000000000001

O legal é que, como este número divertido 0xAAAAAAAA tem 2 (chato) como fator, fica óbvio que teremos outro número bonito e divertido retirando o 2 dos fatores (dividindo por 2, ou deslocando um bit pra direita): 0x55555555. Como tiramos o 2 da história, os fatores ficam 5, 17, 257 e 65537, que são todos números bonitos e dão séries contínuas de exponenciação como visto acima. :)

0x55555555 em binário é 01010101010101010101010101010101 e em octal fica um pouco menos bonito que o seu irmão: 12525252525. Em decimal fica um desinteressante 1431655765. E pra fechar, olhem que massa: as versões menores destes números de 32bits também continuam interessantes, e a série de fatores deles fica interessantíssima!

    fatores de 0x55 = 5 17

  fatores de 0x5555 = 5 17 257

fatores de 0x555555 = 5 17 257 65537

O mesmo acontece com 0xAA, 0xAAAA e 0xAAAAAA, somente adicionando o 2 inicial. :) Pena que indo pra 64bits aí já entram outros fatores menos divertidos.

Update: Acabaram as reuniões do dia. Mais diversão com o bc pra ver que a série continua bem legal:

$ bc
bc 1.06.95
...

2 ^ 2 ^ 5 + 1
4294967297
 

2 ^ 2 ^ 6 + 1
18446744073709551617

obase=16
 

5 * 17 * 257 * (2 ^ 2 ^ 5 + 1)
555500005555
 

2 * 5 * 17 * 257 * (2 ^ 2 ^ 5 + 1)
AAAA0000AAAA
 

5 * 17 * 257 * (2 ^ 2 ^ 5 + 1) * (2 ^ 2 ^ 6 + 1)
5555000055550000555500005555
 

2 * 5 * 17 * 257 * (2 ^ 2 ^ 5 + 1) * (2 ^ 2 ^ 6 + 1)
AAAA0000AAAA0000AAAA0000AAAA
... e assim por diante. :)