4
\$\begingroup\$

I'm just wanting feedback on the efficiency, design and layout of this code if possible please. I suspect it's weird having a constructor with nothing in. I'd be grateful if it could be explained how to modify the code to fit in with conventions, especially in this respect, but also in others.

package cubes;

import java.util.ArrayList;

public class Cubes {

    ArrayList<Integer> sum = new ArrayList<Integer>();
    ArrayList<Integer> x = new ArrayList<Integer>();
    ArrayList<Integer> y = new ArrayList<Integer>();
    boolean found = false;
    int  cSum = 0, a = 0 , b = 0, c = 0, d = 0, k, floor;
    Integer cubeSum, X, Y, answer;
    double K, J, cs;
    int iterations;

    public static void main(String[] args) {

        Cubes c = new Cubes();
        c.find();
    }

    public Cubes()
    {

    }

    private void find()
    {
        int i = 3;

        K = (double)2;
        J = (double)1;
        cs = Math.pow(K,3.0)+Math.pow(J,3.0);
        cubeSum = new Integer((int) cs);

        sum.add(cubeSum);
        x.add(1);
        y.add(2);

        i = 4;

        while(found!=true)
        {
            floor = (int)Math.floor(i/2);

            for(int j = 1; j < floor+1; j++)
            {
                k=i-j;
                K = (double)k;
                J = (double)j;
                cs = Math.pow(K,3.0)+Math.pow(J,3.0);
                cubeSum = new Integer((int) cs);
                X = new Integer((int) j);
                Y = new Integer((int) k);

                for (int l = 0; l < sum.size(); l++)
                {
                    a = (int)x.get(l);
                    b = (int)y.get(l);
                    if(cubeSum.compareTo(sum.get(l))==0)
                    {
                        if (a != j && a != k && b != j && b != k)
                        {
                            c=j;
                            d=k;
                            System.out.println("The first positive integer "
                            + "expressible as the sum\nof 2 different positive"
                            + " cubes in 2 different ways\nis "
                            + cubeSum + " = " +a+"^3 + "+b+"^3 = "
                            + c+"^3 + "+d+"^3");
                            found=true;
                        }
                    }
                }

                sum.add(cubeSum);
                x.add(X);
                y.add(Y);
            }
            i++;
        }
    }
}
\$\endgroup\$
1

2 Answers 2

4
\$\begingroup\$

There are a few things I would like to comment on:

  1. Whether you have an empty constructor or not is irrelevant. In your case, there already was a public 'default' (empty) constructor, and you have just made it explicit. This is neither a good thing nor a bad thing. Many classes have an empty constructor. Many IDE's will warn you that you have an empty method though, so I recommend that you put a comment in there to make it happy: // empty constructor does nothing. On the other hand, you will have the identical Java behaviour if you remove the constructor entirely (the default constructor is public Cubes() {} anyway).
  2. Do you really need to even create an instance of the class? Sometimes it makes things neater, but sometimes it is just redundant. In your case, I would be just as happy to put all the logic in the main method (you do not need to do anything object related, so why bother).
  3. in general, when doing 'high performance computing' (which is what this problem is), it is best to optimize the algorithms as much as possible. In your case, th regular conversions of values from double to int and to Integer is just wasting CPU time.
  4. similarly, storing values as Integers in an ArrayList means that you are creating lots of Integer values and you are regularly converting them back to int to do the math.
  5. finally, sometimes moving the heavy computations (the Math.pow(....) ) out of the loop is a good thing. Is there any reason why you have to continuously repeat the calculation of integer powers?

So, taking the above in to consideration, consider the following method, it has the properies:

  1. it precomputes the powers, saving redundant computation time in the loops.
  2. it does not do any primitive to Object 'auto-boxing'.
  3. it uses binary search for fast lookups.
  4. it uses primitive-based comparisons and arithmetic.
public static void main(String[] args) {

    long[] cubes = new long[8192];
    int ncubes = 0;
    // your code limits the largest sum to Integer.MAX_INT (your code declares 'i' to be 'int')
    // I'll calculate all the way to half of Long.MAX_VALUE instead....
    // pre-calculate the cube value of all cubes less than Integer.MAX_INT.
    for (long i = 0; i < Integer.MAX_VALUE; i++) {
        final long cube = i * i * i;
        if (cube > (Long.MAX_VALUE >>> 1)) {
            break;
        }
        if (ncubes >= cubes.length) {
            cubes = Arrays.copyOf(cubes, cubes.length * 2);
        }
        cubes[ncubes++] = cube;
    }
    cubes = Arrays.copyOf(cubes, ncubes);

    System.out.println("There are " + ncubes + " int values which have cubes less than " + Long.MAX_VALUE);

    // Now, start from the smallest possible sum-of-cubes.
    // we start from 1 and 4 because we know that there needs to be at least 2 cubes between them in order
    // to have another pair that has the same sum.
    for (long sum = cubes[1] + cubes[4]; sum < Long.MAX_VALUE; sum++) {
        // go through all the 'i' cubes which are less than half the sum (because we still need to add a larger value)
        final long halfsum = sum >> 1;
        for (int i = 1; i < cubes.length - 4 && cubes[i] < halfsum; i++) {
            // find a 'partner' for cube[i] that together will add up to match the target sum
            final int jmatch = Arrays.binarySearch(cubes, i+3, cubes.length - (i + 3), sum - cubes[i]);
            if (jmatch >= 0) {
                // there's one pair that matches the target sum.... let's see if there's another.
                // the other pair will have to be somewhere in between these two values.
                for (int k = i+1; k <= jmatch - 2 && cubes[k] < halfsum; k++) {
                    // start scanning ahead, and look for it....
                    final long difference = sum - cubes[k];
                    int match = Arrays.binarySearch(cubes, k+1, jmatch, difference);
                    if (match >= 0) {
                        System.out.printf("Both pairs (%d,%d) and (%d,%d) have cube-sums of %d\n", i, jmatch, k, match, sum);
                    }
                }
            }
        }
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ Looks like a good answer. I haven't taken it all in yet. I must admit that I'm not familiar with the >> or >>> operators. \$\endgroup\$ Commented Nov 7, 2013 at 19:03
  • 1
    \$\begingroup\$ In all cases (in this code - because all the values are positive) they just mean 'divide by 2'. \$\endgroup\$
    – rolfl
    Commented Nov 7, 2013 at 19:03
  • \$\begingroup\$ Why not just use '/2'? +1 for info. I might have accepted this answer prematurely though. Was your code supposed to be a complete solution? If so, it doesn't seem to be correct, since it doesn't stop when it finds the Hardy-Ramanujan number. Your post does contain useful info though. I'm a fair way from understanding everything you've written, but I have already learnt some useful things. \$\endgroup\$ Commented Nov 7, 2013 at 19:31
  • 1
    \$\begingroup\$ If you are really only after the first valid numbers, then simply return after the System.out.println line. Otherwise it is complete.... but will keep running until it gets to very large combinations. \$\endgroup\$
    – rolfl
    Commented Nov 7, 2013 at 20:05
  • \$\begingroup\$ Good. I like it. Answer reaccepted. +1 for return info. I had thought of doing that, but for some reason I didn't bother and got distracted. In this particular case, searching ahead results in lots of unnecesary computation, but I suppose there are cases where it's worth doing so. \$\endgroup\$ Commented Nov 7, 2013 at 21:46
6
\$\begingroup\$

Discrete Mathematics

Discrete calculations should not be done using floating-point math. You should be suspicious of any results contaminated by floating-point math. The way to compute the cube of an integer is n * n * n. For larger powers, do repeated squaring, or use BigInteger.pow() (which is slower, but immune to overflow).

Variable Usage

To be honest, I found your code extremely difficult to read, mainly due to the way you misuse variables.

  • Scope: You should declare and define variables as close as possible to the point of use. If a variable only applies within a loop, declare and define it inside the loop. If it's local to a function, define it as a local variable in the function. Instead, you've used a lot of instance variables, which, for all practical purposes, are "global" (since you only have one class). As you really only have one function, all of the variables should have been local!
  • Proliferation: You've declared 19 instance variables. Surely fewer variables would suffice? A human brain can keep track of about 7 items at a time. You have cSum (an int), cubeSum (an Integer), and cs (a double) — which raises the question, how are they related? (Answer: cSum is never used, and cs is just a temporary variable that shouldn't have been needed at all.) Also, answer and iterations are never used. You've got so many variables that you couldn't keep track of the dead ones to prune.
  • Cryptic naming: Without studying the code, can you remember what x, y, k, X, Y, K, J, and floor mean? If not, then your variables are named too cryptically.
  • Unconventional naming: By connotation, I would expect x to represent a floating-point number, not a list of Integers. Then, you've also got X, which is a boxed version of j.
  • Misuse for flow control: To terminate the loop, why do you set a variable and test for found != true elsewhere? Just return after printing the result — you're done!

Language Disfluency

If you familiarize yourself with the Java language a bit more, you can express yourself less clumsily.

  • Prefer primitives: You should always prefer the primitives (e.g. int) to their boxed counterparts (Integer). Code written using primitives reads better and performs better. The boxed types exist mainly so that you can store them in collections such as ArrayList<Integer>. Even then, the compiler will automatically box and unbox the values for you, so you don't have to say new Integer(n).
  • Type Promotion: The compiler will automatically perform widening conversions, such as promoting int to double, so casting is unnecessary in those cases.
  • Integer division: When dividing an integer by an integer, the result will also be integral (with truncation towards 0). When you do (int)Math.floor(i/2), you're just promoting i / 2 to a double argument, rounding it to the same double, and casting the result back to an int. It would have been sufficient to just do i / 2.

Time Out… Let's Rewrite!

Let's rewrite the code using the trivial simplifications mentioned so far.

import java.util.ArrayList;

public class Cubes {

    public static void main(String[] args) {
        new Cubes().find();
    }

    private void find()
    {
        ArrayList<Integer> sum = new ArrayList<Integer>();
        ArrayList<Integer> x = new ArrayList<Integer>();
        ArrayList<Integer> y = new ArrayList<Integer>();
        int a, b, c, d;

        sum.add((2 * 2 * 2) + (1 * 1 * 1));
        x.add(1);
        y.add(2);

        int i = 4;

        while(true)
        {
            for(int j = 1; j < i/2 +1; j++)
            {
                int k=i-j;
                int cubeSum = (k * k * k) + (j * j * j);

                for (int l = 0; l < sum.size(); l++)
                {
                    a = (int)x.get(l);
                    b = (int)y.get(l);
                    if(cubeSum == sum.get(l))
                    {
                        if (a != j && a != k && b != j && b != k)
                        {
                            c=j;
                            d=k;
                            System.out.println("The first positive integer "
                            + "expressible as the sum\nof 2 different positive"
                            + " cubes in 2 different ways\nis "
                            + cubeSum + " = " +a+"^3 + "+b+"^3 = "
                            + c+"^3 + "+d+"^3");
                            return;
                        }
                    }
                }

                sum.add(cubeSum);
                x.add(j);
                y.add(k);
            }
            i++;
        }
    }
}

I find the rewritten version slightly more readable than the original, though I still can't really understand it.


Now, back to our regularly scheduled programming…

Algorithm

  • Magic numbers: You start with x.add(1), y.add(2), and i = 4. Where did those magic numbers come from? They're not naturally part of the problem, and you didn't explain.
  • x vs. y: What do lists x and y represent? How does a number end up on these lists, why would it appear on x rather than y, or y rather than x?
  • Commenting: What is the strategy of your code? Please outline it in a comment. Mathematical algorithms in general are complicated, and algorithms, more than anything else, need comments!
  • False proof: How do you know that you've found the minimum answer rather than just any answer? I'm not convinced at all. In fact, if you remove the return after System.out.println() and just let it run, you'll see that it prints 110808 = 6^3 + 48^3 = 27^3 + 45^3 before 110656 = 4^3 + 48^3 = 36^3 + 40^3. Therefore, the fact that your program prints 1729 is luck, not skill.
  • Separation of concerns: If you force yourself to separate the code that does input/output from the code that does pure computation, then you will also force yourself to write well organized code.

Proposed Solution

Since your algorithm is bogus, we'll have to start from scratch. I propose an algorithm in which we iterate through n = 1, 2, 3, 4, … until we find one that is the sum of two cubes. Then we test if it is also expressible as a sum of another two cubes. Since we're testing n in increasing sequence, we can be sure that the first result is indeed the minimum number meeting the criteria.

To test whether n is a sum of two cubes, we can successively try subtracting 13, 23, 33, 43, … and test whether the difference is also a perfect cube. To test whether the difference is a perfect cube, we could take its cube root (floating point — nope!), or check it against a list of perfect cubes (better — raising integers to the third power is easy). I've written a class called Cubes to help enumerate all perfect cubes.

There's a lot of verbose supporting code. However, if you look at the heart of the solution, which is hardyRamanujanBreakdown(long n), you'll find it to be very readable.

I've also written it such that you can easily modify the program to find subsequent numbers that are representable as sums of two cubes in two ways. If you let this run infinitely, it's vulnerable to overflow, but you'll have hit CtrlC long before that happens. ☺

It's also slower than your original, but the original strategy is flawed, so it doesn't count.

import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;

//////////////////////////////////////////////////////////////////////

/**
 * An iterator of positive perfect cubes, starting from 1, and ignoring
 * overflow.
 */
class Cubes implements Iterator<Long> {
    /**
     * An "infinite" set of all perfect cubes.
     */
    private static SortedSet<Long> allCubes = new TreeSet<Long>();

    /**
     * Helper to generate more members of allCubes as needed.
     */
    private static Cubes allIter = new Cubes();
    static {
        allCubes.add(allIter.next());
    }

    public static boolean isCube(long num) {
        while (num > allCubes.last()) {
            allCubes.add(allIter.next());
        }
        return allCubes.contains(num);
    }

    public static int cubeRoot(long num) {
        while (num > allCubes.last()) {
            allCubes.add(allIter.next());
        }
        return 1 + allCubes.headSet(num).size();
    }

    public static final long cube(int num) {
        return (long)num * num * num;
    }


    private int i = 1;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public Long next() {
        return cube(this.i++);
    }

    public Cubes dup() {
        Cubes moreCubes = new Cubes();
        moreCubes.i = this.i;
        return moreCubes;
    }
}

//////////////////////////////////////////////////////////////////////

public class HardyRamanujan implements Iterator<Long> {

    private long n;
    private long[] breakdown;

    public HardyRamanujan() {
        this.n = 1;
    }

    @Override
    public boolean hasNext() {
        // Ignores overflow
        return true;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public Long next() {
        while (null == (this.breakdown = hardyRamanujanBreakdown(this.n))) {
            this.n++;
        }
        return this.n++;
    }

    /**
     * Returns the breakdown of the current Hardy-Ramanujan number n as an
     * array of four perfect cubes [a, b, c, d].  n = a + b = c + d.
     * a < c <= n/2 <= d < b.  Returns null if next() has never been called.
     */
    public long[] breakdown() {
        return this.breakdown;
    }

    private static long[] hardyRamanujanBreakdown(long n) {
        long a, b, c, d;

        // Exists n == a + b, where a and b are cubes?
        Cubes cubes = new Cubes();
        while ((a = cubes.next()) < n / 2) {
            if (!Cubes.isCube(b = n - a)) {
                continue;
            }

            // If so, exists n == c + d, where c and d are cubes, and c > a ?
            Cubes moreCubes = cubes.dup();
            while ((c = moreCubes.next()) <= n / 2) {
                if (!Cubes.isCube(d = n - c)) {
                    continue;
                }
                return new long[] { a, b, c, d };
            }
        }
        return null;
    }

    public static void main(String[] args) {
        HardyRamanujan hrIter = new HardyRamanujan();
        do {
            long hrNum = hrIter.next();
            long[] breakdown = hrIter.breakdown();
            System.out.format("%d = %d^3 + %d^3 = %d^3 + %d^3\n",
                              hrNum,
                              Cubes.cubeRoot(breakdown[0]),
                              Cubes.cubeRoot(breakdown[1]),
                              Cubes.cubeRoot(breakdown[2]),
                              Cubes.cubeRoot(breakdown[3]));
        } while (false); // Change to true to get more!
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ By the way, the solution proposed here is essentially the same as @rolfl's algorithm, just implemented differently. \$\endgroup\$ Commented Nov 8, 2013 at 8:34
  • \$\begingroup\$ Thanks: you've made lots of useful points here, especially that the algorithm I used obtains the result by luck. (+1). \$\endgroup\$ Commented Nov 8, 2013 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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