jaroslav@1258
|
1 |
/*
|
jaroslav@1258
|
2 |
* Copyright (c) 1999, 2007, Oracle and/or its affiliates. All rights reserved.
|
jaroslav@1258
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
jaroslav@1258
|
4 |
*
|
jaroslav@1258
|
5 |
* This code is free software; you can redistribute it and/or modify it
|
jaroslav@1258
|
6 |
* under the terms of the GNU General Public License version 2 only, as
|
jaroslav@1258
|
7 |
* published by the Free Software Foundation. Oracle designates this
|
jaroslav@1258
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
jaroslav@1258
|
9 |
* by Oracle in the LICENSE file that accompanied this code.
|
jaroslav@1258
|
10 |
*
|
jaroslav@1258
|
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT
|
jaroslav@1258
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
jaroslav@1258
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
jaroslav@1258
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that
|
jaroslav@1258
|
15 |
* accompanied this code).
|
jaroslav@1258
|
16 |
*
|
jaroslav@1258
|
17 |
* You should have received a copy of the GNU General Public License version
|
jaroslav@1258
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation,
|
jaroslav@1258
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
jaroslav@1258
|
20 |
*
|
jaroslav@1258
|
21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
|
jaroslav@1258
|
22 |
* or visit www.oracle.com if you need additional information or have any
|
jaroslav@1258
|
23 |
* questions.
|
jaroslav@1258
|
24 |
*/
|
jaroslav@1258
|
25 |
|
jaroslav@1258
|
26 |
package java.math;
|
jaroslav@1258
|
27 |
|
jaroslav@1258
|
28 |
/**
|
jaroslav@1258
|
29 |
* A simple bit sieve used for finding prime number candidates. Allows setting
|
jaroslav@1258
|
30 |
* and clearing of bits in a storage array. The size of the sieve is assumed to
|
jaroslav@1258
|
31 |
* be constant to reduce overhead. All the bits of a new bitSieve are zero, and
|
jaroslav@1258
|
32 |
* bits are removed from it by setting them.
|
jaroslav@1258
|
33 |
*
|
jaroslav@1258
|
34 |
* To reduce storage space and increase efficiency, no even numbers are
|
jaroslav@1258
|
35 |
* represented in the sieve (each bit in the sieve represents an odd number).
|
jaroslav@1258
|
36 |
* The relationship between the index of a bit and the number it represents is
|
jaroslav@1258
|
37 |
* given by
|
jaroslav@1258
|
38 |
* N = offset + (2*index + 1);
|
jaroslav@1258
|
39 |
* Where N is the integer represented by a bit in the sieve, offset is some
|
jaroslav@1258
|
40 |
* even integer offset indicating where the sieve begins, and index is the
|
jaroslav@1258
|
41 |
* index of a bit in the sieve array.
|
jaroslav@1258
|
42 |
*
|
jaroslav@1258
|
43 |
* @see BigInteger
|
jaroslav@1258
|
44 |
* @author Michael McCloskey
|
jaroslav@1258
|
45 |
* @since 1.3
|
jaroslav@1258
|
46 |
*/
|
jaroslav@1258
|
47 |
class BitSieve {
|
jaroslav@1258
|
48 |
/**
|
jaroslav@1258
|
49 |
* Stores the bits in this bitSieve.
|
jaroslav@1258
|
50 |
*/
|
jaroslav@1258
|
51 |
private long bits[];
|
jaroslav@1258
|
52 |
|
jaroslav@1258
|
53 |
/**
|
jaroslav@1258
|
54 |
* Length is how many bits this sieve holds.
|
jaroslav@1258
|
55 |
*/
|
jaroslav@1258
|
56 |
private int length;
|
jaroslav@1258
|
57 |
|
jaroslav@1258
|
58 |
/**
|
jaroslav@1258
|
59 |
* A small sieve used to filter out multiples of small primes in a search
|
jaroslav@1258
|
60 |
* sieve.
|
jaroslav@1258
|
61 |
*/
|
jaroslav@1258
|
62 |
private static BitSieve smallSieve = new BitSieve();
|
jaroslav@1258
|
63 |
|
jaroslav@1258
|
64 |
/**
|
jaroslav@1258
|
65 |
* Construct a "small sieve" with a base of 0. This constructor is
|
jaroslav@1258
|
66 |
* used internally to generate the set of "small primes" whose multiples
|
jaroslav@1258
|
67 |
* are excluded from sieves generated by the main (package private)
|
jaroslav@1258
|
68 |
* constructor, BitSieve(BigInteger base, int searchLen). The length
|
jaroslav@1258
|
69 |
* of the sieve generated by this constructor was chosen for performance;
|
jaroslav@1258
|
70 |
* it controls a tradeoff between how much time is spent constructing
|
jaroslav@1258
|
71 |
* other sieves, and how much time is wasted testing composite candidates
|
jaroslav@1258
|
72 |
* for primality. The length was chosen experimentally to yield good
|
jaroslav@1258
|
73 |
* performance.
|
jaroslav@1258
|
74 |
*/
|
jaroslav@1258
|
75 |
private BitSieve() {
|
jaroslav@1258
|
76 |
length = 150 * 64;
|
jaroslav@1258
|
77 |
bits = new long[(unitIndex(length - 1) + 1)];
|
jaroslav@1258
|
78 |
|
jaroslav@1258
|
79 |
// Mark 1 as composite
|
jaroslav@1258
|
80 |
set(0);
|
jaroslav@1258
|
81 |
int nextIndex = 1;
|
jaroslav@1258
|
82 |
int nextPrime = 3;
|
jaroslav@1258
|
83 |
|
jaroslav@1258
|
84 |
// Find primes and remove their multiples from sieve
|
jaroslav@1258
|
85 |
do {
|
jaroslav@1258
|
86 |
sieveSingle(length, nextIndex + nextPrime, nextPrime);
|
jaroslav@1258
|
87 |
nextIndex = sieveSearch(length, nextIndex + 1);
|
jaroslav@1258
|
88 |
nextPrime = 2*nextIndex + 1;
|
jaroslav@1258
|
89 |
} while((nextIndex > 0) && (nextPrime < length));
|
jaroslav@1258
|
90 |
}
|
jaroslav@1258
|
91 |
|
jaroslav@1258
|
92 |
/**
|
jaroslav@1258
|
93 |
* Construct a bit sieve of searchLen bits used for finding prime number
|
jaroslav@1258
|
94 |
* candidates. The new sieve begins at the specified base, which must
|
jaroslav@1258
|
95 |
* be even.
|
jaroslav@1258
|
96 |
*/
|
jaroslav@1258
|
97 |
BitSieve(BigInteger base, int searchLen) {
|
jaroslav@1258
|
98 |
/*
|
jaroslav@1258
|
99 |
* Candidates are indicated by clear bits in the sieve. As a candidates
|
jaroslav@1258
|
100 |
* nonprimality is calculated, a bit is set in the sieve to eliminate
|
jaroslav@1258
|
101 |
* it. To reduce storage space and increase efficiency, no even numbers
|
jaroslav@1258
|
102 |
* are represented in the sieve (each bit in the sieve represents an
|
jaroslav@1258
|
103 |
* odd number).
|
jaroslav@1258
|
104 |
*/
|
jaroslav@1258
|
105 |
bits = new long[(unitIndex(searchLen-1) + 1)];
|
jaroslav@1258
|
106 |
length = searchLen;
|
jaroslav@1258
|
107 |
int start = 0;
|
jaroslav@1258
|
108 |
|
jaroslav@1258
|
109 |
int step = smallSieve.sieveSearch(smallSieve.length, start);
|
jaroslav@1258
|
110 |
int convertedStep = (step *2) + 1;
|
jaroslav@1258
|
111 |
|
jaroslav@1258
|
112 |
// Construct the large sieve at an even offset specified by base
|
jaroslav@1258
|
113 |
MutableBigInteger b = new MutableBigInteger(base);
|
jaroslav@1258
|
114 |
MutableBigInteger q = new MutableBigInteger();
|
jaroslav@1258
|
115 |
do {
|
jaroslav@1258
|
116 |
// Calculate base mod convertedStep
|
jaroslav@1258
|
117 |
start = b.divideOneWord(convertedStep, q);
|
jaroslav@1258
|
118 |
|
jaroslav@1258
|
119 |
// Take each multiple of step out of sieve
|
jaroslav@1258
|
120 |
start = convertedStep - start;
|
jaroslav@1258
|
121 |
if (start%2 == 0)
|
jaroslav@1258
|
122 |
start += convertedStep;
|
jaroslav@1258
|
123 |
sieveSingle(searchLen, (start-1)/2, convertedStep);
|
jaroslav@1258
|
124 |
|
jaroslav@1258
|
125 |
// Find next prime from small sieve
|
jaroslav@1258
|
126 |
step = smallSieve.sieveSearch(smallSieve.length, step+1);
|
jaroslav@1258
|
127 |
convertedStep = (step *2) + 1;
|
jaroslav@1258
|
128 |
} while (step > 0);
|
jaroslav@1258
|
129 |
}
|
jaroslav@1258
|
130 |
|
jaroslav@1258
|
131 |
/**
|
jaroslav@1258
|
132 |
* Given a bit index return unit index containing it.
|
jaroslav@1258
|
133 |
*/
|
jaroslav@1258
|
134 |
private static int unitIndex(int bitIndex) {
|
jaroslav@1258
|
135 |
return bitIndex >>> 6;
|
jaroslav@1258
|
136 |
}
|
jaroslav@1258
|
137 |
|
jaroslav@1258
|
138 |
/**
|
jaroslav@1258
|
139 |
* Return a unit that masks the specified bit in its unit.
|
jaroslav@1258
|
140 |
*/
|
jaroslav@1258
|
141 |
private static long bit(int bitIndex) {
|
jaroslav@1258
|
142 |
return 1L << (bitIndex & ((1<<6) - 1));
|
jaroslav@1258
|
143 |
}
|
jaroslav@1258
|
144 |
|
jaroslav@1258
|
145 |
/**
|
jaroslav@1258
|
146 |
* Get the value of the bit at the specified index.
|
jaroslav@1258
|
147 |
*/
|
jaroslav@1258
|
148 |
private boolean get(int bitIndex) {
|
jaroslav@1258
|
149 |
int unitIndex = unitIndex(bitIndex);
|
jaroslav@1258
|
150 |
return ((bits[unitIndex] & bit(bitIndex)) != 0);
|
jaroslav@1258
|
151 |
}
|
jaroslav@1258
|
152 |
|
jaroslav@1258
|
153 |
/**
|
jaroslav@1258
|
154 |
* Set the bit at the specified index.
|
jaroslav@1258
|
155 |
*/
|
jaroslav@1258
|
156 |
private void set(int bitIndex) {
|
jaroslav@1258
|
157 |
int unitIndex = unitIndex(bitIndex);
|
jaroslav@1258
|
158 |
bits[unitIndex] |= bit(bitIndex);
|
jaroslav@1258
|
159 |
}
|
jaroslav@1258
|
160 |
|
jaroslav@1258
|
161 |
/**
|
jaroslav@1258
|
162 |
* This method returns the index of the first clear bit in the search
|
jaroslav@1258
|
163 |
* array that occurs at or after start. It will not search past the
|
jaroslav@1258
|
164 |
* specified limit. It returns -1 if there is no such clear bit.
|
jaroslav@1258
|
165 |
*/
|
jaroslav@1258
|
166 |
private int sieveSearch(int limit, int start) {
|
jaroslav@1258
|
167 |
if (start >= limit)
|
jaroslav@1258
|
168 |
return -1;
|
jaroslav@1258
|
169 |
|
jaroslav@1258
|
170 |
int index = start;
|
jaroslav@1258
|
171 |
do {
|
jaroslav@1258
|
172 |
if (!get(index))
|
jaroslav@1258
|
173 |
return index;
|
jaroslav@1258
|
174 |
index++;
|
jaroslav@1258
|
175 |
} while(index < limit-1);
|
jaroslav@1258
|
176 |
return -1;
|
jaroslav@1258
|
177 |
}
|
jaroslav@1258
|
178 |
|
jaroslav@1258
|
179 |
/**
|
jaroslav@1258
|
180 |
* Sieve a single set of multiples out of the sieve. Begin to remove
|
jaroslav@1258
|
181 |
* multiples of the specified step starting at the specified start index,
|
jaroslav@1258
|
182 |
* up to the specified limit.
|
jaroslav@1258
|
183 |
*/
|
jaroslav@1258
|
184 |
private void sieveSingle(int limit, int start, int step) {
|
jaroslav@1258
|
185 |
while(start < limit) {
|
jaroslav@1258
|
186 |
set(start);
|
jaroslav@1258
|
187 |
start += step;
|
jaroslav@1258
|
188 |
}
|
jaroslav@1258
|
189 |
}
|
jaroslav@1258
|
190 |
|
jaroslav@1258
|
191 |
/**
|
jaroslav@1258
|
192 |
* Test probable primes in the sieve and return successful candidates.
|
jaroslav@1258
|
193 |
*/
|
jaroslav@1258
|
194 |
BigInteger retrieve(BigInteger initValue, int certainty, java.util.Random random) {
|
jaroslav@1258
|
195 |
// Examine the sieve one long at a time to find possible primes
|
jaroslav@1258
|
196 |
int offset = 1;
|
jaroslav@1258
|
197 |
for (int i=0; i<bits.length; i++) {
|
jaroslav@1258
|
198 |
long nextLong = ~bits[i];
|
jaroslav@1258
|
199 |
for (int j=0; j<64; j++) {
|
jaroslav@1258
|
200 |
if ((nextLong & 1) == 1) {
|
jaroslav@1258
|
201 |
BigInteger candidate = initValue.add(
|
jaroslav@1258
|
202 |
BigInteger.valueOf(offset));
|
jaroslav@1258
|
203 |
if (candidate.primeToCertainty(certainty, random))
|
jaroslav@1258
|
204 |
return candidate;
|
jaroslav@1258
|
205 |
}
|
jaroslav@1258
|
206 |
nextLong >>>= 1;
|
jaroslav@1258
|
207 |
offset+=2;
|
jaroslav@1258
|
208 |
}
|
jaroslav@1258
|
209 |
}
|
jaroslav@1258
|
210 |
return null;
|
jaroslav@1258
|
211 |
}
|
jaroslav@1258
|
212 |
}
|