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

Namespaces

namespace  detail

Functions

constexpr uint64_t twos_power_prime (std::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()

uint64_t quickcpplib::_xxx::algorithm::prime_modulus::twos_power_prime ( std::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.

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

◆ prime_modulus()

template<class T>
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.

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