1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/math/BitSieve.java Sat Sep 07 13:51:24 2013 +0200
1.3 @@ -0,0 +1,212 @@
1.4 +/*
1.5 + * Copyright (c) 1999, 2007, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.math;
1.30 +
1.31 +/**
1.32 + * A simple bit sieve used for finding prime number candidates. Allows setting
1.33 + * and clearing of bits in a storage array. The size of the sieve is assumed to
1.34 + * be constant to reduce overhead. All the bits of a new bitSieve are zero, and
1.35 + * bits are removed from it by setting them.
1.36 + *
1.37 + * To reduce storage space and increase efficiency, no even numbers are
1.38 + * represented in the sieve (each bit in the sieve represents an odd number).
1.39 + * The relationship between the index of a bit and the number it represents is
1.40 + * given by
1.41 + * N = offset + (2*index + 1);
1.42 + * Where N is the integer represented by a bit in the sieve, offset is some
1.43 + * even integer offset indicating where the sieve begins, and index is the
1.44 + * index of a bit in the sieve array.
1.45 + *
1.46 + * @see BigInteger
1.47 + * @author Michael McCloskey
1.48 + * @since 1.3
1.49 + */
1.50 +class BitSieve {
1.51 + /**
1.52 + * Stores the bits in this bitSieve.
1.53 + */
1.54 + private long bits[];
1.55 +
1.56 + /**
1.57 + * Length is how many bits this sieve holds.
1.58 + */
1.59 + private int length;
1.60 +
1.61 + /**
1.62 + * A small sieve used to filter out multiples of small primes in a search
1.63 + * sieve.
1.64 + */
1.65 + private static BitSieve smallSieve = new BitSieve();
1.66 +
1.67 + /**
1.68 + * Construct a "small sieve" with a base of 0. This constructor is
1.69 + * used internally to generate the set of "small primes" whose multiples
1.70 + * are excluded from sieves generated by the main (package private)
1.71 + * constructor, BitSieve(BigInteger base, int searchLen). The length
1.72 + * of the sieve generated by this constructor was chosen for performance;
1.73 + * it controls a tradeoff between how much time is spent constructing
1.74 + * other sieves, and how much time is wasted testing composite candidates
1.75 + * for primality. The length was chosen experimentally to yield good
1.76 + * performance.
1.77 + */
1.78 + private BitSieve() {
1.79 + length = 150 * 64;
1.80 + bits = new long[(unitIndex(length - 1) + 1)];
1.81 +
1.82 + // Mark 1 as composite
1.83 + set(0);
1.84 + int nextIndex = 1;
1.85 + int nextPrime = 3;
1.86 +
1.87 + // Find primes and remove their multiples from sieve
1.88 + do {
1.89 + sieveSingle(length, nextIndex + nextPrime, nextPrime);
1.90 + nextIndex = sieveSearch(length, nextIndex + 1);
1.91 + nextPrime = 2*nextIndex + 1;
1.92 + } while((nextIndex > 0) && (nextPrime < length));
1.93 + }
1.94 +
1.95 + /**
1.96 + * Construct a bit sieve of searchLen bits used for finding prime number
1.97 + * candidates. The new sieve begins at the specified base, which must
1.98 + * be even.
1.99 + */
1.100 + BitSieve(BigInteger base, int searchLen) {
1.101 + /*
1.102 + * Candidates are indicated by clear bits in the sieve. As a candidates
1.103 + * nonprimality is calculated, a bit is set in the sieve to eliminate
1.104 + * it. To reduce storage space and increase efficiency, no even numbers
1.105 + * are represented in the sieve (each bit in the sieve represents an
1.106 + * odd number).
1.107 + */
1.108 + bits = new long[(unitIndex(searchLen-1) + 1)];
1.109 + length = searchLen;
1.110 + int start = 0;
1.111 +
1.112 + int step = smallSieve.sieveSearch(smallSieve.length, start);
1.113 + int convertedStep = (step *2) + 1;
1.114 +
1.115 + // Construct the large sieve at an even offset specified by base
1.116 + MutableBigInteger b = new MutableBigInteger(base);
1.117 + MutableBigInteger q = new MutableBigInteger();
1.118 + do {
1.119 + // Calculate base mod convertedStep
1.120 + start = b.divideOneWord(convertedStep, q);
1.121 +
1.122 + // Take each multiple of step out of sieve
1.123 + start = convertedStep - start;
1.124 + if (start%2 == 0)
1.125 + start += convertedStep;
1.126 + sieveSingle(searchLen, (start-1)/2, convertedStep);
1.127 +
1.128 + // Find next prime from small sieve
1.129 + step = smallSieve.sieveSearch(smallSieve.length, step+1);
1.130 + convertedStep = (step *2) + 1;
1.131 + } while (step > 0);
1.132 + }
1.133 +
1.134 + /**
1.135 + * Given a bit index return unit index containing it.
1.136 + */
1.137 + private static int unitIndex(int bitIndex) {
1.138 + return bitIndex >>> 6;
1.139 + }
1.140 +
1.141 + /**
1.142 + * Return a unit that masks the specified bit in its unit.
1.143 + */
1.144 + private static long bit(int bitIndex) {
1.145 + return 1L << (bitIndex & ((1<<6) - 1));
1.146 + }
1.147 +
1.148 + /**
1.149 + * Get the value of the bit at the specified index.
1.150 + */
1.151 + private boolean get(int bitIndex) {
1.152 + int unitIndex = unitIndex(bitIndex);
1.153 + return ((bits[unitIndex] & bit(bitIndex)) != 0);
1.154 + }
1.155 +
1.156 + /**
1.157 + * Set the bit at the specified index.
1.158 + */
1.159 + private void set(int bitIndex) {
1.160 + int unitIndex = unitIndex(bitIndex);
1.161 + bits[unitIndex] |= bit(bitIndex);
1.162 + }
1.163 +
1.164 + /**
1.165 + * This method returns the index of the first clear bit in the search
1.166 + * array that occurs at or after start. It will not search past the
1.167 + * specified limit. It returns -1 if there is no such clear bit.
1.168 + */
1.169 + private int sieveSearch(int limit, int start) {
1.170 + if (start >= limit)
1.171 + return -1;
1.172 +
1.173 + int index = start;
1.174 + do {
1.175 + if (!get(index))
1.176 + return index;
1.177 + index++;
1.178 + } while(index < limit-1);
1.179 + return -1;
1.180 + }
1.181 +
1.182 + /**
1.183 + * Sieve a single set of multiples out of the sieve. Begin to remove
1.184 + * multiples of the specified step starting at the specified start index,
1.185 + * up to the specified limit.
1.186 + */
1.187 + private void sieveSingle(int limit, int start, int step) {
1.188 + while(start < limit) {
1.189 + set(start);
1.190 + start += step;
1.191 + }
1.192 + }
1.193 +
1.194 + /**
1.195 + * Test probable primes in the sieve and return successful candidates.
1.196 + */
1.197 + BigInteger retrieve(BigInteger initValue, int certainty, java.util.Random random) {
1.198 + // Examine the sieve one long at a time to find possible primes
1.199 + int offset = 1;
1.200 + for (int i=0; i<bits.length; i++) {
1.201 + long nextLong = ~bits[i];
1.202 + for (int j=0; j<64; j++) {
1.203 + if ((nextLong & 1) == 1) {
1.204 + BigInteger candidate = initValue.add(
1.205 + BigInteger.valueOf(offset));
1.206 + if (candidate.primeToCertainty(certainty, random))
1.207 + return candidate;
1.208 + }
1.209 + nextLong >>>= 1;
1.210 + offset+=2;
1.211 + }
1.212 + }
1.213 + return null;
1.214 + }
1.215 +}