diff -r fd16c54261b3 -r 90ce3da70b43 jdk/src/share/classes/java/math/BitSieve.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/java/math/BitSieve.java Sat Dec 01 00:00:00 2007 +0000 @@ -0,0 +1,214 @@ +/* + * Copyright 1999-2007 Sun Microsystems, Inc. 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. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.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. + * + * @see BigInteger + * @author Michael McCloskey + * @since 1.3 + */ +class BitSieve { + /** + * Stores the bits in this bitSieve. + */ + private long bits[]; + + /** + * 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. + */ + 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. + */ + 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. + */ + 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 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); + } + + /** + * 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. + */ + private static long bit(int bitIndex) { + return 1L << (bitIndex & ((1<<6) - 1)); + } + + /** + * 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. + */ + 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. + */ + 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. + */ + 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. + */ + 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>>= 1; + offset+=2; + } + } + return null; + } +}