domingo, 10 de julho de 2016

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).

Nenhum comentário:

Postar um comentário