001: /*
002: * @(#)BitSieve.java 1.12 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.math;
029:
030: /**
031: * A simple bit sieve used for finding prime number candidates. Allows setting
032: * and clearing of bits in a storage array. The size of the sieve is assumed to
033: * be constant to reduce overhead. All the bits of a new bitSieve are zero, and
034: * bits are removed from it by setting them.
035: *
036: * To reduce storage space and increase efficiency, no even numbers are
037: * represented in the sieve (each bit in the sieve represents an odd number).
038: * The relationship between the index of a bit and the number it represents is
039: * given by
040: * N = offset + (2*index + 1);
041: * Where N is the integer represented by a bit in the sieve, offset is some
042: * even integer offset indicating where the sieve begins, and index is the
043: * index of a bit in the sieve array.
044: *
045: * @see BigInteger
046: * @version 1.6, 02/02/00
047: * @author Michael McCloskey
048: * @since 1.3
049: */
050: class BitSieve {
051: /**
052: * Stores the bits in this bitSieve.
053: */
054: private long bits[];
055:
056: /**
057: * Length is how many bits this sieve holds.
058: */
059: private int length;
060:
061: /**
062: * A small sieve used to filter out multiples of small primes in a search
063: * sieve.
064: */
065: private static BitSieve smallSieve = new BitSieve();
066:
067: /**
068: * Construct a "small sieve" with a base of 0. This constructor is
069: * used internally to generate the set of "small primes" whose multiples
070: * are excluded from sieves generated by the main (package private)
071: * constructor, BitSieve(BigInteger base, int searchLen). The length
072: * of the sieve generated by this constructor was chosen for performance;
073: * it controls a tradeoff between how much time is spent constructing
074: * other sieves, and how much time is wasted testing composite candidates
075: * for primality. The length was chosen experimentally to yield good
076: * performance.
077: */
078: private BitSieve() {
079: length = 150 * 64;
080: bits = new long[(unitIndex(length - 1) + 1)];
081:
082: // Mark 1 as composite
083: set(0);
084: int nextIndex = 1;
085: int nextPrime = 3;
086:
087: // Find primes and remove their multiples from sieve
088: do {
089: sieveSingle(length, nextIndex + nextPrime, nextPrime);
090: nextIndex = sieveSearch(length, nextIndex + 1);
091: nextPrime = 2 * nextIndex + 1;
092: } while ((nextIndex > 0) && (nextPrime < length));
093: }
094:
095: /**
096: * Construct a bit sieve of searchLen bits used for finding prime number
097: * candidates. The new sieve begins at the specified base, which must
098: * be even.
099: */
100: BitSieve(BigInteger base, int searchLen) {
101: /*
102: * Candidates are indicated by clear bits in the sieve. As a candidates
103: * nonprimality is calculated, a bit is set in the sieve to eliminate
104: * it. To reduce storage space and increase efficiency, no even numbers
105: * are represented in the sieve (each bit in the sieve represents an
106: * odd number).
107: */
108: bits = new long[(unitIndex(searchLen - 1) + 1)];
109: length = searchLen;
110: int start = 0;
111:
112: int step = smallSieve.sieveSearch(smallSieve.length, start);
113: int convertedStep = (step * 2) + 1;
114:
115: // Construct the large sieve at an even offset specified by base
116: MutableBigInteger r = new MutableBigInteger();
117: MutableBigInteger q = new MutableBigInteger();
118: do {
119: // Calculate base mod convertedStep
120: r.copyValue(base.mag);
121: r.divideOneWord(convertedStep, q);
122: start = r.value[r.offset];
123:
124: // Take each multiple of step out of sieve
125: start = convertedStep - start;
126: if (start % 2 == 0)
127: start += convertedStep;
128: sieveSingle(searchLen, (start - 1) / 2, convertedStep);
129:
130: // Find next prime from small sieve
131: step = smallSieve.sieveSearch(smallSieve.length, step + 1);
132: convertedStep = (step * 2) + 1;
133: } while (step > 0);
134: }
135:
136: /**
137: * Given a bit index return unit index containing it.
138: */
139: private static int unitIndex(int bitIndex) {
140: return bitIndex >>> 6;
141: }
142:
143: /**
144: * Return a unit that masks the specified bit in its unit.
145: */
146: private static long bit(int bitIndex) {
147: return 1L << (bitIndex & ((1 << 6) - 1));
148: }
149:
150: /**
151: * Get the value of the bit at the specified index.
152: */
153: private boolean get(int bitIndex) {
154: int unitIndex = unitIndex(bitIndex);
155: return ((bits[unitIndex] & bit(bitIndex)) != 0);
156: }
157:
158: /**
159: * Set the bit at the specified index.
160: */
161: private void set(int bitIndex) {
162: int unitIndex = unitIndex(bitIndex);
163: bits[unitIndex] |= bit(bitIndex);
164: }
165:
166: /**
167: * This method returns the index of the first clear bit in the search
168: * array that occurs at or after start. It will not search past the
169: * specified limit. It returns -1 if there is no such clear bit.
170: */
171: private int sieveSearch(int limit, int start) {
172: if (start >= limit)
173: return -1;
174:
175: int index = start;
176: do {
177: if (!get(index))
178: return index;
179: index++;
180: } while (index < limit - 1);
181: return -1;
182: }
183:
184: /**
185: * Sieve a single set of multiples out of the sieve. Begin to remove
186: * multiples of the specified step starting at the specified start index,
187: * up to the specified limit.
188: */
189: private void sieveSingle(int limit, int start, int step) {
190: while (start < limit) {
191: set(start);
192: start += step;
193: }
194: }
195:
196: /**
197: * Test probable primes in the sieve and return successful candidates.
198: */
199: BigInteger retrieve(BigInteger initValue, int certainty) {
200: // Examine the sieve one long at a time to find possible primes
201: int offset = 1;
202: for (int i = 0; i < bits.length; i++) {
203: long nextLong = ~bits[i];
204: for (int j = 0; j < 64; j++) {
205: if ((nextLong & 1) == 1) {
206: BigInteger candidate = initValue.add(BigInteger
207: .valueOf(offset));
208: if (candidate.isProbablePrime(certainty))
209: return candidate;
210: }
211: nextLong >>>= 1;
212: offset += 2;
213: }
214: }
215: return null;
216: }
217: }
|