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;
}
}

public class DLList {
protected Node head, tail;
protected int size;

public DLList() {
    this.size = 0;          // initially sets the size of the list to be 0
    this.head = new Node(0, 0, 0, 0, null, null);       // initially sets the head to be null
    this.tail = new Node(0, 0, 0, 0, null, null);       // initially sets the tail to be null
    head.setNext(tail);
    tail.setPrev(head);
}

public boolean isEmpty() {      // checks to see whether list is empty
    return size == 0;
}

public int size() {     // returns size of list
    return size;
}

public Node getFirst() throws IllegalStateException {       // gets the head of list
    if (isEmpty()) throw new IllegalStateException("List is empty.");
    return head.getNext();
}

public Node getLast() throws IllegalStateException {        // gets the tail of list
    if (isEmpty()) throw new IllegalStateException("List is empty.");
    return tail.getPrev();
}

public Node getPrev(Node v) throws IllegalArgumentException {       // returns node before given node
    if (v == head) throw new IllegalArgumentException
        ("Cannot move back past the head of the list.");
    return v.getPrev();
}

public Node getNext(Node v) throws IllegalArgumentException {       // returns node after given node
    if (v == tail) throw new IllegalArgumentException
        ("Cannot move forward past the tail of the list.");
    return v.getNext();
}

public void addBefore(Node v, Node z) {     // inserts node z before given node v
    Node u = getPrev(v);
    z.setPrev(u);
    z.setNext(v);
    v.setPrev(z);
    u.setNext(z);
    size++;
}


public void addAfter(Node v, Node z) {      // inserts node z after given node v
    Node w = getNext(v);
    z.setPrev(v);
    z.setNext(w);
    w.setPrev(z);
    v.setNext(z);
    size++;
}

public void addFirst(Node v) {      // adds first node in the list
    addAfter(head, v);
}

public void addLast(Node v) {       // adds last node in the list
    addBefore(tail, v);
}

public Node remove(Node v) {        // removes a given node from the list
    Node u = getPrev(v);
    Node w = getNext(v);
    w.setPrev(u);
    u.setNext(w);
    v.setPrev(null);
    v.setNext(null);
    size--;
    return v;
}
}
share|improve this question

migrated from stackoverflow.com Nov 17 '12 at 0:32

This question came from our site for professional and enthusiast programmers.

1  
As a general piece of advice, when you're stuck, use a profiler like jvisualvm. –  biziclop Nov 17 '12 at 0:09
add comment

2 Answers 2

up vote 1 down vote accepted

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.

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

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.

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