java.math
Class BitSieve

java.lang.Object
  extended byjava.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
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.