Euler.java

Below is the syntax highlighted version of Euler.java from §5.6 Cryptography.

/******************************************************************************
 *  Compilation:  javac Euler.java
 *  Execution:    java Euler N
 *  
 *  Tests whether there are any four positive integers that satisfy
 *  a^4 + b^4 + c^4 = d^4. Euler conjectured that no such solutions
 *  exists, but his conjecture was later disproved.
 *
 *  Mathematical shortcut: can assume
 *     - a is a multiple of 8
 *     - b is a multiple of 40
 *     - d-1 is a multiple of 8
 *     - either c+d is a multiple of 1024 or d-c is a multiple of 1024
 *     - d is not a multiple of 5
 *
 *  % java -Xmx900MB -Xms900MB Euler 500000
 *  95800^4 + 414560^4 + 217519^4 = 422481^4
 *  109208^4 + 367120^4 + 259225^4 = 481433^4
 *  137992^4 + 167600^4 + 32639^4 = 246913^4
 *  138688^4 + 332520^4 + 330537^4 = 421673^4
 *  414560^4 + 95800^4 + 217519^4 = 422481^4
 * 
 *  This takes approximately 75 minutes and used 736MB of memory.
 *
 *  Known bugs:
 *  -----------
 *  -  Only the first solution actually is valid, the others
 *     satisfy a^4 + b^4 = d^4 - c^4 (mod 2^64). These numbers should
 *     be checked with extended precision arithmetic.
 *  -  It is possible, but extremely unlikely, that we miss a solution.
 *     This could happen if two values of d^4 - c^4 are equal (mod 2^64)
 *     AND d^4 - c^4 is equal to a^4 + b^4 (mod 2^64)  AND the first
 *     (d, c) pair does not form a valid solution with (a, b) AND
 *     the second (d, c) pair does. We could modify the hash search
 *     function to return all items with a given sum, but this seems
 *     like overkill.
 *
 *
 ******************************************************************************/

public class Euler {
    static long[] four;       // table of fourth powers
    static Item[] st;         // symbol table - hash table

    static int hash(long sum) { return (int) (sum) >>> 7; }

   /***************************************************************************
    *  Insert item into ST.
    ***************************************************************************/
    static void insert(Item x) {
        int i = hash(x.sum);
        while (st[i] != null) {
            i++;
            if (i >= st.length) i-= st.length;
        }
        st[i] = x;
    }

   /***************************************************************************
    *  Search ST for given key.
    ***************************************************************************/
    static Item search(long sum) {
        int i = hash(sum);
        while (st[i] != null) {
            if (st[i].sum == sum) return st[i];
            i++;
            if (i >= st.length) i-= st.length;
        }
        return null;
    }


   /***************************************************************************
    *  Item to store in hash table.
    ***************************************************************************/
    private static class Item {
        int d, c;
        long sum;    // d^4 - c^4  (mod 2^64)
        
        Item(int d, int c, long sum) { this.d = d; this.c = c; this.sum = sum; }
    }


    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);
        long a4, b4, c4, d4;
        st = new Item[33554432];   // 2^25

       /**************************************************************
        * Precompute i^4 (mod 2^64) by relying on fact that overflow
        * of long in Java is automatically done this way.
        **************************************************************/
        long[] four = new long[N+1];
        for (int i = 0; i <= N; i++) {
            four[i] = i;
            four[i] *= four[i];
            four[i] *= four[i];
        }
        StdOut.println("Done precomputing table of fourth powers");

       /**************************************************************
        * Enumerate of all pairs (c, d) and put d^4 - c^4 (mod 2^64)
        * in a hash table along with c and d.
        **************************************************************/
        for (int d = 1; d < N; d += 8) {
            if (d % 5 == 0) continue;
            d4 = four[d];
            for (int c = d % 1024; c < d; c += 1024) {
                c4 = four[c];
                insert(new Item(d, c, d4 - c4));
            }
            for (int c = 1024 - d % 1024; c < d; c += 1024) {
                c4 = four[c];
                insert(new Item(d, c, d4 - c4));
            }
        }

        StdOut.println("Done building hash table");

       /**************************************************************
        * Enumerate of all pairs (a, b) and search in a hash table
        * for a^4 + b^4 (mod 2^64). If match, perform full precision
        * check to see if a^4 + b^4 = d^4 - c^4
        **************************************************************/
        for (int a = 8; a < N; a += 8) {
            a4 = four[a];
            if (a % 10000 == 0) StdOut.println(a);
            for (int b = 40; b < N; b += 40) {
                b4 = four[b];
                if (search(a4 + b4) != null) {
                    Item item = search(a4 + b4);
                    StdOut.print(a + "^4 + " + b + "^4 + ");
                    StdOut.println(item.c + "^4 = " + item.d + "^4");
                }
            }
        }

    }
}