PrimeFinder


1   package com.jofti.util;
2   
3   /**
4   
5   * An amended version of the PrimeFinder implementation from CERN's COLT project.
6   * 
7    * Not of interest for users; only for implementors of hashtables.
8   
9    * Used to keep hash table capacities prime numbers.
10  
11   *
12  
13   * <p>Choosing prime numbers as hash table capacities is a good idea to keep them working fast,
14  
15   * particularly under hash table expansions.
16  
17   *
18  
19   * <p>However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to keep capacities prime.
20  
21   * This class provides efficient means to choose prime capacities.
22  
23   *
24  
25   * <p>Choosing a prime is <tt>O(log 300)</tt> (binary search in a list of 300 int's).
26  
27   * Memory requirements: 1 KB static memory.
28  
29   *
30  
31   * @author steve@jofti.com
32   * @author wolfgang.hoschek@cern.ch
33  
34   * @version 1.1  03/01/06 
35   * @version 1.0, 09/24/99
36  
37   */
38  public class PrimeFinder  {
39  
40      /**
41  
42       * The largest prime this class can generate; currently equal to <tt>Integer.MAX_VALUE</tt>.
43  
44       */
45  
46      public static final int largestPrime = Integer.MAX_VALUE; //yes, it is prime.
47  
48  
49  
50      /**
51  
52       * The prime number list consists of 11 chunks.
53  
54       * Each chunk contains prime numbers.
55  
56       * A chunk starts with a prime P1. The next element is a prime P2. P2 is the smallest prime for which holds: P2 >= 2*P1.
57  
58       * The next element is P3, for which the same holds with respect to P2, and so on.
59  
60       *
61  
62       * Chunks are chosen such that for any desired capacity >= 1000 
63  
64       * the list includes a prime number <= desired capacity * 1.11 (11%).
65  
66       * For any desired capacity >= 200 
67  
68       * the list includes a prime number <= desired capacity * 1.16 (16%).
69  
70       * For any desired capacity >= 16
71  
72       * the list includes a prime number <= desired capacity * 1.21 (21%).
73  
74       * 
75  
76       * Therefore, primes can be retrieved which are quite close to any desired capacity,
77  
78       * which in turn avoids wasting memory.
79  
80       * For example, the list includes 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
81  
82       * So if you need a prime >= 1040, you will find a prime <= 1040*1.11=1154.
83  
84       *  
85  
86       * Chunks are chosen such that they are optimized for a hashtable growthfactor of 2.0;
87  
88       * If your hashtable has such a growthfactor then,  
89  
90       * after initially "rounding to a prime" upon hashtable construction, 
91  
92       * it will later expand to prime capacities such that there exist no better primes.
93  
94       *
95  
96       * In total these are about 32*10=320 numbers -> 1 KB of static memory needed.
97  
98       * If you are stingy, then delete every second or fourth chunk.
99  
100      */
101 
102     
103 
104     private static final int[] primeCapacities = {
105 
106         //chunk #0
107 
108         largestPrime,
109 
110         
111 
112         //chunk #1
113 
114         5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,
115 
116           411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939,
117 
118           210719881,421439783,842879579,1685759167,
119 
120           
121 
122         //chunk #2
123 
124         433,877,1759,3527,7057,14143,28289,56591,113189,226379,452759,905551,1811107,
125 
126           3622219,7244441,14488931,28977863,57955739,115911563,231823147,463646329,927292699,
127 
128           1854585413,
129 
130           
131 
132         //chunk #3
133 
134         953,1907,3821,7643,15287,30577,61169,122347,244703,489407,978821,1957651,3915341,
135 
136           7830701,15661423,31322867,62645741,125291483,250582987,501165979,1002331963,
137 
138           2004663929,
139 
140           
141 
142         //chunk #4
143 
144         1039,2081,4177,8363,16729,33461,66923,133853,267713,535481,1070981,2141977,4283963,
145 
146           8567929,17135863,34271747,68543509,137087021,274174111,548348231,1096696463,
147 
148           
149 
150         //chunk #5
151 
152         31,67,137,277,557,1117,2237,4481,8963,17929,35863,71741,143483,286973,573953,
153 
154           1147921,2295859,4591721,9183457,18366923,36733847,73467739,146935499,293871013,
155 
156           587742049,1175484103,
157 
158           
159 
160         //chunk #6
161 
162         599,1201,2411,4831,9677,19373,38747,77509,155027,310081,620171,1240361,2480729,
163 
164           4961459,9922933,19845871,39691759,79383533,158767069,317534141,635068283,1270136683,
165 
166           
167 
168         //chunk #7
169 
170         311,631,1277,2557,5119,10243,20507,41017,82037,164089,328213,656429,1312867,
171 
172           2625761,5251529,10503061,21006137,42012281,84024581,168049163,336098327,672196673,
173 
174           1344393353,
175 
176           
177 
178         //chunk #8
179 
180         3,7,17,37,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899,
181 
182           701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,
183 
184           359339171,718678369,1437356741,
185 
186           
187 
188         //chunk #9
189 
190         43,89,179,359,719,1439,2879,5779,11579,23159,46327,92657,185323,370661,741337,
191 
192           1482707,2965421,5930887,11861791,23723597,47447201,94894427,189788857,379577741,
193 
194           759155483,1518310967,
195 
196           
197 
198         //chunk #10
199 
200         379,761,1523,3049,6101,12203,24407,48817,97649,195311,390647,781301,1562611,
201 
202           3125257,6250537,12501169,25002389,50004791,100009607,200019221,400038451,800076929,
203 
204           1600153859
205 
206 
207 
208         };
209 
210         
211 
212 
213 
214     static { //initializer
215 
216         // The above prime numbers are formatted for human readability.
217 
218         // To find numbers fast, we sort them once and for all.
219 
220         
221 
222         java.util.Arrays.sort(primeCapacities);
223 
224 
225     }
226 
227     
228 
229 /**
230 
231  * Makes this class non instantiable, but still let's others inherit from it.
232 
233  */
234 
235 protected PrimeFinder() {}
236 
237 /**
238 
239  
240 
241 
242 /**
243 
244  * Returns a prime number which is <code>&gt;= desiredCapacity</code> and very close to <code>desiredCapacity</code> (within 11% if <code>desiredCapacity &gt;= 1000</code>).
245 
246  * @param desiredCapacity the capacity desired by the user.
247 
248  * @return the capacity which should be used for a hashtable.
249 
250  */
251 
252 public static int nextPrime(int desiredCapacity) {
253 
254     int i = java.util.Arrays.binarySearch(primeCapacities, desiredCapacity);
255 
256 
257     if (i<0) {
258 
259         // desired capacity not found, choose next prime greater than desired capacity
260 
261         i = -i -1; // remember the semantics of binarySearch...
262 
263     }
264 
265     return primeCapacities[i];
266 
267 }
268 
269 
270 }
271
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags