Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Tpetra_Details_Hash.cpp
1 /*
2 // @HEADER
3 // ***********************************************************************
4 //
5 // Tpetra: Templated Linear Algebra Services Package
6 // Copyright (2008) Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
39 //
40 // ************************************************************************
41 // @HEADER
42 */
43 
44 #include "Tpetra_Details_Hash.hpp"
45 
46 namespace Tpetra {
47 namespace Details {
48 namespace Impl {
49 
50 int getRecommendedSizeInt (const int size)
51 {
52  // A large list of prime numbers.
53  // Based on a recommendation by Andres Valloud in hash forums.
54  // There are only enough primes here so that between any number N and 2*N,
55  // there will be at least about 8 to choose from (except the first 10).
56  // This is a balance between a small list of primes, and getting a
57  // collection size that doesn't waste too much space. In addition,
58  // the primes in this table were chosen so that they do not divide
59  // 256^k +- a, for 1<=k<=8, and -32<=a<=32. This is so that
60  // using them as a modulo will not have a tendency to just throw away
61  // the most significant bits of the object's hash. The primes (except the
62  // first ten) or not close to any power of two to avoid aliasing
63  // between hash functions based on bit manipulation and the moduli.
64  int primes [ ] = {
65  3, 7, 13, 23, 53, 97, 193, 389, 769, 1543,
66  2237, 2423, 2617, 2797, 2999, 3167, 3359, 3539,
67  3727, 3911, 4441 , 4787 , 5119 , 5471 , 5801 , 6143 , 6521 , 6827
68  , 7177 , 7517 , 7853 , 8887 , 9587 , 10243 , 10937 , 11617 , 12289
69  , 12967 , 13649 , 14341 , 15013 , 15727
70  , 17749 , 19121 , 20479 , 21859 , 23209 , 24593 , 25939 , 27329
71  , 28669 , 30047 , 31469 , 35507 , 38231 , 40961 , 43711 , 46439
72  , 49157 , 51893 , 54617 , 57347 , 60077 , 62801 , 70583 , 75619
73  , 80669 , 85703 , 90749 , 95783 , 100823 , 105871 , 110909 , 115963
74  , 120997 , 126031 , 141157 , 151237 , 161323 , 171401 , 181499 , 191579
75  , 201653 , 211741 , 221813 , 231893 , 241979 , 252079
76  , 282311 , 302483 , 322649 , 342803 , 362969 , 383143 , 403301 , 423457
77  , 443629 , 463787 , 483953 , 504121 , 564617 , 604949 , 645313 , 685609
78  , 725939 , 766273 , 806609 , 846931 , 887261 , 927587 , 967919 , 1008239
79  , 1123477 , 1198397 , 1273289 , 1348177 , 1423067 , 1497983 , 1572869
80  , 1647761 , 1722667 , 1797581 , 1872461 , 1947359 , 2022253
81  , 2246953 , 2396759 , 2546543 , 2696363 , 2846161 , 2995973 , 3145739
82  , 3295541 , 3445357 , 3595117 , 3744941 , 3894707 , 4044503
83  , 4493921 , 4793501 , 5093089 , 5392679 , 5692279 , 5991883 , 6291469
84  , 6591059 , 6890641 , 7190243 , 7489829 , 7789447 , 8089033
85  , 8987807 , 9586981 , 10186177 , 10785371 , 11384539 , 11983729
86  , 12582917 , 13182109 , 13781291 , 14380469 , 14979667 , 15578861
87  , 16178053 , 17895707 , 19014187 , 20132683 , 21251141 , 22369661
88  , 23488103 , 24606583 , 25725083 , 26843549 , 27962027 , 29080529
89  , 30198989 , 31317469 , 32435981 , 35791397 , 38028379 , 40265327
90  , 42502283 , 44739259 , 46976221 , 49213237 , 51450131 , 53687099
91  , 55924061 , 58161041 , 60397993 , 62634959 , 64871921
92  , 71582857 , 76056727 , 80530643 , 85004567 , 89478503 , 93952427
93  , 98426347 , 102900263 , 107374217 , 111848111 , 116322053 , 120795971
94  , 125269877 , 129743807 , 143165587 , 152113427 , 161061283 , 170009141
95  , 178956983 , 187904819 , 196852693 , 205800547 , 214748383 , 223696237
96  , 232644089 , 241591943 , 250539763 , 259487603 , 268435399 };
97 
98  int hsize = primes[220] ;
99  for (int i = 0; i < 221; ++i) {
100  if (size <= primes[i]) {
101  hsize = primes[i];
102  break;
103  }
104  }
105  return hsize;
106 }
107 
108 } // namespace Impl
109 } // namespace Details
110 } // namespace Tpetra