Desenvolvendo uma Solução para os Superquadrados

Desenvolvendo uma Solução para os Superquadrados Gabriel Dias Schmoeller, Patrick Thiago Bard 1

Faculdade de Informática (FACIN) Pontifícia Universidade Católica do Rio Grande do Sul (PUCRS) 5 de abril de 2013 {gabriel.schmoeller,patrick.bard}@acad.pucrs.br

Resumo. Este artigo apresenta os algoritmos desenvolvidos para solucionar o primeiro trabalho proposto na disciplina de Algoritmos e Programação III, no primeiro semestre de 2013. O problema envolve uma série de operações básicas, baseadas em três valores (X,Y e Z) que variam de um até dois milhões. O objetivo é encontrar as combinações onde todas operações juntas geram quadrados perfeitos. Desenvolvemos um algoritmo que seu pior caso se caracteriza como O(n2 ), mas no geral, possui um caso médio O(n).

1. Introdução Basicamente, temos como finalidade criar um algoritmo capaz de realizar uma tarefa simples porém demorada, de modo a otimizada-la e torna-la mais rápida, utilizando o conhecimento adquirido durante o curso. Como restrições temos que X, Y e Z, devem obedecer aos seguintes requisitos:

• Os valores devem ser diferentes entre si; • Estar em na faixa entre um e dois milhões; • E todas as operações, sendo elas X + Y, X - Y, Y + Z, Y - Z, X + Z e X - Z, resultem em quadrados perfeitos simultaneamente. É possível dizer que é simples desenvolver um algoritmo que realize esta tarefa, porém a maneira fácil compararia os valores X, Y e Z um à um, o que geraria excesso de comparações, onde o tempo de execução pode superar semanas dependendo do computador. Nossas abordagens ao problema variaram dês de tentativa e erro até meios matemáticos. Dependendo da escolhida, é possível de diminuir insignificantemente, razoavelmente ou consideravelmente o tempo de execução do algoritmo. No decorrer do documento iremos explicar as diferentes tentativas que utilizamos durante a criação e desenvolvimento do algoritmo utilizando a linguagem de programação JAVA, analisando também o porquê de suas falhas e apontando suas principais vantagens e desvantagens.

2. Primeiras abordagens do problema 2.1. Introdução Nesta parte do relatório iremos apresentar nossas primeiras abordagens ao problema demonstrando suas principais fraquezas. 2.2. Base do problema Ao analisar este problema percebe-se que a complexidade dele basicamente é de O(n3 ) sendo n = 2.000.000. Seguindo a ideia de força bruta, o problema possuiria assim, milhões de combinações ou mais dependendo da implementação, mas sem fugir deste patamar. Tantas combinações assim fariam com que um algoritmo desse tipo demorasse muitas horas ou até dias para obter resultados. Como é possível ver, o problema pode ser facilmente resolvível porém o tempo de execução não é algo que uma pessoa estaria disposta de esperar para receber os resultados. Para resolvermos este problema de maneira eficiente tivemos que tentar diversas abordagens diferentes. Algoritmo Força Bruta para X de 1 a 2000000 para Y de 1 a 2000000 { para Z de 1 a 2000000 { a = X + Y; b = X - Y; c = Y + Z; d = Y - Z; e = X + Z; f = X - Z; se(QuadradoPerfeito(a) e QuadradoPerfeito(b) e QuadradoPerfeito(c) e QuadradoPerfeito(d) e QuadradoPerfeito(e) e QuadradoPerfeito(f)){ lista adiciona X, Y e Z } } } Onde a função "QuadradoPerfeito"utilizada a cima, sendo também a mesma função da próxima abordagem, possui um retorno booleano, verificando se o número fornecido possui uma raiz quadrada exata e resultando em TRUE neste caso. se(X menor que 0 ou resto da divisão de X por 10 for (2 ou 3 ou 7 ou 8) retorna FALSO; } A = raiz quadrada de X; //Math.sqrt() se((inteiro) A igual A){retorna VERDADEIRO;} retorna FALSO;

Ela foi implementada para otimizar cálculo da raiz, ao invés de usar simplesmente Math.sqrt(). Basicamente ela primeiro verifica se o número pode ter raiz, já que nenhum número terminado em 2, 3, 7 ou 8 possui raiz exata. Assim, usando o resto da divisão por dez podemos saber o ultimo digito de um número e fazemos esta verificação. Como ela não executa sempre o método de raiz, mas apenas uma simples divisão, ela deveria agilizar o cálculo. Mas esta função possui certas peculiaridades. Percebemos que isto pode variar de acordo com a arquitetura do computador. Em todos computadores com processador da mesma família o método acima implementado, colaborou muito para o desempenho, porém em processadores diferentes seu uso não fazia diferença e em alguns casos, acrescia o tempo de execução. Seguindo esta lógica, como já foi citado, o tempo de execução ficava absurdo. Aqui apresentamos o gráfico que mostra o crescimento do tempo. Lembrando que neste caso o X sempre permanece em um, e o Z varia ate dois milhões, em 5 segundos (5000 ms), Y alcança apenas o valor 50.

Figura 1. Gráfico apresentando a relação do tempo e as iterações da primeira abordagem

2.3. Otimizações Básicas Pensando em como otimizar o modo bruto percebemos que não é necessário comparar todos os valores um a um durante todos os X, Y e Z. Poderíamos organizar o algoritmo de maneira que ele não necessite entrar sempre em um laço de comparação com o Z. Se X + Y ou X - Y não for um quadrado perfeito não precisamos continuar usando esses valores, pois se qualquer um dos critérios de validação estiver incorreto todo o conjunto é inválido. para X de 1 a 2000000 para Y de 1 a X { a = X + Y; se(QuadradoPerfeito(a)){

b = X - Y; se(QuadradoPerfeito(b)){ para Z de 1 a Y { c = Y + Z; se(QuadradoPerfeito(c)){ d = Y - Z; se(QuadradoPerfeito(d)){ e = X + Z; se(QuadradoPerfeito(e)){ f = X - Z; se(QuadradoPerfeito(f)){ lista adiciona X, Y e Z } } } } } } } } Como o código apresentado a cima, que possui pequenas mudanças comparado ao anterior, foi evitado uma serie comparações desnecessárias. Utilizando pontos de fuga para os laços podemos pular diversos valores que concluímos que não teriam validade, ou seja, sem precisar executar todas as comparações. Isto foi suficiente para que esta lógica pudesse ser executada completamente utilizando um tempo médio de duas horas e meia. No gráfico a seguir pode-se perceber que tanto o Y quanto o Z variam o seu máximo, e em pouco mais de 8 segundos X atinge o valor de 20000.

Figura 2. Gráfico apresentando a relação do tempo e as iterações da segunda abordagem

Assim obtivemos os resultados para X, Y e Z como apresentado na Tabela 1. Tabela 1. Valores encontrados

X 434657 733025 993250 1738628

Y 420968 488000 949986 1683872

Z 150568 418304 856350 602272

Apesar de possuirmos certeza que os resultados obtidos estão corretos, já que o algoritmo faz comparações um a um, apenas evitando casos não necessários, é preciso conferir-los. Na Tabela 2 exemplificamos cada operação, provando que cada número obtido satisfaz todos os requisitos necessários. √ X +Y 925 1105 1394 1850

Tabela 2. Verificação dos resultados

√ X −Y 117 495 208 234

√ Y +Z 756 952 1344 1512

√

Y −Z 520 264 306 1040

√

X +Z 765 1073 1360 1530

√ X −Z 533 561 370 1066

3. Solução Final 3.1. Introdução A partir desta fase do relatório abordaremos as principais ideias que nos levaram a solução mais eficiente que conseguimos alcançar (até o momento) para este problema. 3.2. Grupo de quadrados perfeitos Embora o último algoritmo citado seja razoavelmente aceitável comparado ao primeiro, já que com ele obtemos os resultados corretamente , o tempo de execução ainda é elevado de mais para esperar por tal resposta, parte disto envolve o fato de que sua complexidade não deixou de ser O(n3 ) em seu pior caso. A partir desta insatisfação partimos para uma abordagem diferente. Afinal, quanto tempo a maquina demora para encontrar todos os quadrados perfeitos possíveis? Para resolver esta questão, simplesmente fizemos um algoritmo que calcula todos números elevados ao quadrado de 1 à 1999, ou seja, enquanto os resultados forem menor que 4.000.000, pois o maior quadrado perfeito que pode ser encontrado deve se no máximo X + Y em seus maiores valores válidos: 2.000.000 + 1.999.999. Utilizando este algoritmo foi possível encontrar todos quadrados perfeitos possíveis para serem utilizados no problema. 3.3. Centros exatos O primeiro passo para acharmos o melhor caminho foi tentar um novo modo de pensar. Após algumas observações, como tentativas para simplificação das fórmulas, percebemos

algo bem interessante e simples. Se temos que X + Z e X - Y são quadrados perfeitos, então, podemos dizer que X está exatamente no meio de dois quadrados perfeitos quaisquer entre 1 e 4.000.000. E ainda, Y é a distancia exata entre o X e qualquer um dos dois quadrados, sendo os mesmos um número inteiro. Utilizando essa ideia podemos por em prática o uso dos 1999 quadrados encontrados anteriormente. Para saber se é mais eficaz sem ter que elaborar toda a lógica em cima das regras passadas, ignoramos temporariamente a existência da variável Z trabalhando apenas com X e Y. O primeiro passo para o novo algoritmo foi utilizar o código construído anteriormente para encontrar os quadrados perfeitos. Após isso percorremos a lista de quadrados utilizando dois laços, um percorrendo a lista de maneira crescente e o outro decrescente. Além disso, um condicional para que quando o quadrado referente ao laço interno encontrar o quadrado referente ao externo parar a execução do primeiro, pois sabemos que todos os externos anteriores ao atual já foram testados com todos os quadrados do laços interno, assim evitamos comparações desnecessárias e ganhamos desempenho. Desta maneira podemos encontrar todos os centros inteiros exatos entre todos os quadrados perfeitos e denomina-los de "possíveis X". E a diferença do maior quadrado atual com a dele podemos chamar de "possível Y". 3.4. Simplificação de Regras Até o momento encontramos uma lógica aceitavelmente rápida para encontrar todos os possíveis pares de X e Y, porém ainda é preciso utilizarmos comparações com Z. Assim, nosso objetivo foi enquadrar o termo Z no algoritmo sem perder desempenho. Voltando a analisar os cálculos que validam os trios encontramos outro padrão, se analisarmos as contas X + Z, X - Y e X + Z, X - Z podemos chegar a conclusão que baseado em um X qualquer o conjunto de "possíveis y" é também o mesmo conjunto de "possíveis Z", por outro lado analisando as contas Y + Z, Y- Z e X + Z, X - Z podemos dizer que baseado em um Z qualquer o conjunto de "possíveis y" é também o mesmo conjunto de "possíveis X". Simplificando ainda mais as regras podemos chegar a conclusão de que X + Z, X - Z e Y + Z, Y - Z esta no conjunto de "possíveis X + Z, X - Y", levando também em consideração de que o conjunto de X e Y válidos é maior que o conjunto de Z válidos pois X > Y > Z para evitar números negativos ou repetições. Utilizando esta simplificação das regras sabemos que todas as duplas possíveis estão contidas no conjunto que adquirimos anteriormente, porém ainda é necessário apresenta-los na ordem correta. Para esta ultima etapa do problema tivemos a utilização de um dicionário para armazenar nosso conjunto de "possíveis X" e "possíveis Y", de maneira que o X será a chave, e todos os "possíveis Y" para aquele X formarão uma lista de valores. Sabendo que um X válido deve ser a mesma chave para o Y e o Z verificamos todos os X que possuem tamanho de "possiveis Y" maior ou igual a 2, durante esta verificação vimos cada item da lista de "possiveis Y", sabemos também que o Y válido em algum momento deve ser um "possível X"onde seu "possivel Y" seja o Z, ou seja, usamos cada Y na lista desta chave e avaliamos se em algum lugar do dicionário ele também já foi uma chave, caso ele seja, procuramos dentro da lista

de "possiveis Y" dele se existe algum Y que exista nesse conjunto mas também exista no conjunto de "possiveis Y" do, até agora, X válido, se ele existir significa que finalmente encontramos nosso trio válido de X,Y e Z, pois temos que X no centro exato e inteiro de dois quadrados perfeitos, a uma distancia de exatamente um Y de dois quadrados ao mesmo tempo de Z de outros 2 quadrados, e esta mesma validação confere que o Y esta no centro de dois quadrados a uma distancia de um Z de outros 2 quadrados, sabendo que o Y assume o mesmo valor para as duas situações e o mesmo vale para Z. Ao executar este código conseguimos um bom desempenho, onde em todos casos testados os testes duravam menos de um segundo para a lógica completa. No gráfico 3 podemos ver uma dessas execuções

Figura 3. Gráfico apresentando a relação do tempo e as iterações da terceira abordagem

Abaixo apresentamos o pseudo-código do ultimo algoritmo desenvolvido: superQuadrados(limite){ lista raizes = sqrts(limite) //dicionario que contém possiveis x e y //chave = X, valor = lista de Y; XS = Dicionario