001: // Copyright (c) 1999 CERN - European Organization for Nuclear Research.
002:
003: // Permission to use, copy, modify, distribute and sell this software
004: // and its documentation for any purpose is hereby granted without fee,
005: // provided that the above copyright notice appear in all copies and
006: // that both that copyright notice and this permission notice appear in
007: // supporting documentation. CERN makes no representations about the
008: // suitability of this software for any purpose. It is provided "as is"
009: // without expressed or implied warranty.
010: package gnu.trove;
011:
012: import java.util.Arrays;
013:
014: /*
015: * Modified for Trove to use the java.util.Arrays sort/search
016: * algorithms instead of those provided with colt.
017: */
018:
019: /**
020: * Used to keep hash table capacities prime numbers.
021: * Not of interest for users; only for implementors of hashtables.
022: *
023: * <p>Choosing prime numbers as hash table capacities is a good idea
024: * to keep them working fast, particularly under hash table
025: * expansions.
026: *
027: * <p>However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to
028: * keep capacities prime. This class provides efficient means to
029: * choose prime capacities.
030: *
031: * <p>Choosing a prime is <tt>O(log 300)</tt> (binary search in a list
032: * of 300 ints). Memory requirements: 1 KB static memory.
033: *
034: * @author wolfgang.hoschek@cern.ch
035: * @version 1.0, 09/24/99
036: */
037: public final class PrimeFinder {
038: /**
039: * The largest prime this class can generate; currently equal to
040: * <tt>Integer.MAX_VALUE</tt>.
041: */
042: public static final int largestPrime = Integer.MAX_VALUE; //yes, it is prime.
043:
044: /**
045: * The prime number list consists of 11 chunks.
046: *
047: * Each chunk contains prime numbers.
048: *
049: * A chunk starts with a prime P1. The next element is a prime
050: * P2. P2 is the smallest prime for which holds: P2 >= 2*P1.
051: *
052: * The next element is P3, for which the same holds with respect
053: * to P2, and so on.
054: *
055: * Chunks are chosen such that for any desired capacity >= 1000
056: * the list includes a prime number <= desired capacity * 1.11.
057: *
058: * Therefore, primes can be retrieved which are quite close to any
059: * desired capacity, which in turn avoids wasting memory.
060: *
061: * For example, the list includes
062: * 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
063: *
064: * So if you need a prime >= 1040, you will find a prime <=
065: * 1040*1.11=1154.
066: *
067: * Chunks are chosen such that they are optimized for a hashtable
068: * growthfactor of 2.0;
069: *
070: * If your hashtable has such a growthfactor then, after initially
071: * "rounding to a prime" upon hashtable construction, it will
072: * later expand to prime capacities such that there exist no
073: * better primes.
074: *
075: * In total these are about 32*10=320 numbers -> 1 KB of static
076: * memory needed.
077: *
078: * If you are stingy, then delete every second or fourth chunk.
079: */
080:
081: private static final int[] primeCapacities = {
082: //chunk #0
083: largestPrime,
084:
085: //chunk #1
086: 5,
087: 11,
088: 23,
089: 47,
090: 97,
091: 197,
092: 397,
093: 797,
094: 1597,
095: 3203,
096: 6421,
097: 12853,
098: 25717,
099: 51437,
100: 102877,
101: 205759,
102: 411527,
103: 823117,
104: 1646237,
105: 3292489,
106: 6584983,
107: 13169977,
108: 26339969,
109: 52679969,
110: 105359939,
111: 210719881,
112: 421439783,
113: 842879579,
114: 1685759167,
115:
116: //chunk #2
117: 433,
118: 877,
119: 1759,
120: 3527,
121: 7057,
122: 14143,
123: 28289,
124: 56591,
125: 113189,
126: 226379,
127: 452759,
128: 905551,
129: 1811107,
130: 3622219,
131: 7244441,
132: 14488931,
133: 28977863,
134: 57955739,
135: 115911563,
136: 231823147,
137: 463646329,
138: 927292699,
139: 1854585413,
140:
141: //chunk #3
142: 953,
143: 1907,
144: 3821,
145: 7643,
146: 15287,
147: 30577,
148: 61169,
149: 122347,
150: 244703,
151: 489407,
152: 978821,
153: 1957651,
154: 3915341,
155: 7830701,
156: 15661423,
157: 31322867,
158: 62645741,
159: 125291483,
160: 250582987,
161: 501165979,
162: 1002331963,
163: 2004663929,
164:
165: //chunk #4
166: 1039,
167: 2081,
168: 4177,
169: 8363,
170: 16729,
171: 33461,
172: 66923,
173: 133853,
174: 267713,
175: 535481,
176: 1070981,
177: 2141977,
178: 4283963,
179: 8567929,
180: 17135863,
181: 34271747,
182: 68543509,
183: 137087021,
184: 274174111,
185: 548348231,
186: 1096696463,
187:
188: //chunk #5
189: 31, 67, 137, 277, 557, 1117, 2237, 4481, 8963,
190: 17929,
191: 35863,
192: 71741,
193: 143483,
194: 286973,
195: 573953,
196: 1147921,
197: 2295859,
198: 4591721,
199: 9183457,
200: 18366923,
201: 36733847,
202: 73467739,
203: 146935499,
204: 293871013,
205: 587742049,
206: 1175484103,
207:
208: //chunk #6
209: 599, 1201, 2411, 4831, 9677, 19373, 38747, 77509,
210: 155027,
211: 310081,
212: 620171,
213: 1240361,
214: 2480729,
215: 4961459,
216: 9922933,
217: 19845871,
218: 39691759,
219: 79383533,
220: 158767069,
221: 317534141,
222: 635068283,
223: 1270136683,
224:
225: //chunk #7
226: 311, 631, 1277, 2557, 5119, 10243, 20507, 41017, 82037,
227: 164089, 328213, 656429, 1312867,
228: 2625761,
229: 5251529,
230: 10503061,
231: 21006137,
232: 42012281,
233: 84024581,
234: 168049163,
235: 336098327,
236: 672196673,
237: 1344393353,
238:
239: //chunk #8
240: 3, 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949,
241: 21911, 43853, 87719, 175447, 350899, 701819, 1403641,
242: 2807303, 5614657, 11229331, 22458671,
243: 44917381,
244: 89834777,
245: 179669557,
246: 359339171,
247: 718678369,
248: 1437356741,
249:
250: //chunk #9
251: 43, 89, 179, 359, 719, 1439, 2879, 5779, 11579, 23159,
252: 46327, 92657, 185323, 370661, 741337, 1482707, 2965421,
253: 5930887, 11861791, 23723597, 47447201, 94894427, 189788857,
254: 379577741,
255: 759155483,
256: 1518310967,
257:
258: //chunk #10
259: 379, 761, 1523, 3049, 6101, 12203, 24407, 48817, 97649,
260: 195311, 390647, 781301, 1562611, 3125257, 6250537,
261: 12501169, 25002389, 50004791, 100009607, 200019221,
262: 400038451, 800076929, 1600153859 };
263:
264: static { //initializer
265: // The above prime numbers are formatted for human readability.
266: // To find numbers fast, we sort them once and for all.
267:
268: Arrays.sort(primeCapacities);
269: }
270:
271: /**
272: * Returns a prime number which is <code>>= desiredCapacity</code>
273: * and very close to <code>desiredCapacity</code> (within 11% if
274: * <code>desiredCapacity >= 1000</code>).
275: *
276: * @param desiredCapacity the capacity desired by the user.
277: * @return the capacity which should be used for a hashtable.
278: */
279: public static final int nextPrime(int desiredCapacity) {
280: int i = Arrays.binarySearch(primeCapacities, desiredCapacity);
281: if (i < 0) {
282: // desired capacity not found, choose next prime greater
283: // than desired capacity
284: i = -i - 1; // remember the semantics of binarySearch...
285: }
286: return primeCapacities[i];
287: }
288: }
|