# Solving Diophantine equations

I have a project for solving Diophantine equations, where a solution exists if

$$A^5 + B^5 + C^5 + D^5 + E^5 = F^5$$

where $0 < A <= B <= C <= D <=E <= F <= N$

The program will take an input N and first generate all values from 1 to $N^5$. Then it will get all possible sum values of $A^5 + B^5 + C^5$ and store the sum in an doubly linked list. Then it gets the possible sum values of $F^5 - (D^5 + E^5)$ and store that into a separate list. When creating the list, it also does a check to make sure the condition also holds (so like $A^5 <= B^5$ etc).

It will then do quicksort on both lists and then compare both values. During comparison, there is also a check in place to make sure that the value for $C <= D$.

So far my code is running, however it isn't running at optimal performance. It takes a considerable amount of time to find a solution for large $N$ values. The code should be running at a time complexity of $O(N^3LogN)$. Can anyone please give me some hints or suggestions as to how I can improve my current code?

import java.util.Scanner;
import java.lang.Math;

public class EquationSolver {
private long[] values;
private long numVal;
private long sum1, sum2;
private long a, b, c, d, e, f;
private DLList list1, list2;

public EquationSolver(String command) {
numVal = Integer.parseInt(command);
values = new long[(int) numVal];

Node refNode1 = new Node(0, 0, 0, 0, null, null);
Node refNode2 = new Node(0, 0, 0, 0, null, null);

for (int i = 0; i < numVal; i++) {
int x = (int) Math.pow(i+1, 5);
values[i] = x;
}

list1 = new DLList();
for (int i = 1; i < numVal; i++) {
c = values[i];

for (int j = 1; j < numVal; j++) {
b = values[j];
if (b > c) {
break;
}
else {
for (int k = 1; k < numVal; k++) {
a = values[k];
if (a > b || a > c) {
break;
}
else {
sum1 = a + b + c;
Node tempNode1 = new Node(sum1, a, b, c, null, null);
if (list1.isEmpty()) {
refNode1 = tempNode1;
}
else {
refNode1 = tempNode1;
}
}
}
}
}
}

list2 = new DLList();
for (int i = 1; i < numVal; i++) {
f = values[i];

for (int j = 1; j < numVal; j++) {
e = values[j];
if (e > f) {
break;
}
else {
for (int k = 1; k < numVal; k++) {
d = values[k];
if (d > e || d > f) {
break;
}
else {
sum2 = f - (d + e);
if (sum2 < 0) {
break;
}
else {
Node tempNode2 = new Node(sum2, d, e, f, null, null);
if (list2.isEmpty()) {
refNode2 = tempNode2;
}
else {
refNode2 = tempNode2;
}
}
}
}
}
}
}

list1 = quickSort(list1);
list2 = quickSort(list2);

int z = 0;
long temp1 = 0;
long temp2 = 0;
long checkA = 0;
long checkB = 0;
long checkC = 0;
long checkD = 0;
long checkE = 0;
long checkF = 0;
Node tempNode1 = new Node(0, 0, 0, 0, null, null);
Node tempNode2 = new Node(0, 0, 0, 0, null, null);

for (int x = 0; x < list1.size(); x++) {
if (x == 0) {
tempNode1 = list1.getFirst();
temp1 = tempNode1.getSum();
checkA = tempNode1.getValue1();
checkB = tempNode1.getValue2();
checkC = tempNode1.getValue3();
}
else {
tempNode1 = tempNode1.getNext();
temp1 = tempNode1.getSum();
checkA = tempNode1.getValue1();
checkB = tempNode1.getValue2();
checkC = tempNode1.getValue3();
}
for (int y = 0; y < list2.size(); y++) {
if (y == 0) {
tempNode2 = list2.getFirst();
temp2 = tempNode2.getSum();
checkD = tempNode2.getValue1();
checkE = tempNode2.getValue2();
checkF = tempNode2.getValue3();
}
else {
tempNode2 = tempNode2.getNext();
temp2 = tempNode2.getSum();
checkD = tempNode2.getValue1();
checkE = tempNode2.getValue2();
checkF = tempNode2.getValue3();
}
if (temp1 == temp2 && checkC <= checkD) {
checkA = (long) Math.pow(checkA, 1.0/5);
checkB = (long) Math.pow(checkB, 1.0/5);
checkC = (long) Math.pow(checkC, 1.0/5);
checkD = (long) Math.pow(checkD, 1.0/5);
checkE = (long) Math.pow(checkE, 1.0/5);
checkF = (long) Math.pow(checkF, 1.0/5);
System.out.println("Solution: "+checkA+"," + checkB+"," + checkC+"," + checkD+"," + checkE+"," + checkF);
}
if (x == list1.size()-1) {
System.exit(0);
}
}
}
}

public DLList quickSort(DLList S) {
DLList L = new DLList();
DLList E = new DLList();
DLList G = new DLList();

if (S.size() <= 1) {
return S;
}

long p = S.getLast().getSum();
while (!S.isEmpty()) {
if (S.getLast().getSum() < p) {
}
else if (S.getLast().getSum() == p) {
}
else {
}
}

quickSort(L);
quickSort(G);

while (!L.isEmpty()) {
}
while (!E.isEmpty()) {
}
while (!G.isEmpty()) {
}
return S;
}

public static void main(String[] args) {
Scanner input = new Scanner(System.in);

System.out.println("Enter a value of 72 or higher: ");
String command = input.nextLine();

EquationSolver solver = new EquationSolver(command);
}
}

public class Node {
private long sum, val1, val2, val3;
private Node prev, next;

public Node(long sumVal, long value1, long value2, long value3, Node p, Node n) {       // stores the values in a node
this.sum = sumVal;
this.val1 = value1;
this.val2 = value2;
this.val3 = value3;
this.prev = p;
this.next = n;
}

public long getSum() {      // returns the value for key
return sum;
}

public long getValue1() {       // returns length value of the node
return val1;
}

public long getValue2() {
return val2;
}

public long getValue3() {
return val3;
}

public Node getPrev() {
return prev;
}

public Node getNext() {     // returns the next node of current node
return next;
}

public void setPrev(Node nPrev) {
prev = nPrev;
}

public void setNext(Node nNext) {       // sets the next node of current node
next = nNext;
}
}

-
As a general piece of advice, when you're stuck, use a profiler like jvisualvm. –  biziclop Nov 17 '12 at 0:09
"doubly linked list" What's wrong with ArrayList? –  Nick ODell Nov 17 '12 at 2:11

## Time Complexity

You have three nested loops each going to n and in the innermost body you add to the linked list, which makes that list roughly size O(n^3). Same thing for the second list. Afterwards, you have loops over those lists nested, which gives you O(n^6).

Instead of even building the second list, I would suggest to switch to an entirely different data structure: You could store the initial list's result in a HashMap indexed by their sum. In the second round (where you previously created the second list) you would then just lookup the "sum" value of D,E, and F in that map. If a corresponding key exists, you have found a solution. While this does not really change the theoretical complexity, it does give you less required space, less object creations, and no need for even running any sorting algorithms. (If you care about multiple solutions, you may need to map the sum to a list of possible values.)

## Data Structures

We have no information about your DLList class, but there is absolutely no reason to roll your own doubly-linked list instead of java.util.LinkedList. Similarly, why do you write your own quicksort implementation instead of relying to the proven and fast sorting implementations already available?

## Code Structure / Style

Your EquationSolver looks like a mess. Around a dozen local variables and a huge block of code all in one method smells bad. You should refactor this with "Extract to Method" heavily.

Your Node class is kind of off. Firstly, it does not need the reference to other nodes at all, if you relied on the existing list implementations. Then, it would not really be a node anymore anyways, and you'd have to think up a proper name for it. Secondly, storing three values and their sum is a huge source of errors, because the values may easily become inconsistent. Instead, you should just compute the sum from the given other values (on demand, or in the constructor). (Note that you could store D and E negatively to make this work.) Given all of this, your class Node rather resembles a Tuple3 class, i.e. a class that represents a tuple of 3 values.

-
Actually, running an O(n^3) algorithm twice doesn't give you an O(n^6) algorithm, it gives you O(2(n^3)). –  ZeroOne Nov 19 '12 at 16:42
It's not running twice, but nested. –  Frank Nov 20 '12 at 19:25
I can only first spot a regular "for" loop, then a nested "for for for" loop, then another "for for for" loop, and finally a "for for" loop. I still cannot see where there's a "for for for for for for" loop. What am I missing? –  ZeroOne Nov 20 '12 at 22:41
The "for for" loop that loops over list1 outside and list2 inside with each list being roughly n^3-sized (after the sort calls). –  Frank Nov 21 '12 at 6:17

The most important point is the comment in the accepted answer in your related post in SO: You are not using that the lists are ordered. Instead of checking every value in list1 and list2 you could move along them at the same time.

Rough idea:

When y in list2 is larger than x in list1 then select a larger x until you get a value larger than y and then select a larger y, etc. As it is the code seem to me to be O(n^6).

Another minor thing is the list generation: you don't need to compare b and c in the second nested loop since c = i^5 and b=j^5 then you can make the second cycle go up to i instead of numVal. The same applies to the third nested loop.

The result would be something like:

for (int i = 1; i < numVal; i++) {
c = values[i];

for (int j = 1; j < i; j++) {
b = values[j];

for (int k = 1; k < j; k++) {
a = values[k];


Hope this things help.

-
So basically rather than using two nested loops for comparison, I should compare the lists while iterating through them at the same time? Also if I do it the way you mention it, will it run in O(N^3logN) time? –  Somebody Nov 17 '12 at 1:52
I would not feel confident enough to assert if that would be the running time but it would seem so. (2*N^3 to generate the lists, N^3 log(N^3) = 3*N^3 logN to sort them and 2*N^3 to iterate through them) –  madth3 Nov 17 '12 at 2:01
Oh ok. As for iterating through the lists, wouldn't they both iterate through at the same time so the values of x and y will always be the same, until it reaches the end of list2 as the size of it may be smaller? –  Somebody Nov 17 '12 at 2:06

When you compare sorted lists, you want to find identical values. It can be done in one pass, without nested loops. Take first values from both lists and compare. If values are equal, only then make additional checks, then take next values from both lists. If they are not equal, take next value from the list from which node with less value was taken.

-
Ok so I implemented it that way, however it only finds one solution and then it stops searching. It doesn't terminate, but it just stops the search for more solutions for higher N values. –  Somebody Nov 17 '12 at 2:56
what does it mean "stops but not terminate"? Infinite loop? –  Alexei Kaigorodov Nov 17 '12 at 3:03
Like it will print out this: Enter a value of 72 or higher: 94 Solution: 19,43,46,47,67,72 From what I know, there is a second solution it needs to find as well, but it just stops right there. However the code is still running, just not finding any more solutions. It could be a possible infinite loop. –  Somebody Nov 17 '12 at 3:09