Back to index...

	/*
	* Copyright (c) 1999, 2007, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package java.math;

	/**
	* A simple bit sieve used for finding prime number candidates. Allows setting
	* and clearing of bits in a storage array. The size of the sieve is assumed to
	* be constant to reduce overhead. All the bits of a new bitSieve are zero, and
	* bits are removed from it by setting them.
	*
	* To reduce storage space and increase efficiency, no even numbers are
	* represented in the sieve (each bit in the sieve represents an odd number).
	* The relationship between the index of a bit and the number it represents is
	* given by
	* N = offset + (2*index + 1);
	* Where N is the integer represented by a bit in the sieve, offset is some
	* even integer offset indicating where the sieve begins, and index is the
	* index of a bit in the sieve array.
	*
	* @see BigInteger
	* @author Michael McCloskey
	* @since 1.3
	*/
	class BitSieve {
	/**
	* Stores the bits in this bitSieve.
	*/
	private long bits[];

	/**
	* Length is how many bits this sieve holds.
	*/
	private int length;

	/**
	* A small sieve used to filter out multiples of small primes in a search
	* sieve.
	*/
	private static BitSieve smallSieve = new BitSieve();

	/**
	* Construct a "small sieve" with a base of 0. This constructor is
	* used internally to generate the set of "small primes" whose multiples
	* are excluded from sieves generated by the main (package private)
	* constructor, BitSieve(BigInteger base, int searchLen). The length
	* of the sieve generated by this constructor was chosen for performance;
	* it controls a tradeoff between how much time is spent constructing
	* other sieves, and how much time is wasted testing composite candidates
	* for primality. The length was chosen experimentally to yield good
	* performance.
	*/
	private BitSieve() {
	length = 150 * 64;
	bits = new long[(unitIndex(length - 1) + 1)];

	// Mark 1 as composite
	set(0);
	int nextIndex = 1;
	int nextPrime = 3;

	// Find primes and remove their multiples from sieve
	do {
	sieveSingle(length, nextIndex + nextPrime, nextPrime);
	nextIndex = sieveSearch(length, nextIndex + 1);
	nextPrime = 2*nextIndex + 1;
	} while((nextIndex > 0) && (nextPrime < length));
	}

	/**
	* Construct a bit sieve of searchLen bits used for finding prime number
	* candidates. The new sieve begins at the specified base, which must
	* be even.
	*/
	BitSieve(BigInteger base, int searchLen) {
	/*
	* Candidates are indicated by clear bits in the sieve. As a candidates
	* nonprimality is calculated, a bit is set in the sieve to eliminate
	* it. To reduce storage space and increase efficiency, no even numbers
	* are represented in the sieve (each bit in the sieve represents an
	* odd number).
	*/
	bits = new long[(unitIndex(searchLen-1) + 1)];
	length = searchLen;
	int start = 0;

	int step = smallSieve.sieveSearch(smallSieve.length, start);
	int convertedStep = (step *2) + 1;

	// Construct the large sieve at an even offset specified by base
	MutableBigInteger b = new MutableBigInteger(base);
	MutableBigInteger q = new MutableBigInteger();
	do {
	// Calculate base mod convertedStep
	start = b.divideOneWord(convertedStep, q);

	// Take each multiple of step out of sieve
	start = convertedStep - start;
	if (start%2 == 0)
	start += convertedStep;
	sieveSingle(searchLen, (start-1)/2, convertedStep);

	// Find next prime from small sieve
	step = smallSieve.sieveSearch(smallSieve.length, step+1);
	convertedStep = (step *2) + 1;
	} while (step > 0);
	}

	/**
	* Given a bit index return unit index containing it.
	*/
	private static int unitIndex(int bitIndex) {
	return bitIndex >>> 6;
	}

	/**
	* Return a unit that masks the specified bit in its unit.
	*/
	private static long bit(int bitIndex) {
	return 1L << (bitIndex & ((1<<6) - 1));
	}

	/**
	* Get the value of the bit at the specified index.
	*/
	private boolean get(int bitIndex) {
	int unitIndex = unitIndex(bitIndex);
	return ((bits[unitIndex] & bit(bitIndex)) != 0);
	}

	/**
	* Set the bit at the specified index.
	*/
	private void set(int bitIndex) {
	int unitIndex = unitIndex(bitIndex);
	bits[unitIndex] \|= bit(bitIndex);
	}

	/**
	* This method returns the index of the first clear bit in the search
	* array that occurs at or after start. It will not search past the
	* specified limit. It returns -1 if there is no such clear bit.
	*/
	private int sieveSearch(int limit, int start) {
	if (start >= limit)
	return -1;

	int index = start;
	do {
	if (!get(index))
	return index;
	index++;
	} while(index < limit-1);
	return -1;
	}

	/**
	* Sieve a single set of multiples out of the sieve. Begin to remove
	* multiples of the specified step starting at the specified start index,
	* up to the specified limit.
	*/
	private void sieveSingle(int limit, int start, int step) {
	while(start < limit) {
	set(start);
	start += step;
	}
	}

	/**
	* Test probable primes in the sieve and return successful candidates.
	*/
	BigInteger retrieve(BigInteger initValue, int certainty, java.util.Random random) {
	// Examine the sieve one long at a time to find possible primes
	int offset = 1;
	for (int i=0; i<bits.length; i++) {
	long nextLong = ~bits[i];
	for (int j=0; j<64; j++) {
	if ((nextLong & 1) == 1) {
	BigInteger candidate = initValue.add(
	BigInteger.valueOf(offset));
	if (candidate.primeToCertainty(certainty, random))
	return candidate;
	}
	nextLong >>>= 1;
	offset+=2;
	}
	}
	return null;
	}
	}

Back to index...