Solving Diophantine equations - reloaded once

Question

Inspired by this question, I was curios, if I could solve it for large n. For n=6209, its fifth power overflows long and I decided to stop below such numbers. The current algorithm reimplements the one from the linked question (the description, not the code) and could use some optimizations (but I'm not asking specifically about them as I'm having an idea already). For n=1000, the computation takes half an hour and the complexity is cubic, so there's no reason to look any further before optimizations.

Feel free to ignore slightly deviating coding conventions. My goal was to quickly create a solver and to keep the code short and the effort small. The next time I'll do the optimizations.

My biggest concern is understandability. I wrote nearly as much Javadoc as code and it took me longer, but I'm unsatisfied with the result (although I only care about clarity for people having read the linked question).

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Verify.verify;

import java.util.Collection;
import java.util.Map;
import java.util.Set;

import lombok.Getter;
import lombok.RequiredArgsConstructor;
import lombok.ToString;

import com.google.common.collect.ComparisonChain;
import com.google.common.collect.HashMultimap;
import com.google.common.collect.Multimap;
import com.google.common.collect.Sets;

public class Diophantinus1 {
    @RequiredArgsConstructor @Getter @ToString private static class Triple {
        private final int x, y, z;
    }

    @RequiredArgsConstructor @Getter @ToString static class Solution implements Comparable<Solution> {
        boolean isValid() {
            return pow5(a) + pow5(b) + pow5(c) + pow5(d) + pow5(e) == pow5(f);
        }

        @Override public int compareTo(Solution o) {
            return ComparisonChain
                    .start()
                    .compare(a, o.a)
                    .compare(b, o.b)
                    .compare(c, o.c)
                    .compare(d, o.d)
                    .compare(e, o.e)
                    .compare(f, o.f)
                    .result();
        }

        private final int a, b, c, d, e, f;
    }

    /**
     * Find all integer solutions of {@code a**5 + b**5 + c**5 + d**5 + e**5 = f**5}
     * with {@code 1 <= a <= b <= c <= d <= e <= f <= n}.
     */
    static Set<Solution> findSolutions(int n) {
        // TODO Replace the magic constant by some computation.
        return findSolutions(n, 12);
    }

    /**
     * Find all integer solutions of {@code a**5 + b**5 + c**5 + d**5 + e**5 = f**5}
     * with {@code 1 <= a <= b <= c <= d <= e <= f <= n}.
     *
     * <p>The algorithm goes as described in https://codereview.stackexchange.com/q/18720/14363
     * For triples {@code a, b, c} it evaluates {@code value = a**5 + b**5 + c**5} and
     * for triples {@code d, e, f} it evaluates {@code value = f**5 - d**5 - e**5}.
     *
     * <p>The algorithm gathers and matches the values.
     * Because of huge memory requirements, the solution set is partitioned into {@code 2**maskBits} subsets.
     * In the n-th step, only values congruent to n modulo 2**maskBits are considered.
     */
    private static Set<Solution> findSolutions(int n, int maskBits) {
        checkArgument(1 <= maskBits && maskBits <= 30);
        final Set<Solution> result = Sets.newTreeSet();
        for (int maskValue=0; maskValue < (1<<maskBits); ++maskValue) {
            final Multimap<Long, Triple> abcMultimap = computeSums(n, false, maskBits, maskValue);
            final Multimap<Long, Triple> defMultimap = computeSums(n, true, maskBits, maskValue);

            for (final Map.Entry<Long, Collection<Triple>> entry : abcMultimap.asMap().entrySet()) {
                final Long key = entry.getKey();
                final Collection<Triple> second = defMultimap.get(key);
                if (second.isEmpty()) continue;
                final Collection<Triple> first = entry.getValue();
                for (final Triple abc : first) {
                    for (final Triple def : second) {
                        if (abc.z() > def.x()) continue;
                        final boolean added =
                                result.add(new Solution(abc.x(), abc.y(), abc.z(), def.x(), def.y(), def.z()));
                        verify(added);
                    }
                }
            }
        }
        return result;
    }

    /**
     * For all {@code 1 <= x <= y <= z <= n} compute possible values of the expression
     * {@code value = (subtract ? -1 : 1) * (x**5 + y**5) + z**5}.
     *
     * <p>In order to conserve memory, discard values for which {@code (value & mask) != maskValue}
     * where {@code mask = (1 << maskBits) - 1} and also discard non-positive values.
     *
     * <p>If a value doesn't get discarded,
     * store it together with the {@code Triple(x, y, z)} in the result {@code Multimap}.
     *
     * <p>The algorithm is obviously inefficient as the vast majority of values gets discarded.
     */
    private static Multimap<Long, Triple> computeSums(int n, boolean subtract, int maskBits, int maskValue) {
        checkArgument(n < LIMIT, "n must be smaller than %s to prevent overflow, but was %s", LIMIT, n);
        checkArgument(1 <= maskBits && maskBits <= 30);
        final int mask = (1 << maskBits) - 1;
        checkArgument(0 <= maskValue && maskValue < mask);

        final Multimap<Long, Triple> result = HashMultimap.create();
        for (int x=1; x<n; ++x) {
            final long x5 = pow5(x);
            for (int y=x; y<n; ++y) {
                final long y5 = pow5(y);
                final int sign = subtract ? -1 : +1;
                final long sum = sign * (x5 + y5);
                for (int z=y; z<n; ++z) {
                    final long z5 = pow5(z);
                    final long value = sum + z5;
                    if ((value & mask) != maskValue) continue;
                    if (value <= 0) continue;
                    result.put(value, new Triple(x, y, z));
                }
            }
        }
        return result;
    }

    private static long pow5(int x) {
        assert x < LIMIT;
        final long x2 = (long) x * x;
        return x * x2 * x2;
    }

    private static final int LIMIT = (int) Math.floor(Math.pow(Long.MAX_VALUE, 1.0/5)) + 1;
}

Answer 1

1. Your for loops are too nested - consider extracting them to separate private methods, something like:

   for (final Map.Entry<Long, Collection<Triple>> entry : abcMultimap.asMap().entrySet()) {
       analyzeEntry(entry);
   }
   

2. Solution's constructor gets quite unreadable. I assume it is generated by Lombok, but still, new Solution(abc.x(), abc.y(), abc.z(), def.x(), def.y(), def.z()) is too long, and while quite clear, I guess you could add a more readable public Solution(Triple a, Triple b) constructor to improve readability.

3. By convention, you should stick to using brackets for if's - it's what most coders would expect. That said, if (second.isEmpty()) continue; is not a huge abuser of that, but an abuser nonetheless.

4. You've marked all your final variables as final - for me that's dead code, it only adds to the visual clutter.

5. This code:

   private static long pow5(int x) {
       assert x < LIMIT;
       final long x2 = (long) x * x;
       return x * x2 * x2;
   }
   

   versus

   Math.pow(x, 5)
   

6. This code:

   private static final int LIMIT = (int) Math.floor(Math.pow(Long.MAX_VALUE, 1.0/5)) + 1;
   

   versus

   private static final int LIMIT = 6209; // LIMIT^5 <= Long.MAX_VALUE