I am working on some multi-threaded code that requires a prime-number source.
The following code keeps an array of primes in memory, extending it as needed. It works in the 'int' domain, being careful to avoid overflows, and to keep the memory for storing the data relatively small.
it uses a state-based concurrency model... it keeps an immutable state that covers a range of primes (from 1..range). If a request is for some data that is outside that range, it will defer to a backup process which is single-threaded, where one thread extends the state. At any time, some other thread can query the state, and it is not blocked if the existing state covers its needs.
The idea is that only one thread is working at a time on calculating primes, and any pre-calculated primes are reused by other threads.
Additionally, during prime calculation, if one thread is calculating a really large extension, it regularly creates a new state, then 'breaks' out of the locked code, and allows any other waiting threads to use that new state if it is good enough.... The long-calculating thread will then start again on the next extension.
PrimeReserveInt.java
import java.util.Arrays;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicReference;
/**
* A thread-safe container that stores a list of prime numbers. The prime number
* list will be extended if needed to satisfy any request for primes up to
* MAX_PRIME_ALLOWED (Integer.MAX_VALUE). This is the 105097565th prime number
* (MAX_PRIME_NTH). Int primes require 4 bytes per number, or just less than
* 400MB to contain. Because of the way this code works, it occasionally needs
* to have two copies of the data in memory at a time, which leads to an
* occasional need for up to 1GB to do the work. Use -Xmx2g to get up these
* limits.
*
* Many sieve implementations would require an array of 2 Billion int values
* (8GB) to calculate this 100Millionth prime, so, in reality, this is a small
* implementation...
*
* @author rolf
*
*/
public final class PrimeReserveInt {
/**
* The largest prime this Reserve can contain. This also happens to be
* Integer.MAX_VALUE (which is prime).
*/
public static final int MAX_PRIME_ALLOWED = Integer.MAX_VALUE;
/**
* The largest nth' prime that can be managed (MAX_PRIME_ALLOWED is the
* MAX_PRIME_NTH prime number).
*/
public static final int MAX_PRIME_NTH = 105097565;
/**
* This is the most primes we will calculate in one locked operation.
*
* NEVER Violate the prime directive!
*/
private static final int PRIME_DIRECTIVE = 8 * 1024 * 1024;
/**
* As prime numbers are calculated, they will extend this far beyond the
* requested calc. This is a performance optimization so that when a user is
* incrementing through the primes, they do not have to do a full calc for
* each value....
*/
private static final int PRIME_STEP = 1024;
/**
* Internal state class. This class contains immutable values, and thus is
* thread-safe. The class model is that it creates various
*/
private static final class PrimeState {
private final int[] primes;
private final int limit;
// replaced is an indicator of whether this state is the currently
// active one.
private boolean replaced = false;
public PrimeState(int[] primes) {
if (primes.length == 0) {
throw new IllegalStateException("Cannot have empty prime state");
}
this.primes = primes;
this.limit = primes[primes.length - 1];
}
/**
* get a copy of all prime numbers less than or equal to the input range
*
* @param range
* the largest prime value to return.
* @return an ordered array of primes less than or equal to the range.
*/
public int[] getPrimesTo(final int range) {
if (range > limit) {
throw new IllegalArgumentException(
"This state only has values up to " + limit
+ " so cannot process range " + range);
}
// find the position of the prime after `range`
int pos = Arrays.binarySearch(primes, range);
if (pos < 0) {
pos = -pos - 1;
} else {
pos++;
}
return Arrays.copyOf(primes, pos);
}
/**
* get the nth prime number from this state.
*
* @param nth
* the prime number to retrieve
* @return the nth prime number.
*/
public int getNthPrime(final int nth) {
if (nth < 1 || nth > primes.length) {
throw new IllegalArgumentException("This state only has "
+ primes.length
+ " values, so cannot access nth prime " + nth);
}
return primes[nth - 1];
}
/**
* indicates whether this state includes the specified range
*
* @param range
* the value to check whether it is included.
* @return true if the range is within this state.
*/
public boolean coversRange(final int range) {
return range <= limit;
}
/**
* indicate whether this state contains the nth prime
*
* @param nth
* the prime to check for
* @return true if it is contained within this state.
*/
public boolean containsPrime(final int nth) {
return nth <= primes.length;
}
/**
* indicate how many primes are in this state
*
* @return the number of primes in this state.
*/
public int getPrimeCount() {
return primes.length;
}
/**
* the largest prime covered by this state.
*
* @return the largest in-state prime.
*/
public int getLargestPrime() {
return limit;
}
/**
* identify the 'nth' value for a prime number.
*
* @param prime
* the prime to get the nth for.
* @return the nth value of the prime (0 if the input is not prime).
*/
public int whichPrime(final int prime) {
int pos = Arrays.binarySearch(primes, prime);
return pos >= 0 ? (pos + 1) : 0;
}
/**
* get the largest prime less than or equal to the input.
*
* @param to
* the value to get the previous prime from.
* @return the largest prime <= to.
*/
public int getLargestPrimeTo(final int to) {
int pos = Arrays.binarySearch(primes, to);
if (pos >= 0) {
return primes[pos];
}
pos = (-pos - 1);
return primes[pos - 1];
}
private synchronized void waitReplaced() {
while (!replaced) {
try {
// wait up to a second....
this.wait(1000);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
private synchronized void replaced() {
replaced = true;
this.notifyAll();
}
}
/**
* Seed the initial state with the first 6 primes.
*/
private final AtomicReference<PrimeState> safestate = new AtomicReference<>(
new PrimeState(new int[] { 2, 3, 5, 7, 11, 13 }));
/**
* If a recalc is needed, this makes sure only one thread is recalcing at a
* time.
*/
private final AtomicBoolean lock = new AtomicBoolean();
/**
* Create a 'strategic reserve' of prime numbers.
*
* This class is fully thread-safe.
*
* If any thread has previously calculated primes that satisfy requests then
* querying those primes is a lock-free process, and O(1).
*
* If the primes you need to query have not been calculated, then only one
* thread calculates those primes, and other threads block until they are
* satisfied, at which point they are released and no longer block.
*/
public PrimeReserveInt() {
// useful to seed the system with the first batch of primes.
getPrimesTo(1000);
}
/**
* Get an array of all primes less-than-or-equals-to the input range.
*
* @param to
* the largest value to return in the results (or smaller if to
* is not prime)
* @return an array of primes less-than-or-equals-to to.
*/
public int[] getPrimesTo(final int to) {
return coverTo(to).getPrimesTo(to);
}
/**
* Get an array of all primes less-than-or-equals-to the input range.
*
* @param to
* the largest value to return in the results (or smaller if to
* is not prime)
* @return an array of primes less-than-or-equals-to to.
*/
public int[] getFirstNPrimes(final int n) {
final int nth = getNthPrime(n);
return coverTo(nth).getPrimesTo(nth);
}
/**
* get the value of the nth prime. The values are 1-based, i.e.
* getNthPrime(1) returns 2.
*
* @param nth
* the prime value to get.
* @return the prime value.
* @throws IllegalArgumentException
* if nth < 1 or the nth prime is larger than Long.MAX_VALUE
*/
public int getNthPrime(final int nth) {
if (nth < 1) {
throw new IllegalArgumentException("Cannot get the " + nth
+ " prime");
}
if (nth > MAX_PRIME_NTH) {
throw new IllegalArgumentException("The " + MAX_PRIME_NTH
+ "th prime is the largest int prime (" + MAX_PRIME_ALLOWED
+ "). Cannot get the " + nth + " prime.");
}
// zero-based nth
// final int zbnth = nth - 1;
PrimeState state = null;
while (!(state = safestate.get()).containsPrime(nth)) {
// guess something that will likely cover the nth prime.
// the following is the approximate number gap between primes.
double distribution = ((double) state.getLargestPrime())
/ state.getPrimeCount();
// need about this many more primes....
int extension = (int) ((nth - state.getPrimeCount()) * distribution);
// overcommit the primes in case there is a system extending things
// beyond.... one-at-a-time
final int current = state.getLargestPrime();
int to = current + extension;
if (to < current) {
// integer overflow.
to = MAX_PRIME_ALLOWED;
}
extendStateTo(state, to); // take it 1024 further just in case.
}
return state.getNthPrime(nth);
}
/**
* Which prime is the supplied value.
*
* @param prime
* the prime value to identify
* @return the position of the prime number, or 0 if the number is not
* prime.
*/
public int whichPrime(final int prime) {
if (prime <= 1 || prime > MAX_PRIME_ALLOWED) {
return 0;
}
return coverTo(prime).whichPrime(prime);
}
/**
* Get the largest prime that is less-than-or-equal to the input value.
*
* @param to
* the value to get the largest prime from.
* @return the largest prime available, or 0 if the input is less than 2.
*/
public int getLargestPrimeTo(int to) {
return to < 2 ? 0 : coverTo(to).getLargestPrimeTo(to);
}
private PrimeState coverTo(final int to) {
if (to <= 1) {
throw new IllegalArgumentException("Illegal range to " + to);
}
if (to > MAX_PRIME_ALLOWED) {
throw new IllegalArgumentException(
"Memory-limited to the largest prime " + MAX_PRIME_ALLOWED
+ " (which is the " + MAX_PRIME_NTH + "th prime)");
}
PrimeState state = null;
while (!(state = safestate.get()).coversRange(to)) {
// the current state is not good enough, extend it.
// over-commit the primes... in case there is a user that is looping
// through
// increasing values.
int realto = to + PRIME_STEP;
if (realto < state.getLargestPrime()) {
// overflow
realto = MAX_PRIME_ALLOWED;
}
extendStateTo(state, realto);
}
return state;
}
private void extendStateTo(final PrimeState estate, final int to) {
if (lock.compareAndSet(false, true)) {
// we are the thread with the lock...
try {
// OK, we are the only thread in here, and the state is not good
// enough...
// create a new state that will be good enough....
PrimeState nextstate = extendStateInternal(estate, to);
if (!safestate.compareAndSet(estate, nextstate)) {
throw new IllegalStateException(
"This can never happen, if it does, then shoot Monkey!");
}
estate.replaced();
} finally {
lock.compareAndSet(true, false);
}
} else {
estate.waitReplaced();
}
}
private PrimeState extendStateInternal(final PrimeState estate, final int to) {
// This method will only be called from a locked context...
// to limit the amount of memory we occupy, we will only process
// primes in a smallish sieve..... (limit to 10million or so entries)
// the way this works is that it creates a sieve that is a 'window' on
// a virtual full-size sieve
// this allows us to work with numbers in the long domain, while staying
// in the int domain.
final int offset = estate.getLargestPrime() + 1;
int longsievesize = (to - offset) + 1;
final int sievesize = longsievesize > PRIME_DIRECTIVE ? (int) PRIME_DIRECTIVE
: (int) longsievesize;
final int tolimit = offset - 1 + sievesize; // need to use tolimit as <=
// hence the -1 in case
// tolimit is
// Intger.MAX_VALUE
boolean[] sieve = new boolean[sievesize];
final int maxp = (int) Math.sqrt(to);
// For the sieve, eliminate all previously calculated primes.
for (int p : estate.primes) {
// optimize -- break at sqrt(to).
if (p > maxp) {
break;
}
// optimize -- start at square value.
int check = p * p;
if (check > 0 && check < offset) {
// the prime square is less than our sieve window. Extend it in
// to the window.
check = p + (((offset - 1) / p) * p);
}
while (check > 0 && check <= tolimit) {
int pos = (int) (check - offset);
// if (to == MAX_PRIME_ALLOWED) {
// System.out.println("In end-range with prime " + p +
// " and check " + check);
// }
sieve[pos] = true;
check += p;
}
}
// now apply all the newly found primes....
int cnt = 0;
for (int i = 0; i < sievesize; i++) {
if (!sieve[i]) {
// found a prime....
cnt++;
int p = offset + i;
// optimize -- break at sqrt(to).
if (p > maxp) {
continue;
}
// optimize -- start at square value.
int check = p * p;
if (check < offset) {
check = p + (((offset - 1) / p) * p);
}
while (check > 0 && check <= tolimit) {
int pos = (int) (check - offset);
// if (to == MAX_PRIME_ALLOWED) {
// System.out.println("In end-range with prime " + p +
// " and check " + check);
// }
sieve[pos] = true;
check += p;
}
}
}
int pos = estate.primes.length;
int[] primes = Arrays.copyOf(estate.primes, pos + cnt);
for (int i = 0; i < sieve.length; i++) {
if (!sieve[i]) {
primes[pos++] = offset + i;
}
}
return new PrimeState(primes);
}
}
PrimeTester.java
(used to test the generator)
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
public class PrimeTester {
// These values extracted from: http://www.primos.mat.br/dados/2T_part11.7z
private static final int[] largeprimes = {
2147459851, 2147459887, 2147459917, 2147459959, 2147459969, 2147459981, 2147459987, 2147459999, 2147460013, 2147460017,
2147460019, 2147460041, 2147460089, 2147460137, 2147460151, 2147460173, 2147460187, 2147460197, 2147460223, 2147460233,
2147460253, 2147460269, 2147460277, 2147460299, 2147460373, 2147460379, 2147460421, 2147460431, 2147460437, 2147460449,
2147460457, 2147460461, 2147460467, 2147460547, 2147460569, 2147460589, 2147460611, 2147460629, 2147460631, 2147460641
};
--TESTER NOTE .... there are other numbers I trimmed out to get this below 30K
private static final void tests(final PrimeReserveInt pr) {
// compare the first million primes with an external reference...
checkMillion(pr);
checkNthPrime(pr, 29, 109);
checkNthPrime(pr, 1229, 9973);
checkNthPrime(pr, 50000, 611953);
checkNthPrime(pr, 100000000, 2038074743);
checkNthPrime(pr, PrimeReserveInt.MAX_PRIME_NTH, PrimeReserveInt.MAX_PRIME_ALLOWED);
int pos = 105096451; // this is verified as: pr.whichPrime(largeprimes[0]);
for (int lp : largeprimes) {
checkNthPrime(pr, pos++, lp);
}
checkPrimeNth(pr, PrimeReserveInt.MAX_PRIME_ALLOWED, PrimeReserveInt.MAX_PRIME_NTH);
checkPrimeNth(pr, -1, 0);
checkPrimeNth(pr, 2147459851, 105096451);
checkPrimeBefore(pr, 2147483646, 2147483629);
checkPrimeBefore(pr, 2147483647, 2147483647);
checkPrimeBefore(pr, 1, 0);
}
public static void main(String[] args) throws InterruptedException {
int cpus = Runtime.getRuntime().availableProcessors();
ExecutorService pool = Executors.newFixedThreadPool(cpus);
final PrimeReserveInt pr = new PrimeReserveInt();
for (int i = cpus; i > 0; i--) {
final Runnable torun = new Runnable() {
@Override
public void run() {
tests(pr);
}
};
pool.execute(torun);
}
pool.shutdown();
while (!pool.isTerminated()) {
System.out.println("Waiting for executorservice...");
pool.awaitTermination(10, TimeUnit.SECONDS);
}
System.out.println("Service complete");
}
private static void checkPrimeBefore(PrimeReserveInt pr, int target,
int expectprime) {
int actual = pr.getLargestPrimeTo(target);
System.out.printf("Prime (which) %d US %d REF %d %s\n", target, actual, expectprime, expectprime == actual ? "OK" : "FAIL!!!");
}
private static void checkPrimeNth(PrimeReserveInt pr, int prime,
int expectnth) {
int actual = pr.whichPrime(prime);
System.out.printf("Prime (which) %d US %d REF %d %s\n", prime, actual, expectnth, expectnth == actual ? "OK" : "FAIL!!!");
}
private static final void checkNthPrime(PrimeReserveInt pr, int nth, int expectprime) {
int actual = pr.getNthPrime(nth);
System.out.printf("Prime (nth) %d US %d REF %d %s\n", nth, actual, expectprime, expectprime == actual ? "OK" : "FAIL!!!");
}
private static void checkMillion(PrimeReserveInt pr) {
// http://primes.utm.edu/lists/small/millions/primes1.zip
PrimeReader reader = new PrimeReader("primes1.txt");
int[] reference = reader.readFile();
int[] actual = pr.getPrimesTo(pr.getNthPrime(1000000));
int ri = 0;
int ai = 0;
while (ri < reference.length && ai < actual.length) {
while (ai < actual.length && ri < reference.length && actual[ai] < reference[ri]) {
System.out.println("Extra value " + ai + " " + actual[ai]);
ai++;
}
while (ai < actual.length && ri < reference.length && actual[ai] > reference[ri]) {
System.out.println("Missing value before " + ai + " (" + ri + " in reference) " + reference[ri]);
ri++;
}
ri++;
ai++;
}
}
}
