PrimeFinder


1   package prefuse.util.collections;
2   
3   /**
4    * Not of interest for users; only for implementors of hashtables. Used to keep
5    * hash table capacities prime numbers.
6    * 
7    * <p>
8    * Choosing prime numbers as hash table capacities is a good idea to keep them
9    * working fast, particularly under hash table expansions.
10   * </p>
11   * 
12   * <p>
13   * However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to keep
14   * capacities prime. This class provides efficient means to choose prime
15   * capacities.
16   * </p>
17   * 
18   * <p>
19   * Choosing a prime is <tt>O(log 300)</tt> (binary search in a list of 300
20   * int's). Memory requirements: 1 KB static memory.
21   * </p>
22   * 
23   * This class has been adapted from the corresponding class in the COLT
24   * library for scientfic computing.
25   * 
26   * @author wolfgang.hoschek@cern.ch
27   * @version 1.0, 09/24/99
28   */
29  public class PrimeFinder extends Object   {
30      /**
31       * The largest prime this class can generate; currently equal to
32       * <tt>Integer.MAX_VALUE</tt>.
33       */
34      public static final int largestPrime = Integer.MAX_VALUE; // yes, it is
35                                                                  // prime.
36  
37      /**
38       * The prime number list consists of 11 chunks. Each chunk contains prime
39       * numbers. A chunk starts with a prime P1. The next element is a prime P2.
40       * P2 is the smallest prime for which holds: P2 >= 2*P1. The next element is
41       * P3, for which the same holds with respect to P2, and so on.
42       * 
43       * Chunks are chosen such that for any desired capacity >= 1000 the list
44       * includes a prime number <= desired capacity * 1.11 (11%). For any desired
45       * capacity >= 200 the list includes a prime number <= desired capacity *
46       * 1.16 (16%). For any desired capacity >= 16 the list includes a prime
47       * number <= desired capacity * 1.21 (21%).
48       * 
49       * Therefore, primes can be retrieved which are quite close to any desired
50       * capacity, which in turn avoids wasting memory. For example, the list
51       * includes 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081. So if
52       * you need a prime >= 1040, you will find a prime <= 1040*1.11=1154.
53       * 
54       * Chunks are chosen such that they are optimized for a hashtable
55       * growthfactor of 2.0; If your hashtable has such a growthfactor then,
56       * after initially "rounding to a prime" upon hashtable construction, it
57       * will later expand to prime capacities such that there exist no better
58       * primes.
59       * 
60       * In total these are about 32*10=320 numbers -> 1 KB of static memory
61       * needed. If you are stingy, then delete every second or fourth chunk.
62       */
63      private static final int[] primeCapacities = {
64          // chunk #0
65          largestPrime,
66  
67          // chunk #1
68          5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717,
69          51437, 102877, 205759, 411527, 823117, 1646237, 3292489, 6584983,
70          13169977, 26339969, 52679969, 105359939, 210719881, 421439783,
71          842879579, 1685759167,
72  
73          // chunk #2
74          433, 877, 1759, 3527, 7057, 14143, 28289, 56591, 113189, 226379,
75          452759, 905551, 1811107, 3622219, 7244441, 14488931, 28977863,
76          57955739, 115911563, 231823147, 463646329, 927292699, 1854585413,
77  
78          // chunk #3
79          953, 1907, 3821, 7643, 15287, 30577, 61169, 122347, 244703, 489407,
80          978821, 1957651, 3915341, 7830701, 15661423, 31322867, 62645741,
81          125291483, 250582987, 501165979, 1002331963, 2004663929,
82  
83          // chunk #4
84          1039, 2081, 4177, 8363, 16729, 33461, 66923, 133853, 267713,
85          535481, 1070981, 2141977, 4283963, 8567929, 17135863, 34271747,
86          68543509, 137087021, 274174111, 548348231, 1096696463,
87  
88          // chunk #5
89          31, 67, 137, 277, 557, 1117, 2237, 4481, 8963, 17929, 35863, 71741,
90          143483, 286973, 573953, 1147921, 2295859, 4591721, 9183457,
91          18366923, 36733847, 73467739, 146935499, 293871013, 587742049,
92          1175484103,
93  
94          // chunk #6
95          599, 1201, 2411, 4831, 9677, 19373, 38747, 77509, 155027, 310081,
96          620171, 1240361, 2480729, 4961459, 9922933, 19845871, 39691759,
97          79383533, 158767069, 317534141, 635068283, 1270136683,
98  
99          // chunk #7
100         311, 631, 1277, 2557, 5119, 10243, 20507, 41017, 82037, 164089,
101         328213, 656429, 1312867, 2625761, 5251529, 10503061, 21006137,
102         42012281, 84024581, 168049163, 336098327, 672196673, 1344393353,
103 
104         // chunk #8
105         3, 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911,
106         43853, 87719, 175447, 350899, 701819, 1403641, 2807303, 5614657,
107         11229331, 22458671, 44917381, 89834777, 179669557, 359339171,
108         718678369, 1437356741,
109 
110         // chunk #9
111         43, 89, 179, 359, 719, 1439, 2879, 5779, 11579, 23159, 46327,
112         92657, 185323, 370661, 741337, 1482707, 2965421, 5930887, 11861791,
113         23723597, 47447201, 94894427, 189788857, 379577741, 759155483,
114         1518310967,
115 
116         // chunk #10
117         379, 761, 1523, 3049, 6101, 12203, 24407, 48817, 97649, 195311,
118         390647, 781301, 1562611, 3125257, 6250537, 12501169, 25002389,
119         50004791, 100009607, 200019221, 400038451, 800076929, 1600153859
120         
121         /*
122          * // some more chunks for the low range [3..1000] //chunk #11
123          * 13,29,59,127,257,521,1049,2099,4201,8419,16843,33703,67409,134837,269683,
124          * 539389,1078787,2157587,4315183,8630387,17260781,34521589,69043189,138086407,
125          * 276172823,552345671,1104691373,
126          * 
127          * //chunk #12 19,41,83,167,337,677,
128          * //1361,2729,5471,10949,21911,43853,87719,175447,350899,
129          * //701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,
130          * //359339171,718678369,1437356741,
131          * 
132          * //chunk #13 53,107,223,449,907,1823,3659,7321,14653,29311,58631,117269,
133          * 234539,469099,938207,1876417,3752839,7505681,15011389,30022781,
134          * 60045577,120091177,240182359,480364727,960729461,1921458943
135          */
136     };
137 
138     static { // initializer
139         // The above prime numbers are formatted for human readability.
140         // To find numbers fast, we sort them once and for all.
141         java.util.Arrays.sort(primeCapacities);
142     }
143 
144     /**
145      * Makes this class non instantiable, but still let's others inherit from
146      * it.
147      */
148     protected PrimeFinder() {
149     }
150 
151     /**
152      * Returns a prime number which is <code>&gt;= desiredCapacity</code> and
153      * very close to <code>desiredCapacity</code> (within 11% if
154      * <code>desiredCapacity &gt;= 1000</code>).
155      * 
156      * @param desiredCapacity
157      *            the capacity desired by the user.
158      * @return the capacity which should be used for a hashtable.
159      */
160     public static int nextPrime(int desiredCapacity) {
161         int i = java.util.Arrays.binarySearch(primeCapacities, desiredCapacity);
162         if (i < 0) {
163             // desired capacity not found, choose next prime greater than
164             // desired capacity
165             i = -i - 1; // remember the semantics of binarySearch...
166         }
167         return primeCapacities[i];
168     }
169 
170 } // end of class PrimeFinder
171
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags