FileDocCategorySizeDatePackage
BitSieve.javaAPI DocJava SE 6 API6643Tue Jun 10 00:25:40 BST 2008java.math

BitSieve

public 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.
see
BigInteger
version
1.12, 03/10/06
author
Michael McCloskey
since
1.3

Fields 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.
Constructors Summary
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.


                                                                                                 
      
        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));
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.

        /*
         * 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 r = new MutableBigInteger();
        MutableBigInteger q = new MutableBigInteger();
        do {
            // Calculate base mod convertedStep
            r.copyValue(base.mag);
            r.divideOneWord(convertedStep, q);
            start = r.value[r.offset];

            // 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);
Methods Summary
private static longbit(int bitIndex)
Return a unit that masks the specified bit in its unit.

        return 1L << (bitIndex & ((1<<6) - 1));
private booleanget(int bitIndex)
Get the value of the bit at the specified index.

        int unitIndex = unitIndex(bitIndex);
        return ((bits[unitIndex] & bit(bitIndex)) != 0);
java.math.BigIntegerretrieve(java.math.BigInteger initValue, int certainty, java.util.Random random)
Test probable primes in the sieve and return successful candidates.

        // 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;
private voidset(int bitIndex)
Set the bit at the specified index.

        int unitIndex = unitIndex(bitIndex);
        bits[unitIndex] |= bit(bitIndex);
private intsieveSearch(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.

        if (start >= limit)
            return -1;
        
        int index = start;
        do {
            if (!get(index))
                return index;
            index++;
        } while(index < limit-1);
        return -1;
private voidsieveSingle(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.

        while(start < limit) {
            set(start);
            start += step;
        }
private static intunitIndex(int bitIndex)
Given a bit index return unit index containing it.

        return bitIndex >>> 6;