QuickCppLib 0.10
Eliminate all the tedious hassle when making state-of-the-art C++ 14 - 23 libraries!
Loading...
Searching...
No Matches
Namespaces | Functions
quickcpplib::_xxx::algorithm::prime_modulus Namespace Reference

Namespaces

namespace  detail
 

Functions

constexpr uint64_t twos_power_prime (size_t power) noexcept
 Returns a constexpr prime just under a twos power e.g. for 8, you get 251, which is the prime just below (1<<8) = 256. Very handy for hash tables.
 
template<class T >
constexpr T prime_modulus (T v, uint32_t power)
 Return the modulus of a number by the prime just below a twos power. Implemented as a fixed jump table, so the compiler can avoid the CPU division opcode, which still costs 40-90 CPU cycles, and excludes all CPU level parallelism.
 

Function Documentation

◆ twos_power_prime()

constexpr uint64_t quickcpplib::_xxx::algorithm::prime_modulus::twos_power_prime ( size_t  power)
inlineconstexprnoexcept

Returns a constexpr prime just under a twos power e.g. for 8, you get 251, which is the prime just below (1<<8) = 256. Very handy for hash tables.

40 {
41 // Primes come from https://primes.utm.edu/lists/2small/0bit.html
42 // There is a fascinatingly close relationship between powers of two and prime numbers,
43 // as is obvious from the table below. See https://en.wikipedia.org/wiki/Mersenne_prime/.
44 switch(power)
45 {
46 case 0:
47 return 1;
48 case 1:
49 return 2;
50 case 2:
51 return (1ULL << 2) - 1;
52 case 3:
53 return (1ULL << 3) - 1;
54 case 4:
55 return (1ULL << 4) - 3;
56 case 5:
57 return (1ULL << 5) - 1;
58 case 6:
59 return (1ULL << 6) - 3;
60 case 7:
61 return (1ULL << 7) - 1;
62 case 8:
63 return (1ULL << 8) - 5;
64 case 9:
65 return (1ULL << 9) - 3;
66 case 10:
67 return (1ULL << 10) - 3;
68 case 11:
69 return (1ULL << 11) - 9;
70 case 12:
71 return (1ULL << 12) - 3;
72 case 13:
73 return (1ULL << 13) - 1;
74 case 14:
75 return (1ULL << 14) - 3;
76 case 15:
77 return (1ULL << 15) - 19;
78 case 16:
79 return (1ULL << 16) - 15; //
80 case 17:
81 return (1ULL << 17) - 1;
82 case 18:
83 return (1ULL << 18) - 5;
84 case 19:
85 return (1ULL << 19) - 1;
86 case 20:
87 return (1ULL << 20) - 3;
88 case 21:
89 return (1ULL << 21) - 9;
90 case 22:
91 return (1ULL << 22) - 3;
92 case 23:
93 return (1ULL << 23) - 15;
94 case 24:
95 return (1ULL << 24) - 3;
96 case 25:
97 return (1ULL << 25) - 39;
98 case 26:
99 return (1ULL << 26) - 5;
100 case 27:
101 return (1ULL << 27) - 39;
102 case 28:
103 return (1ULL << 28) - 57;
104 case 29:
105 return (1ULL << 29) - 3;
106 case 30:
107 return (1ULL << 30) - 35;
108 case 31:
109 return (1ULL << 31) - 1; //
110 case 32:
111 return (1ULL << 32) - 5;
112 case 33:
113 return (1ULL << 33) - 9;
114 case 34:
115 return (1ULL << 34) - 41;
116 case 35:
117 return (1ULL << 35) - 31;
118 case 36:
119 return (1ULL << 36) - 5;
120 case 37:
121 return (1ULL << 37) - 25;
122 case 38:
123 return (1ULL << 38) - 45;
124 case 39:
125 return (1ULL << 39) - 7;
126 case 40:
127 return (1ULL << 40) - 87;
128 case 41:
129 return (1ULL << 41) - 21;
130 case 42:
131 return (1ULL << 42) - 11;
132 case 43:
133 return (1ULL << 43) - 57;
134 case 44:
135 return (1ULL << 44) - 17;
136 case 45:
137 return (1ULL << 45) - 55;
138 case 46:
139 return (1ULL << 46) - 21;
140 case 47:
141 return (1ULL << 47) - 115;
142 case 48:
143 return (1ULL << 48) - 59; //
144 case 49:
145 return (1ULL << 49) - 81;
146 case 50:
147 return (1ULL << 50) - 27;
148 case 51:
149 return (1ULL << 51) - 129;
150 case 52:
151 return (1ULL << 52) - 47;
152 case 53:
153 return (1ULL << 53) - 111;
154 case 54:
155 return (1ULL << 54) - 33;
156 case 55:
157 return (1ULL << 55) - 55;
158 case 56:
159 return (1ULL << 56) - 5;
160 case 57:
161 return (1ULL << 57) - 13;
162 case 58:
163 return (1ULL << 58) - 27;
164 case 59:
165 return (1ULL << 59) - 55;
166 case 60:
167 return (1ULL << 60) - 93;
168 case 61:
169 return (1ULL << 61) - 1;
170 case 62:
171 return (1ULL << 62) - 57;
172 case 63:
173 return (1ULL << 63) - 25;
174 case 64:
175 return (0xffffffffffffffffULL - 58); //(1ULL << 64) - 59
176 default:
177 return 0;
178 }
179 }

◆ prime_modulus()

template<class T >
constexpr T quickcpplib::_xxx::algorithm::prime_modulus::prime_modulus ( T  v,
uint32_t  power 
)
inlineconstexpr

Return the modulus of a number by the prime just below a twos power. Implemented as a fixed jump table, so the compiler can avoid the CPU division opcode, which still costs 40-90 CPU cycles, and excludes all CPU level parallelism.

Example: prime_modulus(1234, 8) is 1234 % 251 = 230. 251 is the next prime number below (1<<8) = 256.

194 {
195 using detail::mod;
196 switch(power)
197 {
198 case 0:
199 return mod<0>(v);
200 case 1:
201 return mod<1>(v);
202 case 2:
203 return mod<2>(v);
204 case 3:
205 return mod<3>(v);
206 case 4:
207 return mod<4>(v);
208 case 5:
209 return mod<5>(v);
210 case 6:
211 return mod<6>(v);
212 case 7:
213 return mod<7>(v);
214 case 8:
215 return mod<8>(v);
216 case 9:
217 return mod<9>(v);
218 case 10:
219 return mod<10>(v);
220 case 11:
221 return mod<11>(v);
222 case 12:
223 return mod<12>(v);
224 case 13:
225 return mod<13>(v);
226 case 14:
227 return mod<14>(v);
228 case 15:
229 return mod<15>(v);
230 case 16:
231 return mod<16>(v);
232 case 17:
233 return mod<17>(v);
234 case 18:
235 return mod<18>(v);
236 case 19:
237 return mod<19>(v);
238 case 20:
239 return mod<20>(v);
240 case 21:
241 return mod<21>(v);
242 case 22:
243 return mod<22>(v);
244 case 23:
245 return mod<23>(v);
246 case 24:
247 return mod<24>(v);
248 case 25:
249 return mod<25>(v);
250 case 26:
251 return mod<26>(v);
252 case 27:
253 return mod<27>(v);
254 case 28:
255 return mod<28>(v);
256 case 29:
257 return mod<29>(v);
258 case 30:
259 return mod<30>(v);
260 case 31:
261 return mod<31>(v);
262 case 32:
263 return mod<32>(v);
264 case 33:
265 return mod<33>(v);
266 case 34:
267 return mod<34>(v);
268 case 35:
269 return mod<35>(v);
270 case 36:
271 return mod<36>(v);
272 case 37:
273 return mod<37>(v);
274 case 38:
275 return mod<38>(v);
276 case 39:
277 return mod<39>(v);
278 case 40:
279 return mod<40>(v);
280 case 41:
281 return mod<41>(v);
282 case 42:
283 return mod<42>(v);
284 case 43:
285 return mod<43>(v);
286 case 44:
287 return mod<44>(v);
288 case 45:
289 return mod<45>(v);
290 case 46:
291 return mod<46>(v);
292 case 47:
293 return mod<47>(v);
294 case 48:
295 return mod<48>(v);
296 case 49:
297 return mod<49>(v);
298 case 50:
299 return mod<50>(v);
300 case 51:
301 return mod<51>(v);
302 case 52:
303 return mod<52>(v);
304 case 53:
305 return mod<53>(v);
306 case 54:
307 return mod<54>(v);
308 case 55:
309 return mod<55>(v);
310 case 56:
311 return mod<56>(v);
312 case 57:
313 return mod<57>(v);
314 case 58:
315 return mod<58>(v);
316 case 59:
317 return mod<59>(v);
318 case 60:
319 return mod<60>(v);
320 case 61:
321 return mod<61>(v);
322 case 62:
323 return mod<62>(v);
324 case 63:
325 return mod<63>(v);
326 case 64:
327 return mod<64>(v);
328 default:
329 return 0;
330 }
331 }