lib/Math/Prime/XS.xs

filter: Statementstmt 100% 134 / 134 Branchbran 94.3% 134 / 142 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 97.1% 268 / 276 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Math/Prime/XS.pm ↑ Summary
1 #include "EXTERN.h"
2 #include "perl.h"
3 #include "XSUB.h"
4  
5 #include "ppport.h"
6  
7 #ifdef CHAR_BIT
8 # define BYTE_BITS CHAR_BIT /* limits.h */
9 #else
10 # define BYTE_BITS 8 /* at least 8 bits wide */
11 #endif
12  
13 #define BIT_VECTOR(num) ((num) / 2) /* double space for uneven numbers */
14  
15 #define EVEN_NUM(num) ((num) % 2 == 0)
16  
17 #define NUM_SET(num_entry, var_ptr, num_pos, num_val) \
18 (*num_entry).ptr = var_ptr; \
19 (*num_entry).pos = num_pos; \
20 (*num_entry).val = num_val; \
21  
22 #define NUM_LEN(nums) (sizeof (nums) / sizeof (num_entry))
23  
24 /* ULONG_MAX_IS_ODD_COMPOSITE is true if ULONG_MAX is odd and composite.
25 Checking mod 3 is enough to detect 2^32-1 and 2^64-1 (and other even
26 number of bits). */
27 #define ULONG_MAX_IS_ODD_COMPOSITE \
28 ((ULONG_MAX % 2) == 0 || (ULONG_MAX % 3) == 0)
29  
30 typedef struct {
31 unsigned long **ptr;
32 unsigned int pos;
33 unsigned long val;
34 } num_entry;
35  
36 static void
37 57 store (const num_entry *numbers, unsigned int len, unsigned int *pos)
38 {
39 unsigned int i;
40 164 ▶ for (i = 0; i < len; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < len; i++) 107 57 164
41 {
42 107 unsigned long **p = numbers[i].ptr;
43 107 const unsigned int pos = numbers[i].pos;
44 107 ▶ if (*p)
Branch: 1 branch
BranchTrueFalseTotal
if (*p) 98 9 107
45 {
46 98 Renew (*p, pos + 1, unsigned long);
47 98 Zero (*p + pos, 1, unsigned long);
48 }
49 else
50 9 Newxz (*p, 1, unsigned long);
51 107 (*p)[pos] = numbers[i].val;
52 }
53 57 ▶ if (pos) /* keep it optional */
Branch: 1 branch
BranchTrueFalseTotal
if (pos) /* keep it optional */ 57 0 57
54 57 (*pos)++;
55 57 }
56  
57 MODULE = Math::Prime::XS PACKAGE = Math::Prime::XS
58  
59 bool
60 is_prime (n)
61 unsigned long n
62 PREINIT:
63 /* Bit table of numbers 0 to 31 which are primes. */
64 10109 const unsigned long small_table = (( (1 << 2))
65 | (1 << 3)
66 | (1 << 5)
67 | (1 << 7)
68 | (1 << 11)
69 | (1 << 13)
70 | (1 << 17)
71 | (1 << 19)
72 | (1 << 23)
73 | (1 << 29)
74 | (1 << 31));
75  
76 /* Bit table of the remainders mod 30 which might be primes, ie. which
77 aren't divisible by 2, 3 or 5. */
78 10109 const unsigned long mod_table = ~ (( (1 << 0))
79 | (1 << 2)
80 | (1 << 4)
81 | (1 << 6)
82 | (1 << 8)
83 | (1 << 10)
84 | (1 << 12)
85 | (1 << 14)
86 | (1 << 16)
87 | (1 << 18)
88 | (1 << 20)
89 | (1 << 22)
90 | (1 << 24)
91 | (1 << 26)
92 | (1 << 28)
93 | (1 << 30)
94  
95 | (1 << 3)
96 | (1 << 6)
97 | (1 << 9)
98 | (1 << 12)
99 | (1 << 15)
100 | (1 << 18)
101 | (1 << 21)
102 | (1 << 24)
103 | (1 << 27)
104 | (1 << 30)
105  
106 | (1 << 5)
107 | (1 << 10)
108 | (1 << 15)
109 | (1 << 20)
110 | (1 << 25));
111  
112 INIT:
113 unsigned long i;
114 CODE:
115 {
116 10109 double d = SvNV(ST(0));
117 10109 ▶ if (! (d >= 0 && d <= ULONG_MAX)) {
Branch: 2 branches
BranchTrueFalseTotal
if (! (d >= 0 && d <= ULONG_MAX)) { 10105 4 10109
if (! (d >= 0 && d <= ULONG_MAX)) { 2 10103 10105
118 6 croak ("Cannot isprime() on %g", d);
119 }
120 }
121  
122 10103 ▶ if (n < 32) {
Branch: 1 branch
BranchTrueFalseTotal
if (n < 32) { 64 10039 10103
123 64 RETVAL = (small_table >> n) & 1;
124 } else {
125 10039 RETVAL = 0;
126 10039 ▶ if ((mod_table >> (n%30)) & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ((mod_table >> (n%30)) & 1) { 7365 2674 10039
127 2674 unsigned long limit = (unsigned long) floor(sqrt(n));
128  
129 /* At this point n is not a multiple of 2, 3 or 5, so can skip odd
130 i, and i multiple of 3, and i multiple of 5.
131  
132 For reference, doing all odd i would be 15 out of each 30
133 divisors. Excluding i multiples of 3 reduces to 10 out of 30.
134 Excluding i multiples of 5 reduces to 8 out of 30. */
135  
136 2674 i = 7;
137 for (;;) {
138 4741 ▶ if (n % i == 0) goto done; /* i == 30*k+7 */
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) goto done; /* i == 30*k+7 */ 449 4292 4741
139  
140 4292 ▶ if ((i += 4) > limit) break; /* i == 30*k+11 */
Branch: 1 branch
BranchTrueFalseTotal
if ((i += 4) > limit) break; /* i == 30*k+11 */ 209 4083 4292
141 4083 ▶ if (n % i == 0) goto done;
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) goto done; 263 3820 4083
142  
143 3820 ▶ if ((i += 2) > limit) break; /* i == 30*k+13 */
Branch: 1 branch
BranchTrueFalseTotal
if ((i += 2) > limit) break; /* i == 30*k+13 */ 59 3761 3820
144 3761 ▶ if (n % i == 0) goto done;
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) goto done; 208 3553 3761
145  
146 3553 ▶ if ((i += 4) > limit) break; /* i == 30*k+17 */
Branch: 1 branch
BranchTrueFalseTotal
if ((i += 4) > limit) break; /* i == 30*k+17 */ 142 3411 3553
147 3411 ▶ if (n % i == 0) goto done;
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) goto done; 143 3268 3411
148  
149 3268 ▶ if ((i += 2) > limit) break; /* i == 30*k+19 */
Branch: 1 branch
BranchTrueFalseTotal
if ((i += 2) > limit) break; /* i == 30*k+19 */ 71 3197 3268
150 3197 ▶ if (n % i == 0) goto done;
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) goto done; 103 3094 3197
151  
152 3094 ▶ if ((i += 4) > limit) break; /* i == 30*k+23 */
Branch: 1 branch
BranchTrueFalseTotal
if ((i += 4) > limit) break; /* i == 30*k+23 */ 154 2940 3094
153 2940 ▶ if (n % i == 0) goto done;
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) goto done; 111 2829 2940
154  
155 2829 ▶ if ((i += 6) > limit) break; /* i == 30*k+29 */
Branch: 1 branch
BranchTrueFalseTotal
if ((i += 6) > limit) break; /* i == 30*k+29 */ 239 2590 2829
156 2590 ▶ if (n % i == 0) goto done;
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) goto done; 88 2502 2590
157  
158 2502 ▶ if ((i += 2) > limit) break; /* i == 30*k+1 */
Branch: 1 branch
BranchTrueFalseTotal
if ((i += 2) > limit) break; /* i == 30*k+1 */ 86 2416 2502
159 2416 ▶ if (n % i == 0) goto done;
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) goto done; 77 2339 2416
160  
161 2339 ▶ if ((i += 6) > limit) break; /* back to i == 30*k+7 */
Branch: 1 branch
BranchTrueFalseTotal
if ((i += 6) > limit) break; /* back to i == 30*k+7 */ 272 2067 2339
162 }
163 1232 RETVAL = 1;
164 }
165 }
166 10103 ▶ done:
Branch: 1 branch
BranchTrueFalseTotal
done: 1254 8849 10103
167 ;
168 OUTPUT:
169 RETVAL
170  
171 void
172 xs_mod_primes (number, base)
173 unsigned long number
174 unsigned long base
175 PROTOTYPE: $$
176 INIT:
177 unsigned long i, n;
178 PPCODE:
179 /* For the sqrt(), casting double->ulong probably follows the fpu
180 rounding mode, so might round either up or down. If up then the
181 last trial division may be unnecessary, but not harmful.
182 */
183  
184 /* special case for 2 if it's in range, then can use n+=2 for odd n in
185 the loop */
186 5 ▶ if (base <= 2) {
Branch: 1 branch
BranchTrueFalseTotal
if (base <= 2) { 1 4 5
187 1 base = 3;
188 1 ▶ if (number >= 2) {
Branch: 1 branch
BranchTrueFalseTotal
if (number >= 2) { 1 0 1
189 1 ▶ XPUSHs (sv_2mortal(newSVuv(2)));
Branch: 1 branch
BranchTrueFalseTotal
XPUSHs (sv_2mortal(newSVuv(2))); 0 1 1
190 }
191 }
192  
193 /* next higher odd number, if not odd already */
194 5 base |= 1;
195  
196 /* If number==ULONG_MAX then n<=number is always true and would be an
197 infinite loop. If ULONG_MAX and ULONG_MAX-1 are both composites
198 (which is so for 2^32-1 and 2^64-1) then can stop before them, by
199 shortening "number" to ULONG_MAX-2. If not (some strange ULONG_MAX
200 value) then check for n>=ULONG_MAX-1 below so n+=2 doesn't
201 overflow.
202 */
203 if (ULONG_MAX_IS_ODD_COMPOSITE) {
204 /* usual case of 2^32-1 or 2^64-1 */
205 5 ▶ if (number > ULONG_MAX-2)
Branch: 1 branch
BranchTrueFalseTotal
if (number > ULONG_MAX-2) 1 4 5
206 1 number = ULONG_MAX-2;
207 }
208  
209 76 ▶ for (n = base; n <= number; n += 2)
Branch: 1 branch
BranchTrueFalseTotal
for (n = base; n <= number; n += 2) 71 5 76
210 {
211 71 unsigned long limit = (unsigned long) floor(sqrt(n));
212 161 ▶ for (i = 3; i <= limit; i+=2)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 3; i <= limit; i+=2) 127 34 161
213 {
214 127 ▶ if (n % i == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (n % i == 0) 37 90 127
215 37 goto NEXT_OUTER;
216 }
217 /* (n % 1 == 0) && (n % n == 0) */
218 34 ▶ XPUSHs (sv_2mortal(newSVuv(n)));
Branch: 1 branch
BranchTrueFalseTotal
XPUSHs (sv_2mortal(newSVuv(n))); 0 34 34
219  
220 71 NEXT_OUTER:
221 if (! ULONG_MAX_IS_ODD_COMPOSITE) { /* some unusual ULONG_MAX */
222 if (n >= ULONG_MAX-1)
223 break;
224 }
225 }
226  
227 void
228 xs_sieve_primes (number, base)
229 unsigned long number
230 unsigned long base
231 PROTOTYPE: $$
232 ALIAS:
233 xs_sieve_count_primes = 1
234 INIT:
235 10 unsigned long *composite = NULL;
236 unsigned long i, n;
237 10 unsigned long count = 0;
238 PPCODE:
239 10 const unsigned long square_root = sqrt (number); /* truncates */
240 10 const unsigned int size_bits = sizeof (unsigned long) * BYTE_BITS;
241  
242 10 ▶ Newxz (composite, (BIT_VECTOR (number) / size_bits) + 1, unsigned long);
Branch: 1 branch
BranchTrueFalseTotal
Newxz (composite, (BIT_VECTOR (number) / size_bits) + 1, unsigned long); 0 10 10
243  
244 788 ▶ for (n = 3; n <= square_root; n += 2) /* uneven numbers only */
Branch: 1 branch
BranchTrueFalseTotal
for (n = 3; n <= square_root; n += 2) /* uneven numbers only */ 778 10 788
245 {
246 /* (n * n) - start with square */
247 /* (2 * n) - skip even number */
248 3022079 ▶ for (i = (n * n); i <= number; i += (2 * n))
Branch: 1 branch
BranchTrueFalseTotal
for (i = (n * n); i <= number; i += (2 * n)) 3021301 778 3022079
249 {
250 3021301 const unsigned int bits = BIT_VECTOR (i - 2) % size_bits;
251 3021301 const unsigned int field = BIT_VECTOR (i - 2) / size_bits;
252  
253 3021301 composite[field] |= (unsigned long)1 << bits;
254 }
255 }
256 2010536 ▶ for (n = 2; n <= number; n++)
Branch: 1 branch
BranchTrueFalseTotal
for (n = 2; n <= number; n++) 2010526 10 2010536
257 {
258 2010526 ▶ if (n > 2 && EVEN_NUM (n))
Branch: 2 branches
BranchTrueFalseTotal
if (n > 2 && EVEN_NUM (n)) 2010516 10 2010526
if (n > 2 && EVEN_NUM (n)) 1005257 1005259 2010516
259 1005257 continue;
260 1005269 ▶ else if (!EVEN_NUM (n) && composite[BIT_VECTOR (n - 2) / size_bits] & ((unsigned long)1 << (BIT_VECTOR (n - 2) % size_bits)))
Branch: 2 branches
BranchTrueFalseTotal
else if (!EVEN_NUM (n) && composite[BIT_VECTOR (n - 2) / size_bits] & ((unsigned long)1 << (BIT_VECTOR (n - 2) % size_bits))) 1005259 10 1005269
else if (!EVEN_NUM (n) && composite[BIT_VECTOR (n - 2) / size_bits] & ((unsigned long)1 << (BIT_VECTOR (n - 2) % size_bits))) 854963 150296 1005259
261 854963 continue;
262 150306 ▶ else if (n >= base)
Branch: 1 branch
BranchTrueFalseTotal
else if (n >= base) 150266 40 150306
263 {
264 150266 ▶ if (ix) {
Branch: 1 branch
BranchTrueFalseTotal
if (ix) { 34 150232 150266
265 /* xs_sieve_count_primes() */
266 34 count++;
267 } else {
268 /* xs_sieve_primes() */
269 150232 ▶ mXPUSHu(n);
Branch: 1 branch
BranchTrueFalseTotal
mXPUSHu(n); 19 150213 150232
270 }
271 }
272 }
273  
274 10 Safefree (composite);
275  
276 10 ▶ if (ix) {
Branch: 1 branch
BranchTrueFalseTotal
if (ix) { 2 8 10
277 /* xs_sieve_count_primes() */
278 2 ▶ mXPUSHu(count);
Branch: 1 branch
BranchTrueFalseTotal
mXPUSHu(count); 0 2 2
279 }
280  
281 void
282 xs_sum_primes (number, base)
283 unsigned long number
284 unsigned long base
285 PROTOTYPE: $$
286 INIT:
287 3 unsigned long *primes = NULL, *sums = NULL;
288 3 unsigned int pos = 0;
289 unsigned long n;
290 PPCODE:
291 183 ▶ for (n = 2; n <= number; n++)
Branch: 1 branch
BranchTrueFalseTotal
for (n = 2; n <= number; n++) 180 3 183
292 {
293 180 bool is_prime = TRUE;
294 180 const unsigned long square_root = sqrt (n); /* truncates */
295 unsigned int c;
296 362 ▶ for (c = 0; c < pos && primes[c] <= square_root; c++)
Branch: 2 branches
BranchTrueFalseTotal
for (c = 0; c < pos && primes[c] <= square_root; c++) 359 3 362
for (c = 0; c < pos && primes[c] <= square_root; c++) 312 47 359
297 {
298 312 unsigned long sum = sums[c];
299 523 ▶ while (sum < n)
Branch: 1 branch
BranchTrueFalseTotal
while (sum < n) 211 312 523
300 211 sum += primes[c];
301 312 sums[c] = sum;
302 312 ▶ if (sum == n)
Branch: 1 branch
BranchTrueFalseTotal
if (sum == n) 130 182 312
303 {
304 130 is_prime = FALSE;
305 130 break;
306 }
307 }
308 180 ▶ if (is_prime)
Branch: 1 branch
BranchTrueFalseTotal
if (is_prime) 50 130 180
309 {
310 num_entry numbers[2];
311 50 NUM_SET (&numbers[0], &primes, pos, n);
312 50 NUM_SET (&numbers[1], &sums, pos, 0);
313 50 store (numbers, NUM_LEN (numbers), &pos);
314  
315 50 ▶ if (n >= base)
Branch: 1 branch
BranchTrueFalseTotal
if (n >= base) 35 15 50
316 {
317 35 ▶ EXTEND (SP, 1);
Branch: 1 branch
BranchTrueFalseTotal
EXTEND (SP, 1); 0 35 35
318 35 PUSHs (sv_2mortal(newSVuv(n)));
319 }
320 }
321 }
322  
323 3 Safefree (primes);
324 3 Safefree (sums);
325  
326 void
327 xs_trial_primes (number, base)
328 unsigned long number
329 unsigned long base
330 PROTOTYPE: $$
331 INIT:
332 3 unsigned long *primes = NULL;
333 3 unsigned int pos = 0;
334 3 unsigned long start = 1;
335 unsigned long i, n;
336 PPCODE:
337 183 ▶ for (n = 2; n <= number; n++)
Branch: 1 branch
BranchTrueFalseTotal
for (n = 2; n <= number; n++) 180 3 183
338 {
339 180 bool is_prime = TRUE;
340 unsigned long square_root; /* calculate later for efficiency */
341 180 ▶ if (n > 2 && EVEN_NUM (n))
Branch: 2 branches
BranchTrueFalseTotal
if (n > 2 && EVEN_NUM (n)) 177 3 180
if (n > 2 && EVEN_NUM (n)) 88 89 177
342 88 continue;
343 92 square_root = sqrt (n); /* truncates */
344 201 ▶ for (i = start; i <= square_root; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = start; i <= square_root; i++) 109 92 201
345 {
346 109 bool save_as_prime = TRUE;
347 unsigned long c;
348 /* not prime */
349 109 ▶ if (i == 1)
Branch: 1 branch
BranchTrueFalseTotal
if (i == 1) 9 100 109
350 9 continue;
351 /* even number */
352 100 ▶ else if (EVEN_NUM (i))
Branch: 1 branch
BranchTrueFalseTotal
else if (EVEN_NUM (i)) 45 55 100
353 45 continue;
354 /* number to resume from equals square root */
355 55 ▶ else if (start == square_root)
Branch: 1 branch
BranchTrueFalseTotal
else if (start == square_root) 41 14 55
356 41 continue;
357 /* check for non-uniqueness */
358 14 ▶ else if (primes && i <= primes[pos - 1])
Branch: 2 branches
BranchTrueFalseTotal
else if (primes && i <= primes[pos - 1]) 11 3 14
else if (primes && i <= primes[pos - 1]) 6 5 11
359 6 continue;
360 28 ▶ for (c = 2; c < i; c++)
Branch: 1 branch
BranchTrueFalseTotal
for (c = 2; c < i; c++) 21 7 28
361 {
362 21 ▶ if (i % c == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (i % c == 0) 1 20 21
363 {
364 1 save_as_prime = FALSE;
365 1 break;
366 }
367 }
368 /* (i % 1 == 0) && (i % i == 0) */
369 8 ▶ if (save_as_prime)
Branch: 1 branch
BranchTrueFalseTotal
if (save_as_prime) 7 1 8
370 {
371 num_entry numbers[1];
372 7 NUM_SET (&numbers[0], &primes, pos, i);
373 7 store (numbers, NUM_LEN (numbers), &pos);
374 }
375 }
376 92 ▶ if (primes)
Branch: 1 branch
BranchTrueFalseTotal
if (primes) 80 12 92
377 {
378 unsigned int c;
379 176 ▶ for (c = 0; c < pos; c++)
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < pos; c++) 138 38 176
380 {
381 138 ▶ if (n % primes[c] == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (n % primes[c] == 0) 42 96 138
382 {
383 42 is_prime = FALSE;
384 42 break;
385 }
386 }
387 }
388 92 ▶ if (is_prime && n >= base)
Branch: 2 branches
BranchTrueFalseTotal
if (is_prime && n >= base) 50 42 92
if (is_prime && n >= base) 35 15 50
389 {
390 35 ▶ EXTEND (SP, 1);
Branch: 1 branch
BranchTrueFalseTotal
EXTEND (SP, 1); 0 35 35
391 35 PUSHs (sv_2mortal(newSVuv(n)));
392 }
393 /* Optimize calculating the minor primes for trial division
394 by starting from the previous square root. */
395 92 start = square_root;
396 }
397  
398 3 Safefree (primes);
« blib/lib/Math/Prime/XS.pm ↑ Summary