KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > mondrian > util > PrimeFinder


1 /*
2 // $Id: //open/mondrian/src/main/mondrian/util/PrimeFinder.java#2 $
3 // This software is subject to the terms of the Common Public License
4 // Agreement, available at the following URL:
5 // http://www.opensource.org/licenses/cpl.html.
6 // Copyright (C) 2007-2007 Julian Hyde and others
7 // All Rights Reserved.
8 // You must accept the terms of that agreement to use this software.
9 */
10
11 // Copyright (c) 1999 CERN - European Organization for Nuclear Research.
12 // Permission to use, copy, modify, distribute and sell this software
13 // and its documentation for any purpose is hereby granted without fee,
14 // provided that the above copyright notice appear in all copies and
15 // that both that copyright notice and this permission notice appear in
16 // supporting documentation. CERN makes no representations about the
17 // suitability of this software for any purpose. It is provided "as is"
18 // without expressed or implied warranty.
19
20 // Created from package cern.colt.map by Richard Emberson, 2007/1/23.
21 // For the source to the Colt project, go to:
22 // http://dsd.lbl.gov/~hoschek/colt/
23
24
25 package mondrian.util;
26
27 import java.util.Arrays JavaDoc;
28 import java.io.PrintWriter JavaDoc;
29
30 /**
31  * Not of interest for users; only for implementors of hashtables.
32  * Used to keep hash table capacities prime numbers.
33  *
34  * <p>
35  * Choosing prime numbers as hash table capacities is a good idea to keep
36  * them working fast, particularly under hash table expansions.
37  * <p>
38  * However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to
39  * keep capacities prime.
40  * This class provides efficient means to choose prime capacities.
41  * <p>
42  * Choosing a prime is <tt>O(log 300)</tt> (binary search in a list of
43  * 300 int's).
44  * Memory requirements: 1 KB static memory.
45  *
46  * @author wolfgang.hoschek@cern.ch
47  * @version 1.0, 09/24/99
48  */
49 final class PrimeFinder {
50     /**
51      * The largest prime this class can generate; currently equal to
52      * <tt>Integer.MAX_VALUE</tt>.
53      * yes, it is prime.
54      */
55     public static final int largestPrime = Integer.MAX_VALUE;
56
57     /**
58      * The prime number list consists of 11 chunks.
59      * Each chunk contains prime numbers.
60      * A chunk starts with a prime P1. The next element is a prime P2. P2
61      * is the smallest prime for which holds: P2 >= 2*P1.
62      * The next element is P3, for which the same holds with respect to P2,
63      * and so on.
64      *
65      * Chunks are chosen such that for any desired capacity >= 1000
66      * the list includes a prime number <= desired capacity * 1.11 (11%).
67      * For any desired capacity >= 200
68      * the list includes a prime number <= desired capacity * 1.16 (16%).
69      * For any desired capacity >= 16
70      * the list includes a prime number <= desired capacity * 1.21 (21%).
71      *
72      * Therefore, primes can be retrieved which are quite close to any desired
73      * capacity, which in turn avoids wasting memory.
74      * For example, the list includes
75      * 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
76      * So if you need a prime >= 1040, you will find a prime <= 1040*1.11=1154.
77      *
78      * Chunks are chosen such that they are optimized for a hashtable
79      * growthfactor of 2.0;
80      * If your hashtable has such a growthfactor then,
81      * after initially "rounding to a prime" upon hashtable construction,
82      * it will later expand to prime capacities such that there exist no
83      * better primes.
84      *
85      * In total these are about 32*10=320 numbers -> 1 KB of static memory
86      * needed.
87      * If you are stingy, then delete every second or fourth chunk.
88      */
89     
90     private static final int[] primeCapacities = {
91         //chunk #0
92 largestPrime,
93         
94         //chunk #1
95 5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,
96         411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939,
97         210719881,421439783,842879579,1685759167,
98           
99         //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      * Returns a prime number which is <code>&gt;= desiredCapacity</code> and
175      * very close to <code>desiredCapacity</code> (within 11% if
176      * <code>desiredCapacity &gt;= 1000</code>).
177      * @param desiredCapacity the capacity desired by the user.
178      * @return the capacity which should be used for a hashtable.
179      */
180     public static int nextPrime(int desiredCapacity) {
181         int i = Arrays.binarySearch(primeCapacities, desiredCapacity);
182         if (i < 0) {
183             // desired capacity not found, choose next prime greater
184 // than desired capacity
185 i = -i -1; // remember the semantics of binarySearch...
186 }
187         return primeCapacities[i];
188     }
189
190     /**
191      * Tests correctness. Try
192      * from=1000, to=10000
193      * from=200, to=1000
194      * from=16, to=1000
195      * from=1000, to=Integer.MAX_VALUE
196      */
197     protected static void main(String JavaDoc args[]) {
198         int from = Integer.parseInt(args[0]);
199         int to = Integer.parseInt(args[1]);
200         
201         statistics(from,to,new PrintWriter JavaDoc(System.out));
202     }
203
204     /**
205      * Tests correctness.
206      */
207     protected static void statistics(int from, int to, PrintWriter JavaDoc pw) {
208         // check that primes contain no accidental errors
209 for (int i=0; i<primeCapacities.length-1; i++) {
210             if (primeCapacities[i] >= primeCapacities[i+1]) {
211                 throw new RuntimeException JavaDoc("primes are unsorted or contain duplicates; detected at "+i+"@"+primeCapacities[i]);
212             }
213         }
214         
215         double accDeviation = 0.0;
216         double maxDeviation = - 1.0;
217
218         for (int i=from; i<=to; i++) {
219             int primeCapacity = nextPrime(i);
220             //System.out.println(primeCapacity);
221 double deviation = (primeCapacity - i) / (double)i;
222             
223             if (deviation > maxDeviation) {
224                 maxDeviation = deviation;
225                 pw.println("new maxdev @"+i+"@dev="+maxDeviation);
226             }
227
228             accDeviation += deviation;
229         }
230         long width = 1 + (long)to - (long)from;
231         
232         double meanDeviation = accDeviation/width;
233         pw.println("Statistics for ["+ from + ","+to+"] are as follows");
234         pw.println("meanDeviation = "+(float)meanDeviation*100+" %");
235         pw.println("maxDeviation = "+(float)maxDeviation*100+" %");
236     }
237 }
238
239 // End PrimeFinder.java
240
Popular Tags