/*
* 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.
Author: Michael McCloskey See Also: - BigInteger
Since: 1.3
/**
* 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.
/**
* Stores the bits in this bitSieve.
*/
private long bits[];
Length is how many bits this sieve holds.
/**
* 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.
/**
* 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.
/**
* 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.
/**
* 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.
/**
* 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.
/**
* 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.
/**
* 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.
/**
* 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.
/**
* 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.
/**
* 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.
/**
* 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;
}
}