Resgatei mais um programinha dos backups: esse calcula qual é maneira de calcular sqrt(7) usando régua e compasso minimizando o número de traçados. Quer dizer, calcularia, se funcionasse!

A história dele é que certa vez o Joao Kogler me desafiou a calcular sqrt(7) com compasso. É fácil, eu disse, você começa com um triângulo retângulo de catetos iguais a 1, aí vai traçando perpendiculares pelos vértices. Depois de algumas iterações, sqrt(7) aparece como a última hipotenusa da espiral.

Mas esse método é ruim, ele me disse! Para traçar uma perpendicular você precisa usar o compasso duas vezes por iteração, tem um jeito que você usa uma vez só. Começa com duas paralelas espaçadas por uma unidade, aí traça o compasso para cima e para baixo alternadamente. Isso também chega em sqrt(7) no final de uma maneira mais simples!

Imediatamente o que me veio na cabeça foi "tá, mas isso é ótimo?". Na teoria é fácil checar isso, é só construir um forward chaining com as regras de construção do Euclides e deixar rodando, eventualmente ele bate na construção mínima de sqrt(7).

Mas na prática não deu certo! Eu subestimei a complexidade do problema. Para o forward chaining funcionar, você precisa checar a cada número se ele está presente na lista de números já encontrados. E comparar dois números construtíveis sem usar os reais é complicado!

Por exemplo, quem é maior, sqrt(7)+sqrt(2) ou sqrt(3)+sqrt(5)? Você precisa de vários passos para descobrir:

sqrt(7) + sqrt(3) ? sqrt(3) + sqrt(5)
7 + 2*sqrt(21) + 3 ? 3 + 2*sqrt(15) + 5
2 + 2*sqrt(21) ? sqrt(15)
4 + 8*sqrt(21) + 4*21 ? 15
8*sqrt(21) ? 15 - 4 - 2*21

Pronto, o lado de lá é negativo então sqrt(7)+sqrt(2) é maior que sqrt(3)+sqrt(5). Meu programa tinha que fazer isso para cada par de números gerados, então ele estourava exponencialmente antes de chegar no sqrt(7) !

Hoje em dia acho que eu usaria o valor real da expressão como um hash para deixar mais rápido (e mesmo assim daria problema rapidinho com overflow do double, mas provavelmente chega no sqrt(7) antes do overflow).

https://github.com/ricbit/Oldies/tree/master/2011-01-geom