Universally Accessible Distributed Computing on Public, Heterogeneous Networks,
Applied to the Search for Mersenne Primes
Appendix B: Processing Resource Applet
Appendix C: Control Server Source Code
Processing Resource Source Code
The processing resource source code consists of five classes and three interfaces, in five files:
Applet.java
package org.projectguts.gutsxl.distrib; import java.math.BigInteger; import java.net.URL; import java.util.BitSet; import java.util.Date; import org.apache.xmlrpc.XmlRpcException; import org.apache.xmlrpc.client.XmlRpcClient; import org.apache.xmlrpc.client.XmlRpcClientConfigImpl; import org.apache.xmlrpc.client.XmlRpcClientException; /** * This class extends the standard {@link javax.swing.JApplet JApplet} class to * implement a distributed processing resource, capable of performing the tasks * required to search for Mersenne primes. The applet communicates with a task * distribution server via XML-RPC – receiving task assignments from the * server, and sending the processing results back to the server. * * @author Max Bond, Harsha Dodda, and Nick Bennett. * @version 1.0.0412 */ public class Applet extends javax.swing.JApplet implements Sieve.Listener, LucasLehmer.Listener, TrialDivision.Listener { private static final String SLEEP_TASK_STATUS = "Idle"; private static final String GETTING_NEXT_TASK_STATUS = "Getting next task from distribution server"; private static final String SENDING_PARTIAL_RESULTS_STATUS = "Sending in-process result to task distribution server"; private static final String SENDING_RESULTS_STATUS = "Sending results to task distribution server"; private static final String LUCAS_LEHMER_TASK_PATTERN = "Testing M(%d) for primality"; private static final String SIEVE_TASK_PATTERN = "Sieving for primes in {%d...%d}"; private static final String TRIAL_DIVISION_TASK_PATTERN = "Performing trial division on M(%d)"; private static final String LUCAS_LEHMER_START_HISTORY_PATTERN = "[%1$tF %1$tT] Started Lucas-Lehmer test on M(%2$d).\n"; private static final String LUCAS_LEHMER_RESUME_HISTORY_PATTERN = "[%1$tF %1$tT] Resumed Lucas-Lehmer test on M(%2$d) at s(%3$d).\n"; private static final String LUCAS_LEHMER_STATUS_HISTORY_PATTERN = "[%1$tF %1$tT] \ts(%3$d) = %4$s.\n"; private static final String CONDENSED_RESIDUE_PATTERN = "%s...%s (%d digits)"; private static final String LUCAS_LEHMER_RESULT_HISTORY_PATTERN = "[%1$tF %1$tT] Completed Lucas-Lehmer test: M(%2$d) is %3$s.\n"; private static final String LUCAS_LEHMER_RESULT_TRUE_STRING = "prime"; private static final String LUCAS_LEHMER_RESULT_FALSE_STRING = "composite"; private static final String SIEVE_START_HISTORY_PATTERN = "[%1$tF %1$tT] Started Sieve of Eratosthenes on {%2$d...%3$d}.\n"; private static final String SIEVE_RESULT_HISTORY_PATTERN = "[%1$tF %1$tT] Completed Sieve of Eratosthenes on {%2$d...%3$d}; " + "found %4$d primes: %5$s.\n"; private static final String TRIAL_DIVISION_START_HISTORY_PATTERN = "[%1$tF %1$tT] Started trial division on M(%2$d).\n"; private static final String TRIAL_DIVISION_RESULT_HISTORY_PATTERN = "[%1$tF %1$tT] Completed trial division: M(%2$d) %3$s.\n"; private static final String TRIAL_DIVISION_RESULT_TRUE_STRING = "might be prime"; private static final String TRIAL_DIVISION_RESULT_FALSE_STRING = "is composite"; private static final String GET_WORK_METHOD = "request_work"; private static final String LUCAS_LEHMER_RESULT_METHOD = "post_lucas_lehmer_result"; private static final String LUCAS_LEHMER_STATUS_METHOD = "post_lucas_lehmer_status"; private static final String SIEVE_RESULT_METHOD = "post_sieved_primes"; private static final String TRIAL_DIVISION_RESULT_METHOD = "post_trial_division_result"; private static final int IDLE_TASK_FLAG = 0; private static final int SIEVE_TASK_FLAG = 1; private static final int TRIAL_DIVISION_TASK_FLAG = 2; private static final int LUCAS_LEHMER_TASK_FLAG = 4; private static final int ALL_TASKS_FLAGS = SIEVE_TASK_FLAG | TRIAL_DIVISION_TASK_FLAG | LUCAS_LEHMER_TASK_FLAG; private static final String SERVICE_URL_PARAM = "serverUrl"; private static final String SERVER_TIMEOUT_PARAM = "serverTimeout"; private static final String POLL_INTERVAL_PARAM = "pollInterval"; private static final String UPDATE_THRESHOLD_PARAM = "updateThreshold"; private static final String HISTORY_ITERATIONS_PARAM = "historyIterations"; private static final String DEFAULT_SERVICE_URL = "distribution-server.cgi"; private static final int DEFAULT_SERVER_TIMEOUT = 60000; // 60 seconds private static final long DEFAULT_POLL_INTERVAL = 10000; // 10 seconds private static final long DEFAULT_UPDATE_THRESHOLD = 600000; // 10 minutes private static final int DEFAULT_HISTORY_ITERATIONS = 10000; private String serviceUrl; private int serverTimeout; private long pollInterval; private long updateThreshold; private int historyIterations; private XmlRpcClient client; private boolean running; private String jobKey; private long lastUpdate; private Thread nextTask; private Sieve sieve; private TrialDivision trialDivision; private LucasLehmer lucasLehmer; private Thread update; /** * Initiates the <code>Applet</code> by creating the UI elements, reading * parameter values (generally set in the <param> child elements * within the <applet> tag in an HTML page), and configuring the * XML-RPC communications context. */ @Override public void init() { try { XmlRpcClientConfigImpl config = new XmlRpcClientConfigImpl(); java.awt.EventQueue.invokeAndWait(new Runnable() { public void run() { initComponents(); } }); readAppletParameters(); config.setServerURL(new URL(getDocumentBase(), serviceUrl)); config.setReplyTimeout(serverTimeout); client = new XmlRpcClient(); client.setConfig(config); } catch (Exception ex) { ex.printStackTrace(); } } /** * Starts applet processing by invoking the {@link #next() next()} method to * request a processing assignment from the task distribution server. */ @Override public void start() { super.start(); running = true; next(); } /** * Creates a new {@link java.lang.Thread Thread} to request, via XML-RPC, a * processing assignment from the task distribution server. Polling for such * an assigment continues until one is received, with the thread sleeping * between requests. */ protected void next() { nextTask = new Thread() { @Override public void run() { boolean assigned = false; while (running && !assigned) { try { Object[] params = new Object[] {ALL_TASKS_FLAGS}; Object response; taskField.setText(SLEEP_TASK_STATUS); Thread.sleep(pollInterval); taskField.setText(GETTING_NEXT_TASK_STATUS); response = client.execute(GET_WORK_METHOD, params); assigned = dispatch(response); } catch (InterruptedException e) { // Thread has been awakened - probably because applet is // being stopped. No need to take corrective action. } catch (XmlRpcClientException e) { // Communication with server failed. e.printStackTrace(); // TODO - Determine and implement appropriate action, // if different from a simple retry. } catch (XmlRpcException e) { // An error occurred on the server. e.printStackTrace(); // TODO - Determine and implement appropriate action, // if different from a simple retry. } catch (Exception e) { // Some other error occurred; dump to the Java console. e.printStackTrace(); // TODO - Determine and implement appropriate action, // if different from a simple retry. } } } }; nextTask.start(); } /** * Creates and starts the appropriate task instance (one of {@link * LucasLehmer LucasLehmer}, {@link TrialDivision TrialDivision}, and {@link * Sieve Sieve}), depending on the specific assignment received from the * task distribution server. * * @param taskInfo <code>Object</code> containing the assignment * received from the task distribution server. * @return <code>boolean</code> value indicating whether * the assignment received resulted in creation of * a task instance (<code>true</code>) or not * (<code>false</code>). */ protected boolean dispatch(Object taskInfo) { boolean assigned = false; try { Object[] details = (Object[]) taskInfo; int taskFlag = (Integer) details[0]; Object[] params; int seed; switch (taskFlag) { case LUCAS_LEHMER_TASK_FLAG: int initialIterations; BigInteger initialResidue; params = (Object[]) details[1]; seed = (Integer) params[0]; initialIterations = (Integer) params[1]; initialResidue = (initialIterations != 0) ? new BigInteger((byte[]) params[2]) : null; jobKey = (initialIterations != 0) ? (String) params[3] : (String) params[2]; lucasLehmer = (initialIterations == 0) ? new LucasLehmer(seed) : new LucasLehmer(seed, initialIterations, initialResidue); lucasLehmer.addListener(this); lastUpdate = new Date().getTime(); taskField.setText( String.format(LUCAS_LEHMER_TASK_PATTERN, seed)); if (initialIterations == 0) { historyField.append(String.format( LUCAS_LEHMER_START_HISTORY_PATTERN, new Date(), seed)); } else { historyField.append(String.format( LUCAS_LEHMER_RESUME_HISTORY_PATTERN, new Date(), seed, initialIterations)); } scrollHistoryToEnd(); lucasLehmer.start(); assigned = true; break; case TRIAL_DIVISION_TASK_FLAG: params = (Object[]) details[1]; seed = (Integer) params[0]; jobKey = (String) params[1]; trialDivision = new TrialDivision(seed); trialDivision.addListener(this); taskField.setText( String.format(TRIAL_DIVISION_TASK_PATTERN, seed)); historyField.append( String.format(TRIAL_DIVISION_START_HISTORY_PATTERN, new Date(), seed)); scrollHistoryToEnd(); trialDivision.start(); assigned = true; break; case SIEVE_TASK_FLAG: int lowerBound; int upperBound; params = (Object[]) details[1]; lowerBound = (Integer) params[0]; upperBound = (Integer) params[1]; jobKey = (String) params[2]; sieve = new Sieve(lowerBound, upperBound); sieve.addListener(this); taskField.setText(String.format(SIEVE_TASK_PATTERN, lowerBound, upperBound - 1)); historyField.append( String.format(SIEVE_START_HISTORY_PATTERN, new Date(), lowerBound, upperBound - 1)); scrollHistoryToEnd(); sieve.start(); assigned = true; break; case IDLE_TASK_FLAG: default: break; } } catch (ClassCastException e) { e.printStackTrace(); // We didn't get an array of objects, or the first item wasn't an // int, etc. e.printStackTrace(); // TODO - Determine and implement appropriate action, // if different from a simple retry. } catch (Exception e) { // Some other error occurred; dump to the Java console. e.printStackTrace(); // TODO - Determine and implement appropriate action, // if different from a simple retry. } return assigned; } /** * Stops applet processing. All dependent threads are interrupted, but this * method doesn't block or try to join with the dependent threads. */ @Override public void stop() { super.stop(); running = false; if ((nextTask != null) && nextTask.isAlive()) { nextTask.interrupt(); } if ((sieve != null) && sieve.isAlive()) { sieve.interrupt(); } if ((lucasLehmer != null) && lucasLehmer.isAlive()) { lucasLehmer.interrupt(); } if ((trialDivision != null) && trialDivision.isAlive()) { trialDivision.interrupt(); } if ((update != null) && update.isAlive()) { update.interrupt(); } } /** * This method is invoked by the {@link LucasLehmer#notifyState(int, * java.math.BigInteger) LucasLehmer.notifyState(int, BigInteger)} method * after each iteration of a Lucas-Lehmer test. Periodically (every 10,000 * iterations, by default), the history displayed by the applet is updated * with the specified information. Also, if sufficient time (10 minutes, by * default) has elapsed since the last time the status of the test was sent * to the task distribution server, an update is sent via XML-RPC. * * @param seed <code>int</code> seed prime. * @param iterations <code>int</code> current iteration count. * @param residue <code>BigInteger</code> current value in the * sequence produced by the Lucas-Lehmer test. */ public void iterationPerformed(final int seed, final int iterations, final BigInteger residue) { if ((iterations % historyIterations) == 0) { historyField.append(String.format( LUCAS_LEHMER_STATUS_HISTORY_PATTERN, new Date(), seed, iterations, formatResidue(residue))); scrollHistoryToEnd(); } if ((iterations < seed - 2) && ((new Date().getTime() - lastUpdate) > updateThreshold)) { if ((update != null) && update.isAlive()) { update.interrupt(); } update = new Thread() { public void run() { Object[] params = new Object[] {seed, iterations, residue.toByteArray(), jobKey}; String saveTask = taskField.getText(); taskField.setText(SENDING_PARTIAL_RESULTS_STATUS); try { client.execute(LUCAS_LEHMER_STATUS_METHOD, params); } catch (XmlRpcClientException e) { // Connection with the server failed. e.printStackTrace(); // TODO - Determine and implement appropriate action, // if different from a simple retry. } catch (XmlRpcException e) { // Server processing error occured. e.printStackTrace(); // TODO - Determine and implement appropriate action, // if different from a simple retry. } catch (Exception e) { // Some other error occurred. e.printStackTrace(); // TODO - Determine and implement appropriate action, // if different from a simple retry. } taskField.setText(saveTask); } }; update.start(); lastUpdate = new Date().getTime(); } } /** * This method is invoked by the {@link LucasLehmer#notifyPrime(boolean) * LucasLehmer.notifyPrime(boolean)} method on completion of a Lucas-Lehmer * test. This method passes the result of the test to the task distribution * server, and invokes the {@link #next() next()} method to request a new * assignment. * * @param seed <code>int</code> seed prime. * @param isPrime <code>boolean</code> result, where * <code>true</code> means that Mersenne number is * prime, and <code>false</code> means it is * composite. */ public void testComplete(int seed, boolean isPrime) { Object[] params = new Object[] {seed, isPrime, jobKey}; boolean retry = true; taskField.setText(SENDING_RESULTS_STATUS); historyField.append(String.format(LUCAS_LEHMER_RESULT_HISTORY_PATTERN, new Date(), seed, isPrime ? LUCAS_LEHMER_RESULT_TRUE_STRING : LUCAS_LEHMER_RESULT_FALSE_STRING)); scrollHistoryToEnd(); while (retry) { // TODO - Should there be a maximum # of retries? try { Object result = client.execute(LUCAS_LEHMER_RESULT_METHOD, params); // TODO - Should result be checked? retry = false; } catch (XmlRpcClientException e) { // Connection with the server failed. e.printStackTrace(); } catch (XmlRpcException e) { // Server processing error occured. e.printStackTrace(); // TODO - Determine and implement appropriate action. } catch (Exception e) { // Some other error occurred. e.printStackTrace(); // TODO - Determine and implement appropriate action. } } next(); } /** * This method is invoked by the {@link Sieve#notify(java.util.BitSet) * Sieve.notify(BitSet)} method on completion of the Sieve of Eratosthenes * on the specified range of numbers. The set of primes found is sent by * this method to the task distribution server as a set of bit flags in a * <code>byte[]</code>. Then, the {@link #next() next()} method is invoked * to request a new assignment. * * @param lower <code>int</code> lower bound (inclusive) of the * sieved range of numbers. * @param upper <code>int</code> upper bound (exclusive) of the * sieved range of numbers. * @param primes <code>BitSet</code> containing all the primes * found in the specified range. */ public void sieveComplete(int lower, int upper, BitSet primes) { Object[] params = new Object[] {lower, upper, Utility.bitSetToByteArray(primes), jobKey}; boolean retry = true; taskField.setText(SENDING_RESULTS_STATUS); historyField.append(String.format(SIEVE_RESULT_HISTORY_PATTERN, new Date(), lower, upper - 1, primes.cardinality(), Utility.bitSetToString(primes, lower, 10))); scrollHistoryToEnd(); while (retry) { // TODO - Should there be a maximum # of retries? try { Object result = client.execute(SIEVE_RESULT_METHOD, params); // TODO - Should result be checked? retry = false; } catch (XmlRpcClientException e) { // Connection with the server failed. e.printStackTrace(); } catch (XmlRpcException e) { // Server processing error occured. e.printStackTrace(); // TODO - Determine and implement appropriate action. } catch (Exception e) { // Some other error occurred. e.printStackTrace(); // TODO - Determine and implement appropriate action. } } next(); } /** * This method is invoked by the {@link TrialDivision#notify(boolean) * TrialDivision.notify(boolean)} method on completion of trial division on * a Mersenne number. This method passes the result of the test to the task * distribution server, and invokes the {@link #next() next()} method to * request a new assignment. * * @param seed <code>int</code> seed prime. * @param mayBePrime <code>boolean</code> result, where * <code>true</code> means that Mersenne number * might be prime, and <code>false</code> means it * is definitely composite. */ public void trialDivisionComplete(int seed, boolean mayBePrime) { Object[] params = new Object[] {seed, mayBePrime, jobKey}; boolean retry = true; taskField.setText(SENDING_RESULTS_STATUS); historyField.append(String.format(TRIAL_DIVISION_RESULT_HISTORY_PATTERN, new Date(), seed, mayBePrime ? TRIAL_DIVISION_RESULT_TRUE_STRING : TRIAL_DIVISION_RESULT_FALSE_STRING)); this.scrollHistoryToEnd(); while (retry) { // TODO - Should there be a maximum # of retries? try { Object result = client.execute(TRIAL_DIVISION_RESULT_METHOD, params); // TODO - Should result be checked? retry = false; } catch (XmlRpcClientException e) { // Connection with the server failed. e.printStackTrace(); } catch (XmlRpcException e) { // Server processing error occured. e.printStackTrace(); // TODO - Determine and implement appropriate action. } catch (Exception e) { // Some other error occurred. e.printStackTrace(); // TODO - Determine and implement appropriate action. } } next(); } private void readAppletParameters() { try { pollInterval = Long.valueOf(getParameter(POLL_INTERVAL_PARAM)); } catch (Exception e) { pollInterval = DEFAULT_POLL_INTERVAL; } try { updateThreshold = Long.valueOf(getParameter(UPDATE_THRESHOLD_PARAM)); } catch (Exception e) { updateThreshold = DEFAULT_UPDATE_THRESHOLD; } try { historyIterations = Integer.valueOf(getParameter(HISTORY_ITERATIONS_PARAM)); } catch (Exception e) { historyIterations = DEFAULT_HISTORY_ITERATIONS; } serviceUrl = getParameter(SERVICE_URL_PARAM); if (serviceUrl == null) { serviceUrl = DEFAULT_SERVICE_URL; } try { serverTimeout = Integer.valueOf(getParameter(SERVER_TIMEOUT_PARAM)); } catch (Exception e) { serverTimeout = DEFAULT_SERVER_TIMEOUT; } } private String formatResidue(BigInteger value) { String displayValue = ""; if (value.bitLength() > 50) { int digits = 0; displayValue = value.toString(); digits = displayValue.length(); displayValue = String.format( CONDENSED_RESIDUE_PATTERN, displayValue.substring(0, 6), displayValue.substring(digits - 6), digits); } else { displayValue = value.toString(); } return displayValue; } private void scrollHistoryToEnd() { historyField.setCaretPosition(historyField.getDocument().getLength()); } @SuppressWarnings("unchecked") private void initComponents() { taskLabel = new javax.swing.JLabel(); historyLabel = new javax.swing.JLabel(); jScrollPane1 = new javax.swing.JScrollPane(); historyField = new javax.swing.JTextArea(); taskField = new javax.swing.JTextField(); taskLabel.setText("Current Task"); historyLabel.setText("History"); historyField.setColumns(20); historyField.setEditable(false); historyField.setRows(5); jScrollPane1.setViewportView(historyField); taskField.setEditable(false); taskField.setText("(none)"); taskField.setFocusable(false); org.jdesktop.layout.GroupLayout layout = new org.jdesktop.layout.GroupLayout(getContentPane()); getContentPane().setLayout(layout); layout.setHorizontalGroup( layout.createParallelGroup( org.jdesktop.layout.GroupLayout.LEADING) .add(org.jdesktop.layout.GroupLayout.TRAILING, layout.createSequentialGroup() .addContainerGap() .add(layout.createParallelGroup( org.jdesktop.layout.GroupLayout.TRAILING) .add(org.jdesktop.layout.GroupLayout.LEADING, jScrollPane1, org.jdesktop.layout.GroupLayout.DEFAULT_SIZE, 430, Short.MAX_VALUE) .add(org.jdesktop.layout.GroupLayout.LEADING, layout.createSequentialGroup() .add(taskLabel) .addPreferredGap(org.jdesktop.layout.LayoutStyle.RELATED) .add(taskField, org.jdesktop.layout.GroupLayout.DEFAULT_SIZE, 364, Short.MAX_VALUE)) .add(org.jdesktop.layout.GroupLayout.LEADING, historyLabel)) .addContainerGap()) ); layout.setVerticalGroup( layout.createParallelGroup(org.jdesktop.layout.GroupLayout.LEADING) .add(layout.createSequentialGroup() .addContainerGap() .add(layout.createParallelGroup( org.jdesktop.layout.GroupLayout.BASELINE) .add(taskLabel) .add(taskField, org.jdesktop.layout.GroupLayout.PREFERRED_SIZE, org.jdesktop.layout.GroupLayout.DEFAULT_SIZE, org.jdesktop.layout.GroupLayout.PREFERRED_SIZE)) .add(18, 18, 18) .add(historyLabel) .addPreferredGap(org.jdesktop.layout.LayoutStyle.RELATED) .add(jScrollPane1, org.jdesktop.layout.GroupLayout.DEFAULT_SIZE, 183, Short.MAX_VALUE) .addContainerGap()) ); } // Variables declaration - do not modify//GEN-BEGIN:variables private javax.swing.JTextArea historyField; private javax.swing.JLabel historyLabel; private javax.swing.JScrollPane jScrollPane1; private javax.swing.JTextField taskField; private javax.swing.JLabel taskLabel; // End of variables declaration//GEN-END:variables }
LucasLehmer.java
package org.projectguts.gutsxl.distrib; import java.math.BigInteger; import static java.math.BigInteger.ONE; import static java.math.BigInteger.ZERO; import java.util.LinkedList; /** * <p>The <code>LucasLehmer</code> class extends {@link java.lang.Thread * Thread}, overriding the {@link java.lang.Thread#run() run()} method to * implement the Lucas-Lehmer test of primality for Mersenne numbers.</p> * * @author Translated to Java by Nick Bennett, from Python code by Max Bond and * Nick Bennett. * @version 1.0.0412 */ public class LucasLehmer extends Thread { /** Initial value for a Lucas-Lehmer test. */ public static final BigInteger DEFAULT_INITIAL_RESIDUE = BigInteger.valueOf(4); private static final BigInteger TWO = BigInteger.valueOf(2); private int seedPrime; private int initialIterations; private BigInteger initialResidue; private BigInteger mersenneNumber; private LinkedList<Listener> listeners; /** * Creates an instance of the <code>LucasLehmer</code> class, using the * specified seed value. This constructor is used when the Lucas-Lehmer test * is to be performed from the start, rather than being resumed from a * previous, incomplete run. * * @param seedPrime <code>int</code> exponent of the Mersenne number * to be tested. */ public LucasLehmer(int seedPrime) { this(seedPrime, 0, DEFAULT_INITIAL_RESIDUE); } /** * Creates an instance of the <code>LucasLehmer</code> class, using the * specified seed value and starting conditions. This constructor is used * when the Lucas-Lehmer test is being resumed from a previous task that * didn't finish processing. * * @param seedPrime <code>int</code> exponent of the Mersenne number * to be tested. * @param initialIterations <code>int</code> starting point for resuming the * Lucas-Lehmer test. * @param initialResidue {@link java.math.BigInteger BigInteger} starting * value of the sequence produced by the * Lucas-Lehmer test. */ public LucasLehmer(int seedPrime, int initialIterations, BigInteger initialResidue) { this.seedPrime = seedPrime; this.initialIterations = initialIterations; this.initialResidue = initialResidue; mersenneNumber = ONE.shiftLeft(seedPrime).subtract(ONE); listeners = new LinkedList<Listener>(); } /** * Calls the {@link #process() process()} method to perform the Lucas-Lehmer * test. This method is called automatically by the {@link * java.lang.Thread#start() Thread.start()} method, and runs in a separate * thread from that of the caller of <code>start()</code>. */ @Override public void run() { process(); } /** * Returns the seed prime of the Mersenne number to be tested. * * @return <code>int</code> seed prime. */ protected int getSeedPrime() { return seedPrime; } /** * Returns the iteration count on which the Lucas-Lehmer test is being * resumed, or 0 if the test isn't being renewed, but is instead being * performed from the start. * * @return <code>int</code> starting iteration count. */ protected int getInitialIterations() { return initialIterations; } /** * Returns the in-process residue value with which the Lucas-Lehmer test is * being resumed, or {@link #DEFAULT_INITIAL_RESIDUE * DEFAULT_INITIAL_RESIDUE} if the test isn't being renewed, but is instead * being performed from the start. * * @return <code>BigInteger</code> starting value in the * sequence that produces the Lucas-Lehmer residue. */ protected BigInteger getInitialResidue() { return initialResidue; } /** * Returns the Mersenne number to be tested, computed as <span class="math"> * <span class="variable">M<sub>seed prime</sub></span> = 2<sup * class="variable">seed prime</sup> - 1</span>. * * @return {@link java.math.BigInteger BigInteger} Mersenne * number. */ protected BigInteger getMersenneNumber() { return mersenneNumber; } /** * Notifies all registered {@link Listener LucasLehmer.Listener}s of the * current state of the Lucas-Lehmer test. * * @param iterations <code>int</code> current iteration count. * @param residue {@link java.math.BigInteger BigInteger} * in-process residue value. */ protected void notifyState(int iterations, BigInteger residue) { int seed = getSeedPrime(); for (Listener listener : listeners) { listener.iterationPerformed(seed, iterations, residue); } } /** * Notifies all registered {@link Listener LucasLehmer.Listener}s of the * result of the Lucas-Lehmer test. * * @param isPrime <code>boolean</code> value, where * <code>true</code> indicates that the Mersenne * number being tested is prime. */ protected void notifyPrime(boolean isPrime) { int seed = getSeedPrime(); for (Listener listener : listeners) { listener.testComplete(seed, isPrime); } } /** * <p>Performs the Lucas-Lehmer test for primality on the Mersenne number * <span class="variable">M<sub>p</sub></span>. * This test consists of generating the sequence * <span class="variable">s</span>, as follows:</p> * <blockquote class="formula"> * <span class="variable">s</span><sub>0</sub> = 4<br /> * <span class="variable">s<sub>n</sub></span> = * [(<span class="variable">s</span><sub><span * class="variable">n</span>-1</sub>)<sup>2</sup> - 2] mod <span * class="variable">M<sub>p</sub></span>, for <span * class="variable">n</span> = 1, 2, …, <span * class="variable">p</span> - 2 * </blockquote> * <p>Where:</p> * <blockquote class="formula"> * <span class="variable">p</span> = seed prime<br /> * <span class="variable">M<sub>p</sub></span> = 2<sup * class="variable">p</sup> - 1 * </blockquote> * <p>The final value of the sequence, * <span class="variable">s</span><sub><span * class="variable">p</span>-2</sub>, is called the <i>Lucas-Lehmer * residue</i>. (In this documentation, the preceding values in the sequence * are referred to as the <i>in-process residue</i>; this usage isn't * technically correct, but the descriptive value outweighs this relatively * minor – and deliberate – error.) If * <span class="variable">s</span><sub><span * class="variable">p</span>-2</sub> = 0, then <span * class="variable">M<sub>p</sub></span> is prime; otherwise, <span * class="variable">M<sub>p</sub></span> is composite. */ protected void process() { int seed = getSeedPrime(); BigInteger residue = getInitialResidue(); BigInteger mersenne = getMersenneNumber(); for (int i = getInitialIterations() + 1; i <= seed - 2; i++) { residue = residue.multiply(residue).subtract(TWO); while (residue.compareTo(mersenne) > 0) { BigInteger rightPart = residue.and(mersenne); BigInteger leftPart = residue.shiftRight(seed); residue = leftPart.add(rightPart); } if (isInterrupted()) { return; } notifyState(i, residue); } notifyPrime((residue.compareTo(mersenne) == 0) || (residue.compareTo(ZERO) == 0)); } /** * Registers a <code>LucasLehmer.Listener</code> that will be notified after * each iteration of the Lucas-Lehmer test, and upon completion of the test. * * @param listener <code>LucasLehmer.Listener</code> to be * notified. */ public void addListener(Listener listener) { listeners.add(listener); } /** * Removes a <code>LucasLehmer.Listener</code> from the notification list. * * @param listener <code>LucasLehmer.Listener</code> to be * removed. */ public void removeListener(Listener listener) { listeners.remove(listener); } /** * The <code>LucasLehmer.Listener</code> interface declares a pair of * methods, which are used to notify concrete implementations of the * progress and result of performing the Lucas-Lehmer test on a Mersenne * number. * * @author Nick Bennett * @version 1.0.0412 */ public static interface Listener { /** * This method is invoked after each iteration of the Lucas-Lehmer test. * Implementations should avoid doing too much processing in the * caller's thread, since the Lucas-Lehmer test blocks on this method. * If some processing is needed which will take a significant amount of * time, it should be performed on another thread. * * @param seed <code>int</code> seed prime. * @param iterations <code>int</code> current iteration count. * @param residue {@link java.math.BigInteger BigInteger} value of * the in-process residue. */ void iterationPerformed(int seed, int iterations, BigInteger residue); /** * This method is invoked on completion of the Lucas-Lehmer test, to * inform the listener of the result. * * @param seed <code>int</code> seed prime. * @param isPrime <code>boolean</code> result of the Lucas-Lehmer * test. A value of <code>true</code> means that * the Mersenne number is prime; <code>false</code> * means that it is composite. */ void testComplete(int seed, boolean isPrime); } }
Sieve.java
package org.projectguts.gutsxl.distrib; import java.util.BitSet; import java.util.LinkedList; /** * <p>The <code>Sieve</code> class extends {@link java.lang.Thread Thread}, * overriding the {@link java.lang.Thread#run() run()} method to implement the * Sieve of Eratosthenes. This implementation includes support for segmented * operation, allowing a large range of numbers to be divided into smaller * segments, which are sieved separately.</p> * * @author Translated to Java by Nick Bennett, from Python code by Max Bond and * Nick Bennett. * @version 1.0.0412 */ public class Sieve extends Thread { /** Lower bound of sieve segment, if none specified. */ public static final int DEFAULT_LOWER_BOUND = 0; private int lower; private int upper; private LinkedList<Listener> listeners; /** * Creates a new instance of <code>Sieve</code>, with the specified upper * bound, and a lower bound of 0. The range of values sieved will be from 0 * (inclusive) to <code>upper</code> (exclusive). * * @param upper <code>int</code> exclusive upper bound of range * to be sieved for primes. */ public Sieve(int upper) { this(DEFAULT_LOWER_BOUND, upper); } /** * Creates a new instance of <code>Sieve</code>, with the specified lower * and upper bounds. The range of values sieved will be from * <code>lower</code> (inclusive) to <code>upper</code> (exclusive). * * @param lower <code>int</code> inclusive lower bound of range * to be sieved for primes. * @param upper <code>int</code> exclusive upper bound of range * to be sieved for primes. */ public Sieve(int lower, int upper) { this.lower = lower; this.upper = upper; listeners = new LinkedList<Listener>(); } /** * Calls the {@link #process() process()} method to perform the sieve. This * method is called automatically by the {@link java.lang.Thread#start() * Thread.start()} method, and runs in a separate thread from that of the * caller of <code>start()</code>. */ @Override public void run() { process(); } /** * Returns the inclusive lower bound of the segment to be sieved. * * @return <code>int</code> inclusive lower bound. */ protected int getLower() { return lower; } /** * Returns the exclusive upper bound of the segment to be sieved. * * @return <code>int</code> exclusive upper bound. */ protected int getUpper() { return upper; } /** * Notifies all registered {@link Listener Sieve.Listener}s that sieve * processing is complete, and pass the set of primes to them. * * @param primes {@link java.util.BitSet BitSet} of flags * giving the prime (<code>true</code>) and * composite (<code>false</code>) status of each * number in the processed range. */ protected void notify(BitSet primes) { for (Listener listener : listeners) { listener.sieveComplete(getLower(), getUpper(), primes); } } /** * <p>Enumerates the prime numbers in the range specified in the constructor * call, using the Sieve of Eratosthenes.</p> * <p>With a lower bound of 0, the sieve is executed in the traditional * manner:</p> * <ol> * <li>Create an ordered list of consecutive integers, from 2 (inclusive) to * <span class="formula variable">u</span> (exclusive).</li> * <li>Set <span class="formula variable">p</span>, the sieving prime, to * the first number in the list (2).</li> * <li>Remove all integral multiples of * <span class="formula variable">p</span> from the list, starting with * <span class="formula"><span class="variable">p</span><sup>2</sup></span>. * </li> * <li>If any number greater than <span class="formula variable">p</span> * and less than or equal to * <span class="formula">⌊√<span * class="variable">(u - 1)</span>⌋ remains in the list, set <span * class="formula variable">p</span> to the lowest such value, and return to * step #3; otherwise, proceed to step #5.</li> * <li>All numbers still in the list are prime.</li> * </ol> * <p>If the range to be sieved doesn't start at 0, 1, or 2, the classical * sieve is modified slightly, starting with the creation of two segments: * one ranging from 0 to * <span class="formula">⌊√<span * class="variable">(u - 1)</span>⌋</span> (inclusive); and a second, * from <span class="formula variable">l</span> (inclusive) to * <span class="formula variable">u</span> (exclusive), where * <span class="formula variable">l</span> and * <span class="formula variable">u</span> are the lower and upper bounds, * respectively, specified in the constructor call. The lower segment is * then sieved in the normal fashion, to enumerate a set of primes; these * primes are then used to sieve the upper segment.</p> */ protected void process() { BitSet result; int lowerBound = getLower(); int upperBound = getUpper(); int root = (int) Math.floor(Math.sqrt(upperBound - 1)); if (root < lowerBound - 1) { int segmentSize = upperBound - lowerBound; BitSet baseFlags = new BitSet(root + 1); BitSet segmentFlags = new BitSet(segmentSize); baseFlags.set(2, root + 1); segmentFlags.set(0, segmentSize); for (int sievePrime = 2; (sievePrime <= root) && (sievePrime != -1); sievePrime = baseFlags.nextSetBit(sievePrime + 1)) { int sieveStart = sievePrime * sievePrime; for (int multiple = sieveStart; multiple <= root; multiple += sievePrime) { baseFlags.clear(multiple); } sieveStart = Math.max(sieveStart, sievePrime * (int) Math.ceil(1.0 * lowerBound / sievePrime)); for (int multiple = sieveStart; multiple < upperBound; multiple += sievePrime) { segmentFlags.clear(multiple - lowerBound); } } result = segmentFlags; } else { BitSet flags = new BitSet(upperBound); flags.set(2, upperBound); for (int sievePrime = 2; (sievePrime <= root) && (sievePrime != -1); sievePrime = flags.nextSetBit(sievePrime + 1)) { for (int multiple = sievePrime * sievePrime; multiple < upperBound; multiple += sievePrime) { flags.clear(multiple); } } result = (lowerBound > 0) ? flags.get(lowerBound, upperBound) : flags; } notify(result); } /** * Registers a <code>Sieve.Listener</code> that will be notified on * completion of sieve processing. * * @param listener <code>Sieve.Listener</code> to be notified. */ public void addListener(Listener listener) { listeners.add(listener); } /** * Removes a <code>Sieve.Listener</code> from the notification list. * * @param listener <code>Sieve.Listener</code> to be removed. */ public void removeListener(Listener listener) { listeners.remove(listener); } /** * The <code>Sieve.Listener</code> interface declares a {@link * Listener#sieveComplete sieveComplete} method, which is used to pass to * listeners the set of primes found by the sieve. * * @author Nick Bennett * @version 1.0.0412 */ public static interface Listener { /** * This method is invoked on completion of the sieve processing, to pass * the set of primes found to the <code>Sieve.Listener</code> * implementation. * * @param lower <code>int</code> inclusive lower bound of the * segment sieved. * @param upper <code>int</code> exclusive upper bound of the * segment sieved. * @param primes {@link java.util.BitSet BitSet} of flags giving * the prime (<code>true</code>) and composite * (<code>false</code>) status of each number in * the segment. */ void sieveComplete(int lower, int upper, BitSet primes); } }
TrialDivision.java
package org.projectguts.gutsxl.distrib; import java.math.BigInteger; import java.util.BitSet; import static java.math.BigInteger.ONE; import static java.math.BigInteger.ZERO; import static java.math.BigInteger.valueOf; import java.util.LinkedList; /** * <p>The <code>TrialDivision</code> class extends {@link java.lang.Thread * Thread}, overriding the {@link java.lang.Thread#run() run()} method to * implement trial division of Mersenne numbers with prime exponents. * If trial division succeed (i.e. the Mersenne number is evenly divisible by * one of the trial divisors), then the Mersenne number is composite, and there * is no need to test it with the Lucas-Lehmer test for primality. If trial * division fails, it doesn't necessarily mean that the Mersenne number is prime * (trial division is by no means exhaustive), but only that further testing * – using the Lucas-Lehmer test – is required.</p> * * @author Translated to Java by Nick Bennett, from Python code by Max Bond and * Nick Bennett. * @version 1.0.0412 */ public class TrialDivision extends Thread { private static final double SQRT2 = Math.sqrt(2); private static final int[] WHEEL_PRIMES = new int[] {2, 3, 5, 7, 11, 13}; private static BitSet wheel; private static int wheelModulus; private int seedPrime; private BigInteger mersenneNumber; private LinkedList<Listener> listeners; static { wheelModulus = 1; for (int i = 0; i < WHEEL_PRIMES.length; i++) { wheelModulus *= WHEEL_PRIMES[i]; } wheel = new BitSet(wheelModulus); wheel.set(1, wheelModulus); for (int i = 0; i < WHEEL_PRIMES.length; i++) { int prime = WHEEL_PRIMES[i]; for (int j = prime; j < wheel.size(); j += (prime << 1)) { wheel.clear(j); } } } /** * Creates a new instance of <code>TrialDivision</code> for the Mersenne * number computed from the specified seed prime. * * @param seedPrime */ public TrialDivision(int seedPrime) { this.seedPrime = seedPrime; mersenneNumber = ONE.shiftLeft(seedPrime).subtract(ONE); listeners = new LinkedList<Listener>(); } /** * Calls the {@link #process() process()} method to perform trial division. * This method is called automatically by the {@link * java.lang.Thread#start() Thread.start()} method, and runs in a separate * thread from that of the caller of <code>start()</code>. */ @Override public void run() { process(); } /** * Returns the seed prime of the Mersenne number to be tested. * * @return <code>int</code> seed prime. */ protected int getSeedPrime() { return seedPrime; } /** * Returns the Mersenne number to be tested, computed as <span class="math"> * <span class="variable">M<sub>seed prime</sub></span> = 2<sup * class="variable">seed prime</sup> - 1</span>. * * @return {@link java.math.BigInteger BigInteger} Mersenne * number. */ protected BigInteger getMersenneNumber() { return mersenneNumber; } /** * Notifies all registered {@link Listener TrialDivision.Listener}s that * trial division is complete, with the specified result. * * @param mayBePrime <code>boolean</code> result – where * <code>false</code> indicates that the Mersenne * number was evenly divisible by one of the trial * divisors, and is thus composite, and * <code>true</code> means that further testing * (by the Lucas-Lehmer test) is required. */ protected void notify(boolean mayBePrime) { int seed = getSeedPrime(); for (Listener listener : listeners) { listener.trialDivisionComplete(seed, mayBePrime); } } /** * */ protected void process() { boolean mayBePrime = true; int seed = getSeedPrime(); long doubleSeed = (long) seed << 1; long sextupleSeed = 3 * doubleSeed; BigInteger mersenne = getMersenneNumber(); long divisor; int doubleRemainder = (int) (doubleSeed % wheelModulus); int sextupleRemainder = (3 * doubleRemainder) % wheelModulus; int remainder; boolean shortJump; long divisorLimit = (seed > 126) ? 0 : (long) Math.floor(Math.pow(SQRT2, seed)); if ((seed & 2) != 0) { divisor = doubleSeed + 1; remainder = doubleRemainder + 1; shortJump = false; } else { divisor = sextupleSeed + 1; remainder = sextupleRemainder + 1; shortJump = true; } for (int i = 0; (i < seed) && ((divisorLimit == 0) || (divisor <= divisorLimit)); ) { if (wheel.get(remainder)) { if (mersenne.mod(valueOf(divisor)).compareTo(ZERO) == 0) { mayBePrime = false; break; } i++; } if (shortJump) { divisor += doubleSeed; remainder += doubleRemainder; } else { divisor += sextupleSeed; remainder += sextupleRemainder; } remainder %= wheelModulus; shortJump = !shortJump; } notify(mayBePrime); } /** * Registers a <code>TrialDivision.Listener</code> that will be notified on * completion of trial division. * * @param listener <code>TrialDivision.Listener</code> to be * notified. */ public void addListener(Listener listener) { listeners.add(listener); } /** * Removes a <code>TrialDivision.Listener</code> from the notification list. * * @param listener <code>TrialDivision.Listener</code> to be * removed. */ public void removeListener(Listener listener) { listeners.remove(listener); } /** * The <code>TrialDivision.Listener</code> interface declares a {@link * Listener#trialDivisionComplete trialDivisionComplete} method, which is * used to notify listeners of the trial division's outcome. * * @author Nick Bennett * @version 1.0.0412 */ public static interface Listener { /** * This method is invoked on completion of trial division, to inform * concrete implementations of <code>TrialDivision.Listener</code> of * the trial division's outcome. * * @param seed <code>int</code> seed prime. * @param mayBePrime <code>boolean</code> result, indicating whether * the Mersenne number might be prime * (<code>true</code>), or is definitely composite * (<code>false</code>). */ void trialDivisionComplete(int seed, boolean mayBePrime); } }
Utility.java
package org.projectguts.gutsxl.distrib; import java.util.BitSet; /** * This class implements a set of static utility methods for handling {@link * java.util.BitSet BitSet} instances. More specifically, these methods convert * a <code>BitSet</code> to a <code>byte</code> array or <code>String</code>. * * @author Nick Bennett * @version 1.0.0412 */ public class Utility { private static final String LEFT_BRACE = "{"; private static final String RIGHT_BRACE = "}"; private static final String DELIMITER = ", "; private static final String CONTINUATION = ", ..."; /** * <p>Converts all of the members of a <code>BitSet</code> to a * <code>byte[]</code> and returns the result.</p> * <p>See {@link #bitSetToByteArray(java.util.BitSet, int, int) * bitSetToByteArray(BitSet, int, int)} for details.</p> * * @param bits <code>BitSet</code> to be converted. * @return <code>byte[]</code> with bits set corresponding * to the members of <code>bits</code>. */ public static byte[] bitSetToByteArray(BitSet bits) { return bitSetToByteArray(bits, 0); } /** * <p>Converts the members of a <code>BitSet</code>, starting at a given * position, to a <code>byte[]</code> and returns the result.</p> * <p>See {@link #bitSetToByteArray(java.util.BitSet, int, int) * bitSetToByteArray(BitSet, int, int)} for details.</p> * * @param bits <code>BitSet</code> to be converted. * @param start <code>int</code> lowest member index to be * included in the result. * @return <code>byte[]</code> with bits set corresponding * to the members of <code>bits</code>. */ public static byte[] bitSetToByteArray(BitSet bits, int start) { return bitSetToByteArray(bits, start, bits.length()); } /** * <p>Converts the members of a <code>BitSet</code>, starting and ending at * specified positions, to a <code>byte[]</code> and returns the result. * Each included member of the set is represented by the appropriate bit * turned on (i.e. with a value of 1) in the appropriate element of the * destination array. The <code>BitSet</code> members are stored into the * destination in big-endian format – i.e. the highest-ordered members * are stored in the lowest-ordered bytes of the array.</p> * <p>Besides other possible uses, the value returned can easily be * converted to base64, and sent via HTTP. For example, a * <code>byte[]</code> can be passed directly to the relevent Apache XML-RPC * methods, and sent as part of an XML-RPC request or response.</p> * * @param bits <code>BitSet</code> to be converted. * @param start <code>int</code> lowest member index to be * included in the result. * @param end <code>int</code> upper bound (exclusive) of * member indices to be included in the result. * @return <code>byte[]</code> with bits set corresponding * to the members of <code>bits</code>. */ public static byte[] bitSetToByteArray(BitSet bits, int start, int end) { int setSize = end - start; int arraySize = 1 + setSize / 8; byte[] bytes = new byte[arraySize]; for (int i = bits.nextSetBit(start); (i < end) && (i != -1); i = bits.nextSetBit(i + 1)) { int index = i - start; bytes[arraySize - (index / 8) - 1] |= (1 << (index % 8)); } return bytes; } /** * Returns a <code>String</code> representation of a <code>BitSet</code>. * This is similar to the function of the {@link java.util.BitSet#toString() * BitSet.toString()} method, but it adds the capability to specify an * offset value for the <code>String</code> representation. In other words, * whereas a member at index 0 of the <code>BitSet</code> will appear as "0" * in the representation produced by <code>BitSet.toString()</code>, it will * be represented by this method as * "<code style='font-style: italic;'>offset</code>"; successive members of * the <code>BitSet</code> will be similarly offset. * * @param bits <code>BitSet</code> to be converted. * @param offset <code>int</code> value to be added to each * set member's position, in the * <code>String</code> representation. * @return <code>String</code> representation of the * <code>BitSet</code>. */ public static String bitSetToString(BitSet bits, int offset) { return bitSetToString(bits, offset, 0); } /** * <p>Returns a <code>String</code> representation of a <code>BitSet</code>, * truncated after the specified number of set members.</p> * <p>See {@link #bitSetToString(java.util.BitSet, int) * bitSetToString(BitSet, int)} for more details on the representation * produced, and how it differs from that produced by the {@link * java.util.BitSet#toString() BitSet.toString()} method.</p> * * @param bits <code>BitSet</code> to be converted. * @param offset <code>int</code> value to be added to each * set member's position, in the * <code>String</code> representation. * @param truncation <code>int</code> maximum number of set members * to be included in the <code>String</code> * representation of the <code>BitSet</code>. * @return <code>String</code> representation of the * <code>BitSet</code>. */ public static String bitSetToString(BitSet bits, int offset, int truncation) { String result = ""; if ((offset == 0) && (truncation == 0)) { result = bits.toString(); } else { boolean firstItem = true; StringBuilder buffer = new StringBuilder(LEFT_BRACE); int count = 0; for (int i = bits.nextSetBit(0); i != -1; i = bits.nextSetBit(i + 1)) { if (!firstItem) { buffer.append(DELIMITER); } else { firstItem = false; } buffer.append(Integer.toString(i + offset)); count++; if ((truncation > 0) && (count >= truncation)) { buffer.append(CONTINUATION); break; } } buffer.append(RIGHT_BRACE); result = buffer.toString(); } return result; } }