java.math
Class BitSieve

java.lang.Object
  |
  +--java.math.BitSieve

class BitSieve

extends Object

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.

Since:

1.3

Version:

1.8, 06/11/02

Author:

Michael McCloskey

See Also:

BigInteger

Field Summary

private long[]	bits Stores the bits in this bitSieve.
private int	length Length is how many bits this sieve holds.
private static BitSieve	smallSieve A small sieve used to filter out multiples of small primes in a search sieve.

Constructor Summary

private	BitSieve() Construct a "small sieve" with a base of 0.
(package private)	BitSieve(BigInteger base, int searchLen) Construct a bit sieve of searchLen bits used for finding prime number candidates.

Method Summary

private static long	bit(int bitIndex) Return a unit that masks the specified bit in its unit.
private boolean	get(int bitIndex) Get the value of the bit at the specified index.
(package private) BigInteger	retrieve(BigInteger initValue, int certainty) Test probable primes in the sieve and return successful candidates.
private void	set(int bitIndex) Set the bit at the specified index.
private int	sieveSearch(int limit, int start) This method returns the index of the first clear bit in the search array that occurs at or after start.
private void	sieveSingle(int limit, int start, int step) Sieve a single set of multiples out of the sieve.
private static int	unitIndex(int bitIndex) Given a bit index return unit index containing it.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

bits

private long[] bits

Stores the bits in this bitSieve.

length

private int length

Length is how many bits this sieve holds.

smallSieve

private static BitSieve smallSieve

A small sieve used to filter out multiples of small primes in a search sieve.

Constructor Detail

BitSieve

private 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.

BitSieve

BitSieve(BigInteger base,
         int searchLen)

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.

Method Detail

unitIndex

private static int unitIndex(int bitIndex)

Given a bit index return unit index containing it.

bit

private static long bit(int bitIndex)

Return a unit that masks the specified bit in its unit.

get

private boolean get(int bitIndex)

Get the value of the bit at the specified index.

set

private void set(int bitIndex)

Set the bit at the specified index.

sieveSearch

private int sieveSearch(int limit,
                        int start)

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.

sieveSingle

private void sieveSingle(int limit,
                         int start,
                         int step)

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.

retrieve

BigInteger retrieve(BigInteger initValue,
                    int certainty)

Test probable primes in the sieve and return successful candidates.