Solving Diophantine equations

Question

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()) {
                            list1.addFirst(tempNode1);
                            refNode1 = tempNode1;
                        }
                        else {
                            list1.addAfter(refNode1, tempNode1);
                            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()) {
                                list2.addFirst(tempNode2);
                                refNode2 = tempNode2;
                            }
                            else {
                                list2.addAfter(refNode2, tempNode2);
                                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) {
            L.addLast(S.remove(S.getLast()));
        }
        else if (S.getLast().getSum() == p) {
            E.addLast(S.remove(S.getLast()));
        }
        else {
            G.addLast(S.remove(S.getLast()));
        }
    }

    quickSort(L);
    quickSort(G);

    while (!L.isEmpty()) {
        S.addLast(L.remove(L.getFirst()));
        }
    while (!E.isEmpty()) {
        S.addLast(E.remove(E.getFirst()));
        }
    while (!G.isEmpty()) {
        S.addLast(G.remove(G.getFirst()));
        }
    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;
}
}

Answer 1

Several points to be said about this code:

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.

Answer 2

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.

Answer 3

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.