bundles/org.simantics.scenegraph/src/gnu/trove/PrimeFinder.java

   1 //   Copyright (c) 1999 CERN - European Organization for Nuclear Research.
   2
   3 //   Permission to use, copy, modify, distribute and sell this software
   4 //   and its documentation for any purpose is hereby granted without fee,
   5 //   provided that the above copyright notice appear in all copies and
   6 //   that both that copyright notice and this permission notice appear in
   7 //   supporting documentation. CERN makes no representations about the
   8 //   suitability of this software for any purpose. It is provided "as is"
   9 //   without expressed or implied warranty.
  10 package gnu.trove;
  11
  12 import java.util.Arrays;
  13
  14 /*
  15  * Modified for Trove to use the java.util.Arrays sort/search
  16  * algorithms instead of those provided with colt.
  17  */
  18
  19 /**
  20  * Used to keep hash table capacities prime numbers.
  21  * Not of interest for users; only for implementors of hashtables.
  22  *
  23  * <p>Choosing prime numbers as hash table capacities is a good idea
  24  * to keep them working fast, particularly under hash table
  25  * expansions.
  26  *
  27  * <p>However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to
  28  * keep capacities prime.  This class provides efficient means to
  29  * choose prime capacities.
  30  *
  31  * <p>Choosing a prime is <tt>O(log 300)</tt> (binary search in a list
  32  * of 300 ints).  Memory requirements: 1 KB static memory.
  33  *
  34  * @author wolfgang.hoschek@cern.ch
  35  * @version 1.0, 09/24/99
  36  */
  37 public final class PrimeFinder {
  38     /**
  39      * The largest prime this class can generate; currently equal to
  40      * <tt>Integer.MAX_VALUE</tt>.
  41      */
  42     public static final int largestPrime = Integer.MAX_VALUE; //yes, it is prime.
  43
  44     /**
  45      * The prime number list consists of 11 chunks.
  46      *
  47      * Each chunk contains prime numbers.
  48      *
  49      * A chunk starts with a prime P1. The next element is a prime
  50      * P2. P2 is the smallest prime for which holds: P2 >= 2*P1.
  51      *
  52      * The next element is P3, for which the same holds with respect
  53      * to P2, and so on.
  54      *
  55      * Chunks are chosen such that for any desired capacity >= 1000
  56      * the list includes a prime number <= desired capacity * 1.11.
  57      *
  58      * Therefore, primes can be retrieved which are quite close to any
  59      * desired capacity, which in turn avoids wasting memory.
  60      *
  61      * For example, the list includes
  62      * 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
  63      *
  64      * So if you need a prime >= 1040, you will find a prime <=
  65      * 1040*1.11=1154.
  66      *
  67      * Chunks are chosen such that they are optimized for a hashtable
  68      * growthfactor of 2.0;
  69      *
  70      * If your hashtable has such a growthfactor then, after initially
  71      * "rounding to a prime" upon hashtable construction, it will
  72      * later expand to prime capacities such that there exist no
  73      * better primes.
  74      *
  75      * In total these are about 32*10=320 numbers -> 1 KB of static
  76      * memory needed.
  77      *
  78      * If you are stingy, then delete every second or fourth chunk.
  79      */
  80
  81     private static final int[] primeCapacities = {
  82         //chunk #0
  83         largestPrime,
  84
  85         //chunk #1
  86         5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,
  87         411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939,
  88         210719881,421439783,842879579,1685759167,
  89
  90         //chunk #2
  91         433,877,1759,3527,7057,14143,28289,56591,113189,226379,452759,905551,1811107,
  92         3622219,7244441,14488931,28977863,57955739,115911563,231823147,463646329,927292699,
  93         1854585413,
  94
  95         //chunk #3
  96         953,1907,3821,7643,15287,30577,61169,122347,244703,489407,978821,1957651,3915341,
  97         7830701,15661423,31322867,62645741,125291483,250582987,501165979,1002331963,
  98         2004663929,
  99
 100         //chunk #4
 101         1039,2081,4177,8363,16729,33461,66923,133853,267713,535481,1070981,2141977,4283963,
 102         8567929,17135863,34271747,68543509,137087021,274174111,548348231,1096696463,
 103
 104         //chunk #5
 105         31,67,137,277,557,1117,2237,4481,8963,17929,35863,71741,143483,286973,573953,
 106         1147921,2295859,4591721,9183457,18366923,36733847,73467739,146935499,293871013,
 107         587742049,1175484103,
 108
 109         //chunk #6
 110         599,1201,2411,4831,9677,19373,38747,77509,155027,310081,620171,1240361,2480729,
 111         4961459,9922933,19845871,39691759,79383533,158767069,317534141,635068283,1270136683,
 112
 113         //chunk #7
 114         311,631,1277,2557,5119,10243,20507,41017,82037,164089,328213,656429,1312867,
 115         2625761,5251529,10503061,21006137,42012281,84024581,168049163,336098327,672196673,
 116         1344393353,
 117
 118         //chunk #8
 119         3,7,17,37,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899,
 120         701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,
 121         359339171,718678369,1437356741,
 122
 123         //chunk #9
 124         43,89,179,359,719,1439,2879,5779,11579,23159,46327,92657,185323,370661,741337,
 125         1482707,2965421,5930887,11861791,23723597,47447201,94894427,189788857,379577741,
 126         759155483,1518310967,
 127
 128         //chunk #10
 129         379,761,1523,3049,6101,12203,24407,48817,97649,195311,390647,781301,1562611,
 130         3125257,6250537,12501169,25002389,50004791,100009607,200019221,400038451,800076929,
 131         1600153859
 132     };
 133
 134     static { //initializer
 135         // The above prime numbers are formatted for human readability.
 136         // To find numbers fast, we sort them once and for all.
 137
 138         Arrays.sort(primeCapacities);
 139     }
 140
 141     /**
 142      * Returns a prime number which is <code>&gt;= desiredCapacity</code>
 143      * and very close to <code>desiredCapacity</code> (within 11% if
 144      * <code>desiredCapacity &gt;= 1000</code>).
 145      *
 146      * @param desiredCapacity the capacity desired by the user.
 147      * @return the capacity which should be used for a hashtable.
 148      */
 149     public static final int nextPrime(int desiredCapacity) {
 150         int i = Arrays.binarySearch(primeCapacities, desiredCapacity);
 151         if (i<0) {
 152             // desired capacity not found, choose next prime greater
 153             // than desired capacity
 154             i = -i -1; // remember the semantics of binarySearch...
 155         }
 156         return primeCapacities[i];
 157     }
 158 }