001 /*
002 // $Id: //open/mondrian/src/main/mondrian/util/PrimeFinder.java#5 $
003 // This software is subject to the terms of the Common Public License
004 // Agreement, available at the following URL:
005 // http://www.opensource.org/licenses/cpl.html.
006 // Copyright (C) 2007-2008 Julian Hyde and others
007 // All Rights Reserved.
008 // You must accept the terms of that agreement to use this software.
009 */
010
011 // Copyright (c) 1999-2007 CERN - European Organization for Nuclear Research.
012 // Permission to use, copy, modify, distribute and sell this software
013 // and its documentation for any purpose is hereby granted without fee,
014 // provided that the above copyright notice appear in all copies and
015 // that both that copyright notice and this permission notice appear in
016 // supporting documentation. CERN makes no representations about the
017 // suitability of this software for any purpose. It is provided "as is"
018 // without expressed or implied warranty.
019
020 // Created from package cern.colt.map by Richard Emberson, 2007/1/23.
021 // For the source to the Colt project, go to:
022 // http://dsd.lbl.gov/~hoschek/colt/
023
024
025 package mondrian.util;
026
027 import java.util.Arrays;
028 import java.io.PrintWriter;
029
030 /**
031 * Not of interest for users; only for implementors of hashtables.
032 * Used to keep hash table capacities prime numbers.
033 *
034 * <p>
035 * Choosing prime numbers as hash table capacities is a good idea to keep
036 * them working fast, particularly under hash table expansions.
037 * <p>
038 * However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to
039 * keep capacities prime.
040 * This class provides efficient means to choose prime capacities.
041 * <p>
042 * Choosing a prime is <tt>O(log 300)</tt> (binary search in a list of
043 * 300 int's).
044 * Memory requirements: 1 KB static memory.
045 *
046 * @author wolfgang.hoschek@cern.ch
047 * @version 1.0, 09/24/99
048 */
049 final class PrimeFinder {
050 /**
051 * The largest prime this class can generate; currently equal to
052 * <tt>Integer.MAX_VALUE</tt>.
053 * yes, it is prime.
054 */
055 public static final int largestPrime = Integer.MAX_VALUE;
056
057 /**
058 * The prime number list consists of 11 chunks.
059 * Each chunk contains prime numbers.
060 * A chunk starts with a prime P1. The next element is a prime P2. P2
061 * is the smallest prime for which holds: P2 >= 2*P1.
062 * The next element is P3, for which the same holds with respect to P2,
063 * and so on.
064 *
065 * Chunks are chosen such that for any desired capacity >= 1000
066 * the list includes a prime number <= desired capacity * 1.11 (11%).
067 * For any desired capacity >= 200
068 * the list includes a prime number <= desired capacity * 1.16 (16%).
069 * For any desired capacity >= 16
070 * the list includes a prime number <= desired capacity * 1.21 (21%).
071 *
072 * Therefore, primes can be retrieved which are quite close to any desired
073 * capacity, which in turn avoids wasting memory.
074 * For example, the list includes
075 * 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
076 * So if you need a prime >= 1040, you will find a prime <= 1040*1.11=1154.
077 *
078 * Chunks are chosen such that they are optimized for a hashtable
079 * growthfactor of 2.0;
080 * If your hashtable has such a growthfactor then,
081 * after initially "rounding to a prime" upon hashtable construction,
082 * it will later expand to prime capacities such that there exist no
083 * better primes.
084 *
085 * In total these are about 32*10=320 numbers -> 1 KB of static memory
086 * needed.
087 * If you are stingy, then delete every second or fourth chunk.
088 */
089
090 private static final int[] primeCapacities = {
091 //chunk #0
092 largestPrime,
093
094 //chunk #1
095 5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,
096 411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939,
097 210719881,421439783,842879579,1685759167,
098
099 //chunk #2
100 433,877,1759,3527,7057,14143,28289,56591,113189,226379,452759,905551,1811107,
101 3622219,7244441,14488931,28977863,57955739,115911563,231823147,463646329,927292699,
102 1854585413,
103
104 //chunk #3
105 953,1907,3821,7643,15287,30577,61169,122347,244703,489407,978821,1957651,3915341,
106 7830701,15661423,31322867,62645741,125291483,250582987,501165979,1002331963,
107 2004663929,
108
109 //chunk #4
110 1039,2081,4177,8363,16729,33461,66923,133853,267713,535481,1070981,2141977,4283963,
111 8567929,17135863,34271747,68543509,137087021,274174111,548348231,1096696463,
112
113 //chunk #5
114 31,67,137,277,557,1117,2237,4481,8963,17929,35863,71741,143483,286973,573953,
115 1147921,2295859,4591721,9183457,18366923,36733847,73467739,146935499,293871013,
116 587742049,1175484103,
117
118 //chunk #6
119 599,1201,2411,4831,9677,19373,38747,77509,155027,310081,620171,1240361,2480729,
120 4961459,9922933,19845871,39691759,79383533,158767069,317534141,635068283,1270136683,
121
122 //chunk #7
123 311,631,1277,2557,5119,10243,20507,41017,82037,164089,328213,656429,1312867,
124 2625761,5251529,10503061,21006137,42012281,84024581,168049163,336098327,672196673,
125 1344393353,
126
127 //chunk #8
128 3,7,17,37,79,163,331,673,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 #9
133 43,89,179,359,719,1439,2879,5779,11579,23159,46327,92657,185323,370661,741337,
134 1482707,2965421,5930887,11861791,23723597,47447201,94894427,189788857,379577741,
135 759155483,1518310967,
136
137 //chunk #10
138 379,761,1523,3049,6101,12203,24407,48817,97649,195311,390647,781301,1562611,
139 3125257,6250537,12501169,25002389,50004791,100009607,200019221,400038451,800076929,
140 1600153859
141 /*
142 // some more chunks for the low range [3..1000]
143 //chunk #11
144 13,29,59,127,257,521,1049,2099,4201,8419,16843,33703,67409,134837,269683,
145 539389,1078787,2157587,4315183,8630387,17260781,34521589,69043189,138086407,
146 276172823,552345671,1104691373,
147
148 //chunk #12
149 19,41,83,167,337,677,
150 //1361,2729,5471,10949,21911,43853,87719,175447,350899,
151 //701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,
152 //359339171,718678369,1437356741,
153
154 //chunk #13
155 53,107,223,449,907,1823,3659,7321,14653,29311,58631,117269,
156 234539,469099,938207,1876417,3752839,7505681,15011389,30022781,
157 60045577,120091177,240182359,480364727,960729461,1921458943
158 */
159 };
160
161
162 static { //initializer
163 // The above prime numbers are formatted for human readability.
164 // To find numbers fast, we sort them once and for all.
165 Arrays.sort(primeCapacities);
166 }
167
168 /**
169 * Makes this class non instantiable.
170 */
171 private PrimeFinder() {
172 }
173
174 /**
175 * Returns a prime number which is <code>>= desiredCapacity</code> and
176 * very close to <code>desiredCapacity</code> (within 11% if
177 * <code>desiredCapacity >= 1000</code>).
178 * @param desiredCapacity the capacity desired by the user.
179 * @return the capacity which should be used for a hashtable.
180 */
181 public static int nextPrime(int desiredCapacity) {
182 int i = Arrays.binarySearch(primeCapacities, desiredCapacity);
183 if (i < 0) {
184 // desired capacity not found, choose next prime greater
185 // than desired capacity
186 i = -i -1; // remember the semantics of binarySearch...
187 }
188 return primeCapacities[i];
189 }
190
191 /**
192 * Tests correctness. Try
193 * from=1000, to=10000
194 * from=200, to=1000
195 * from=16, to=1000
196 * from=1000, to=Integer.MAX_VALUE
197 */
198 protected static void main(String args[]) {
199 int from = Integer.parseInt(args[0]);
200 int to = Integer.parseInt(args[1]);
201
202 statistics(from,to,new PrintWriter(System.out));
203 }
204
205 /**
206 * Tests correctness.
207 */
208 protected static void statistics(int from, int to, PrintWriter pw) {
209 // check that primes contain no accidental errors
210 for (int i = 0; i < primeCapacities.length - 1; i++) {
211 if (primeCapacities[i] >= primeCapacities[i + 1]) {
212 throw new RuntimeException("primes are unsorted or contain duplicates; detected at " + i + "@" + primeCapacities[i]);
213 }
214 }
215
216 double accDeviation = 0.0;
217 double maxDeviation = - 1.0;
218
219 for (int i = from; i <= to; i++) {
220 int primeCapacity = nextPrime(i);
221 //System.out.println(primeCapacity);
222 double deviation = (primeCapacity - i) / (double)i;
223
224 if (deviation > maxDeviation) {
225 maxDeviation = deviation;
226 pw.println("new maxdev @" + i + "@dev=" + maxDeviation);
227 }
228
229 accDeviation += deviation;
230 }
231 long width = 1 + (long)to - (long)from;
232
233 double meanDeviation = accDeviation / width;
234 pw.println("Statistics for [" + from + "," + to + "] are as follows");
235 pw.println("meanDeviation = " + (float)meanDeviation * 100 + " %");
236 pw.println("maxDeviation = " + (float)maxDeviation * 100 + " %");
237 }
238 }
239
240 // End PrimeFinder.java