Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

Thanks!

The following is my 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;
}
}
share|improve this question
1  
"doubly linked list" What's wrong with ArrayList? –  Nick ODell Nov 17 '12 at 2:11
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.