CCM0128 - Computação II (2022i)

Seja \(N\) um inteiro. Queremos saber quantas soluções $(a,b,c,d)$ a equação

\(
a^2+2b^2=3c^3+4d^4
\)

admite, onde exigimos que $a$, $b$, $c$ e $d$ sejam inteiros positivos menores ou iguais a $N$. Por exemplo, para $N = 16$, há três soluções:

2 16 4 3
4 6 2 2
7 3 1 2

Você pode usar o programa Plain.java abaixo para encontrar as soluções para um dado $N$. Entretanto, você verá que Plain.java é lento para valores um pouco maiores de $N$, pois ele tem complexidade da ordem de $N^4$.

Objetivo.  Neste exercício, você deve escrever um programa chamado Solve.java que encontra as soluções da equação acima de forma bem mais eficiente que Plain.java.

Exemplo.  O argumento de linha de comando nas execuções abaixo especificam o valor de $N$:

$ java-algs4 Plain 400 > /dev/null
Elapsed time: 39.759
$ java-algs4 Solve 400 > /dev/null
Elapsed time: 0.088
$

Nas execuções acima, enviamos a saída para /dev/null pois estávamos apenas interessados nos tempos de execução e não nas saídas.

Seu programa.  Seu programa Solve.java deve receber $N$ na linha de comando. Ele deve imprimir o tempo que ele leva para listar todas as soluções encontradas usando o mecanismo usado em Plain.java. Seu programa deve ter o formato de saída que Plain.java tem. Não há nenhuma exigência sobre a ordem que seu programa lista as soluções encontradas.

Testes.  Para testar a saída de seu programa, você pode usar o programa Solution.java dado abaixo, que ordena soluções de nossa equação de acordo com uma certa ordem específica (veja o método compareTo() em Solution.java).

Exemplo.  Primeiras 5 soluções encontradas por Plain.java e por (meu) Solve.java para $N=400$:

$ java-algs4 Plain 400 | head -n5
1 26 7 3
1 42 7 5
1 221 17 12
2 16 4 3
2 18 6 1
Elapsed time: 39.839
$ java-algs4 Solve 400 | head -n5
7 3 1 2
4 6 2 2
19 3 5 1
2 16 4 3
22 4 4 3
Elapsed time: 0.096
$

Para comparar as saídas de Plain.java e Solve.java, podemos usar Solution.java e fazer algo como

$ java-algs4 Plain 400 | java-algs4 Solution | head -n5
Elapsed time: 39.87
7 3 1 2
4 6 2 2
19 3 5 1
2 16 4 3
22 4 4 3
$ java-algs4 Solve 400 | java-algs4 Solution | head -n5
Elapsed time: 0.086
7 3 1 2
4 6 2 2
19 3 5 1
2 16 4 3
22 4 4 3
$

Naturalmente, queremos verificar a saída toda (e não apenas as primeiras 5 linhas). Podemos fazer o seguinte:

$ java-algs4 Plain 400 | java-algs4 Solution | md5
Elapsed time: 39.812
79acb63a479402a36370590526d053cc
$ java-algs4 Solve 400 | java-algs4 Solution | md5
Elapsed time: 0.091
79acb63a479402a36370590526d053cc
$

Como obtivemos o mesmo resultado (79acb...), podemos ficar bastante seguros de que Plain.java e Solve.java geraram a mesma saída. Leia sobre MD5, por exemplo, nessa página. No caso do GNU/Linux, o utilitário para calcular o MD5 chama-se md5sum.

Tempo de execução.  Os arquivos experiments.txt e experimentsGNU.txt abaixo contêm mais execuções de Plain.java e Solve.java. Os tempos de execução de seu Solve.java não devem ser substancialmente diferentes dos tempos que aparecem nesses arquivos. Note que, ao repetir os experimentos nesses arquivos, você deve obter os mesmos MD5.

Sugestão.  Veja o Creative Problem 2.4.25 (Computational number theory) e Web Exercise 2.4.3 (Taxicab numbers) de S&W.