| line |
true |
false |
branch |
|
136
|
12776 |
430648 |
if (n <= 10) |
|
137
|
8992 |
3784 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
5551 |
3441 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
3363 |
2188 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
|
1904 |
1459 |
return (n == 2 || n == 3 || n == 5 || n == 7) ? 2 : 0; |
|
139
|
428708 |
1940 |
if (n < UVCONST(200000000)) { |
|
146
|
240414 |
188294 |
if (mtab == 0) |
|
150
|
18167 |
170127 |
if (d < NPRIME_SIEVE30) |
|
151
|
4144 |
14023 |
return (prime_sieve30[d] & mtab) ? 0 : 2; |
|
153
|
141278 |
28849 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
|
127579 |
13699 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
|
10474 |
117105 |
if (!(n%7) || !(n%11) || !(n%13)) return 0; |
|
156
|
105229 |
11876 |
if (n <= get_prime_cache(0,0)) { |
|
158
|
105229 |
0 |
if (n <= get_prime_cache(0, &sieve)) |
|
159
|
44498 |
60731 |
isprime = 2*((sieve[d] & mtab) == 0); |
|
161
|
105229 |
0 |
if (isprime >= 0) |
|
173
|
16226 |
6257 |
if (n < 30*NPRIME_SIEVE30) { |
|
175
|
16225 |
1 |
if (next != 0) return next; |
|
178
|
0 |
6258 |
if (n >= MPU_MAX_PRIME) return 0; /* Overflow */ |
|
180
|
4055 |
2203 |
if (n < get_prime_cache(0,0)) { |
|
183
|
4055 |
0 |
next = (n < sieve_size) ? next_prime_in_sieve(sieve, n, sieve_size) : 0; |
|
185
|
4055 |
0 |
if (next != 0) return next; |
|
192
|
7524 |
2203 |
} while (!is_prob_prime(n)); |
|
201
|
17606 |
8170 |
if (n < 30*NPRIME_SIEVE30) |
|
204
|
4007 |
4163 |
if (n < get_prime_cache(0,0)) { |
|
207
|
4007 |
0 |
prev = (n < sieve_size) ? prev_prime_in_sieve(sieve, n) : 0; |
|
209
|
4007 |
0 |
if (prev != 0) return prev; |
|
216
|
10105 |
4163 |
} while (!is_prob_prime(n)); |
|
230
|
0 |
0 |
} while ((val = t)); |
|
232
|
0 |
0 |
while (--s > ptr) { char c = *s; *s = *ptr; *ptr++ = c; } |
|
237
|
0 |
0 |
if (res == -1) croak("print_primes write error"); |
|
243
|
0 |
0 |
if ((low <= 2) && (high >= 2)) bend += my_sprint(bend,2); |
|
|
0 |
0 |
if ((low <= 2) && (high >= 2)) bend += my_sprint(bend,2); |
|
244
|
0 |
0 |
if ((low <= 3) && (high >= 3)) bend += my_sprint(bend,3); |
|
|
0 |
0 |
if ((low <= 3) && (high >= 3)) bend += my_sprint(bend,3); |
|
245
|
0 |
0 |
if ((low <= 5) && (high >= 5)) bend += my_sprint(bend,5); |
|
|
0 |
0 |
if ((low <= 5) && (high >= 5)) bend += my_sprint(bend,5); |
|
246
|
0 |
0 |
if (low < 7) low = 7; |
|
248
|
0 |
0 |
if (low <= high) { |
|
252
|
0 |
0 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
253
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
0 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
255
|
0 |
0 |
if (bend-buf > 8000) { bend = write_buf(fd, buf, bend); } |
|
260
|
0 |
0 |
if (bend > buf) { bend = write_buf(fd, buf, bend); } |
|
282
|
47 |
22 |
if (sqrtn*sqrtn != hi) sqrtn++; /* ceil sqrtn */ |
|
285
|
69 |
0 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
190 |
353 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
121 |
69 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
65 |
56 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
29 |
324 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
29 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
29 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
29 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
0 |
353 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
|
69 |
474 |
START_DO_FOR_EACH_PRIME(2, sqrtn) { |
|
287
|
88 |
386 |
if (p > nextlog) { |
|
291
|
0 |
474 |
for (i = PGTLO(p, lo); i <= hi; i += p) |
|
|
0 |
0 |
for (i = PGTLO(p, lo); i <= hi; i += p) |
|
|
147009 |
474 |
for (i = PGTLO(p, lo); i <= hi; i += p) |
|
293
|
0 |
474 |
for (i = PGTLO(p2, lo); i <= hi; i += p2) |
|
|
0 |
0 |
for (i = PGTLO(p2, lo); i <= hi; i += p2) |
|
|
37769 |
474 |
for (i = PGTLO(p2, lo); i <= hi; i += p2) |
|
297
|
22 |
47 |
logp = log2floor(lo); |
|
299
|
84662 |
69 |
for (i = lo; i <= hi; i++) { |
|
301
|
418 |
84244 |
if (i >= nextlog) { logp++; nextlog *= 2; } /* logp is log(p)/log(2) */ |
|
302
|
33103 |
51559 |
if (a & 0x80) { a = 0; } |
|
303
|
12349 |
39210 |
else if (a >= logp) { a = 1 - 2*(a&1); } |
|
307
|
47 |
22 |
if (lo == 0) mu[0] = 0; |
|
318
|
0 |
8 |
if (hi < lo) croak("_totient_range error hi %"UVuf" < lo %"UVuf"\n", hi, lo); |
|
319
|
0 |
8 |
New(0, totients, hi-lo+1, UV); |
|
322
|
2 |
6 |
if (hi < 100 || (hi-lo) < 10 || hi/(hi-lo+1) > 1000) { |
|
|
2 |
0 |
if (hi < 100 || (hi-lo) < 10 || hi/(hi-lo+1) > 1000) { |
|
|
0 |
2 |
if (hi < 100 || (hi-lo) < 10 || hi/(hi-lo+1) > 1000) { |
|
323
|
35 |
6 |
for (i = lo; i <= hi; i++) |
|
329
|
1 |
1 |
if (lo == 0) { |
|
332
|
1 |
0 |
UV max_index = (hi < 67) ? 18 |
|
|
1 |
0 |
UV max_index = (hi < 67) ? 18 |
|
337
|
0 |
1 |
New(0, prime, max_index, UV); /* could use prime_count_upper(hi) */ |
|
339
|
119 |
1 |
for (i = 2; i <= hi/2; i++) { |
|
341
|
60 |
59 |
if ( !(i&1) ) { |
|
342
|
1 |
59 |
if (i == 2) { totients[2] = 1; prime[nprimes++] = 2; } |
|
345
|
29 |
30 |
if (totients[i] == 0) { |
|
349
|
167 |
0 |
for (j=0; j < nprimes && index <= hi; index = i*prime[++j]) { |
|
|
127 |
40 |
for (j=0; j < nprimes && index <= hi; index = i*prime[++j]) { |
|
350
|
19 |
108 |
if (i % prime[j] == 0) { |
|
361
|
60 |
1 |
for (i = ((hi/2) + 1) | 1; i <= hi; i += 2) |
|
362
|
22 |
38 |
if (totients[i] == 0) |
|
369
|
25 |
1 |
for (i = lo; i <= hi; i++) { |
|
371
|
12 |
13 |
if (i % 2 == 0) v -= v/2; |
|
372
|
8 |
17 |
if (i % 3 == 0) v -= v/3; |
|
373
|
5 |
20 |
if (i % 5 == 0) v -= v/5; |
|
378
|
1 |
1 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
379
|
133 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
1 |
132 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
132 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
133 |
3 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
4 |
1 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
380
|
2 |
130 |
for (i = P2GTLO(2*p,p,lo); i <= hi; i += p) |
|
|
128 |
2 |
for (i = P2GTLO(2*p,p,lo); i <= hi; i += p) |
|
|
31 |
132 |
for (i = P2GTLO(2*p,p,lo); i <= hi; i += p) |
|
387
|
13 |
1 |
for (i = lo | 1; i <= hi; i += 2) |
|
388
|
2 |
11 |
if (totients[i-lo] == i) |
|
390
|
0 |
1 |
if (lo <= 1) totients[1-lo] = 1; |
|
406
|
1 |
44 |
if (n <= 1) return n; |
|
409
|
32 |
12 |
if (maxmu < u) maxmu = u; |
|
411
|
0 |
44 |
New(0, M, maxmu+1, short); |
|
413
|
56530 |
44 |
for (j = 1; j <= maxmu; j++) |
|
416
|
56530 |
44 |
for (m = 1; m <= u; m++) { |
|
417
|
34416 |
22114 |
if (mu[m] != 0) { |
|
424
|
228923217 |
34416 |
for (nmk = 1; nmk <= last_nmk; nmk++, nmkm += m) { |
|
429
|
17157 |
17259 |
sum += (mu[m] > 0) ? -inner_sum : inner_sum; |
|
446
|
15343 |
84 |
if ((n <= 3) || (n == UV_MAX)) return 1; |
|
|
0 |
15343 |
if ((n <= 3) || (n == UV_MAX)) return 1; |
|
447
|
17 |
15326 |
if ((n & (n-1)) == 0) return ctz(n); /* powers of 2 */ |
|
|
17 |
0 |
if ((n & (n-1)) == 0) return ctz(n); /* powers of 2 */ |
|
448
|
244 |
15082 |
if (is_perfect_square(n)) return 2 * powerof(isqrt(n)); |
|
449
|
50 |
15032 |
if (is_perfect_cube(n)) return 3 * powerof(icbrt(n)); |
|
452
|
8316 |
6716 |
t = n & 511; if ((t*77855451) & (t*4598053) & 862) return 1; |
|
454
|
15 |
6701 |
if (is_perfect_fifth(n)) return 5 * powerof(rootof(n,5)); |
|
455
|
7 |
6694 |
if (is_perfect_seventh(n)) return 7 * powerof(rootof(n,7)); |
|
457
|
2082 |
4612 |
if (n > 177146 && n <= UVCONST(1977326743)) { |
|
|
1853 |
229 |
if (n > 177146 && n <= UVCONST(1977326743)) { |
|
467
|
218 |
6472 |
if (n >= UVCONST(8589934592)) { |
|
471
|
2 |
216 |
if ( (t = n %121, !((t*19706187) & (t*61524433) & 876897796)) && |
|
|
0 |
2 |
if ( (t = n %121, !((t*19706187) & (t*61524433) & 876897796)) && |
|
475
|
0 |
0 |
if (n == ipow(root,11)) return 11; |
|
477
|
34 |
184 |
if ( (t = n %131, !((t*1545928325) & (t*1355660813) & 2771533888U)) && |
|
|
2 |
32 |
if ( (t = n %131, !((t*1545928325) & (t*1355660813) & 2771533888U)) && |
|
481
|
2 |
0 |
if (n == ipow(root,13)) return 13; |
|
510
|
22 |
10443 |
if (a > 0) { |
|
511
|
22 |
0 |
if (a == 1 || n <= 1) return 1; |
|
|
3 |
19 |
if (a == 1 || n <= 1) return 1; |
|
512
|
17 |
2 |
if ((a % 2) == 0) |
|
513
|
4 |
13 |
return !is_perfect_square(n) ? 0 : (a == 2) ? 1 : is_power(isqrt(n),a>>1); |
|
|
0 |
4 |
return !is_perfect_square(n) ? 0 : (a == 2) ? 1 : is_power(isqrt(n),a>>1); |
|
514
|
2 |
0 |
if ((a % 3) == 0) |
|
515
|
2 |
0 |
return !is_perfect_cube(n) ? 0 : (a == 3) ? 1 : is_power(icbrt(n),a/3); |
|
|
0 |
2 |
return !is_perfect_cube(n) ? 0 : (a == 3) ? 1 : is_power(icbrt(n),a/3); |
|
516
|
0 |
0 |
if ((a % 5) == 0) |
|
517
|
0 |
0 |
return !is_perfect_fifth(n) ? 0 : (a == 5) ? 1 :is_power(rootof(n,5),a/5); |
|
|
0 |
0 |
return !is_perfect_fifth(n) ? 0 : (a == 5) ? 1 :is_power(rootof(n,5),a/5); |
|
520
|
0 |
10443 |
if (a != 0) return !(ret % a); /* Is the max power divisible by a? */ |
|
521
|
152 |
10291 |
return (ret == 1) ? 0 : ret; |
|
534
|
0 |
462 |
if (k == 0) return 0; |
|
535
|
19 |
443 |
if (k == 1) return n; |
|
536
|
116 |
327 |
if (k == 2) return isqrt(n); |
|
537
|
9 |
318 |
if (k == 3) return icbrt(n); |
|
540
|
316 |
2 |
max = 1 + ((k >= ROOT_MAX_3) ? 2 : root_max[k]); |
|
541
|
318 |
0 |
lo = UVCONST(1) << (log2floor(n)/k); |
|
545
|
798 |
318 |
while (lo < hi) { |
|
547
|
443 |
355 |
if (ipow(mid,k) <= n) lo = mid+1; |
|
556
|
6 |
10268 |
if (n < 2) return 0; |
|
558
|
24 |
10244 |
if (!(n&1)) { |
|
559
|
15 |
9 |
if (n & (n-1)) return 0; |
|
561
|
9 |
0 |
return ctz(n); |
|
563
|
15 |
10229 |
if ((n%3) == 0) { |
|
565
|
145 |
11 |
do { n /= 3; power++; } while (n > 1 && (n%3) == 0); |
|
|
141 |
4 |
do { n /= 3; power++; } while (n > 1 && (n%3) == 0); |
|
566
|
4 |
11 |
if (n != 1) return 0; |
|
570
|
2007 |
8222 |
if ((n%5) == 0) { |
|
571
|
2563 |
10 |
do { n /= 5; power++; } while (n > 1 && (n%5) == 0); |
|
|
566 |
1997 |
do { n /= 5; power++; } while (n > 1 && (n%5) == 0); |
|
572
|
1997 |
10 |
if (n != 1) return 0; |
|
576
|
1149 |
7073 |
if ((n%7) == 0) { |
|
577
|
1394 |
9 |
do { n /= 7; power++; } while (n > 1 && (n%7) == 0); |
|
|
254 |
1140 |
do { n /= 7; power++; } while (n > 1 && (n%7) == 0); |
|
578
|
1140 |
9 |
if (n != 1) return 0; |
|
582
|
2690 |
4383 |
if (is_prob_prime(n)) |
|
586
|
4262 |
121 |
if (power == 1) power = 0; |
|
587
|
121 |
4262 |
if (power) { |
|
589
|
103 |
18 |
if (is_prob_prime(root)) |
|
601
|
63 |
2 |
if (k < 2 || n < 2) return 0; |
|
|
8 |
55 |
if (k < 2 || n < 2) return 0; |
|
602
|
54 |
1 |
if (k == 2) return ctz(n); |
|
|
54 |
0 |
if (k == 2) return ctz(n); |
|
603
|
3 |
1 |
while ( !(n % kpower) ) { |
|
614
|
200 |
401 |
if (b == 2) |
|
615
|
200 |
0 |
return log2floor(n); |
|
616
|
0 |
401 |
if (n > UV_MAX/b) { |
|
620
|
1140 |
401 |
for (v = b; v <= n; v *= b) |
|
629
|
2 |
0 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
2 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
2 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
|
0 |
2 |
while (len > 0 && (*ptr == '0' || *ptr == '+' || *ptr == '-')) |
|
634
|
0 |
2 |
Newz(0, s, slen, uint32_t); |
|
635
|
17 |
2 |
for (i = 0; i < slen; i++) { /* Chunks of 8 digits */ |
|
636
|
130 |
15 |
for (j = 0, d = 0, power = 1; j < 8 && len > 0; j++, power *= 10) { |
|
|
128 |
2 |
for (j = 0, d = 0, power = 1; j < 8 && len > 0; j++, power *= 10) { |
|
638
|
0 |
128 |
if (v > 9) croak("Parameter '%s' must be a positive integer",ptr); |
|
644
|
372 |
2 |
while (slen > 1) { |
|
645
|
176 |
196 |
if (s[slen-1] & 1) count++; |
|
647
|
15 |
357 |
if (s[0] == 1) { |
|
648
|
0 |
15 |
if (--slen == 0) break; |
|
651
|
1921 |
372 |
for (i = 0; i < slen; i++) { |
|
652
|
1549 |
372 |
if ( (i+1) < slen && sptr[i] & 1 ) sptr[i+1] += 100000000; |
|
|
771 |
778 |
if ( (i+1) < slen && sptr[i] & 1 ) sptr[i+1] += 100000000; |
|
657
|
54 |
2 |
for (d = s[0]; d > 0; d >>= 1) |
|
658
|
25 |
29 |
if (d & 1) |
|
670
|
3601 |
1275 |
while (a) { |
|
671
|
3601 |
0 |
int r = padic2(a); |
|
672
|
1623 |
1978 |
if (r) { |
|
673
|
1083 |
540 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
|
789 |
294 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
|
148 |
641 |
if ((r&1) && IS_MOD8_3OR5(b)) s = -s; |
|
676
|
404 |
3197 |
if (a & b & 2) s = -s; |
|
679
|
1229 |
46 |
return (b == 1) ? s : 0; |
|
684
|
1239 |
42 |
if (b & 1) return kronecker_uu_sign(a, b, 1); |
|
685
|
18 |
24 |
if (!(a&1)) return 0; |
|
687
|
23 |
1 |
r = padic2(b); |
|
688
|
24 |
0 |
if (r) { |
|
689
|
22 |
2 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
11 |
11 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
5 |
6 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
697
|
35 |
14 |
if (a >= 0) return kronecker_uu(a, b); |
|
698
|
2 |
12 |
if (b == 0) return (a == 1 || a == -1) ? 1 : 0; |
|
|
2 |
0 |
if (b == 0) return (a == 1 || a == -1) ? 1 : 0; |
|
|
1 |
1 |
if (b == 0) return (a == 1 || a == -1) ? 1 : 0; |
|
700
|
12 |
0 |
r = padic2(b); |
|
701
|
2 |
10 |
if (r) { |
|
702
|
0 |
2 |
if (!(a&1)) return 0; |
|
703
|
2 |
0 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
2 |
0 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
|
2 |
0 |
if ((r&1) && IS_MOD8_3OR5(a)) s = -s; |
|
707
|
8 |
4 |
if (a < 0) a += b; |
|
712
|
7 |
11 |
if (a >= 0 && b >= 0) |
|
|
0 |
7 |
if (a >= 0 && b >= 0) |
|
713
|
0 |
0 |
return (b & 1) ? kronecker_uu_sign(a, b, 1) : kronecker_uu(a,b); |
|
714
|
7 |
11 |
if (b >= 0) |
|
716
|
4 |
7 |
return kronecker_su(a, -b) * ((a < 0) ? -1 : 1); |
|
721
|
472 |
2280 |
if ( (n > 12 && sizeof(UV) <= 4) || (n > 20 && sizeof(UV) <= 8) ) return 0; |
|
722
|
13871 |
2280 |
for (i = 2; i <= n; i++) |
|
729
|
186 |
24938 |
if (k == 0) return 1; |
|
730
|
2034 |
22904 |
if (k == 1) return n; |
|
731
|
1553 |
21351 |
if (k >= n) return (k == n); |
|
732
|
10633 |
10718 |
if (k > n/2) k = n-k; |
|
733
|
197192 |
16115 |
for (d = 1; d <= k; d++) { |
|
734
|
14824 |
182368 |
if (r >= UV_MAX/n) { /* Possible overflow */ |
|
738
|
5236 |
9588 |
if (r >= UV_MAX/nr) return 0; /* Unavoidable overflow */ |
|
753
|
0 |
190 |
if (m == n) return 1; |
|
754
|
190 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
190 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
0 |
190 |
if (n == 0 || m == 0 || m > n) return 0; |
|
755
|
19 |
171 |
if (m == 1) return factorial(n); |
|
758
|
0 |
171 |
if (f1 == 0) return 0; |
|
760
|
171 |
0 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
|
0 |
171 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
763
|
171 |
0 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
|
5 |
166 |
if (f2 == 0 || f1 >= UV_MAX/f2) return 0; |
|
771
|
0 |
1789 |
if (m == n) return 1; |
|
772
|
1789 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
1789 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
0 |
1789 |
if (n == 0 || m == 0 || m > n) return 0; |
|
773
|
240 |
1549 |
if (m == 1) return 1; |
|
775
|
165 |
1384 |
if ((f = factorial(m)) == 0) return 0; |
|
776
|
6586 |
1075 |
for (j = 1; j <= (IV)m; j++) { |
|
778
|
115103 |
6277 |
for (k = 1; k <= (IV)n; k++) { |
|
779
|
115103 |
0 |
if (t == 0 || j >= IV_MAX/t) return 0; |
|
|
309 |
114794 |
if (t == 0 || j >= IV_MAX/t) return 0; |
|
782
|
2890 |
3387 |
if ((m-j) & 1) t *= -1; |
|
791
|
0 |
192 |
if (m == n) return 1; |
|
792
|
192 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
192 |
0 |
if (n == 0 || m == 0 || m > n) return 0; |
|
|
0 |
192 |
if (n == 0 || m == 0 || m > n) return 0; |
|
793
|
19 |
173 |
if (m == 1) { |
|
795
|
0 |
19 |
if (f>(UV)IV_MAX) return 0; |
|
796
|
10 |
9 |
return (n&1) ? ((IV)f) : -((IV)f); |
|
799
|
816 |
126 |
for (k = 1; k <= (IV)(n-m); k++) { |
|
803
|
814 |
2 |
if (b1 == 0 || b2 == 0 || s2 == 0 || b1 > IV_MAX/b2) return 0; |
|
|
814 |
0 |
if (b1 == 0 || b2 == 0 || s2 == 0 || b1 > IV_MAX/b2) return 0; |
|
|
804 |
10 |
if (b1 == 0 || b2 == 0 || s2 == 0 || b1 > IV_MAX/b2) return 0; |
|
|
0 |
804 |
if (b1 == 0 || b2 == 0 || s2 == 0 || b1 > IV_MAX/b2) return 0; |
|
805
|
35 |
769 |
if (s2 > IV_MAX/t) return 0; |
|
807
|
430 |
339 |
s += (k & 1) ? -t : t; |
|
814
|
96 |
614 |
if (n <= 1) return n; |
|
817
|
144 |
614 |
while ((n & 0x3) == 0) { n >>= 1; totient <<= 1; } |
|
818
|
333 |
281 |
if ((n & 0x1) == 0) { n >>= 1; } |
|
822
|
649 |
614 |
for (i = 0; i < nfacs; i++) { |
|
824
|
48 |
601 |
if (f == lastf) { totient *= f; } |
|
840
|
490 |
0 |
if (k == 0 || n <= 1) return (n == 1); |
|
|
11 |
479 |
if (k == 0 || n <= 1) return (n == 1); |
|
841
|
457 |
22 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
|
321 |
136 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
|
0 |
321 |
if (k > 6 || (k > 1 && n >= jordan_overflow[k-2])) return 0; |
|
845
|
205 |
457 |
while ((n & 0x3) == 0) { n >>= 1; totient *= (1<
|
|
846
|
226 |
231 |
if ((n & 0x1) == 0) { n >>= 1; totient *= ((1<
|
|
848
|
503 |
457 |
for (i = 0; i < nfac; i++) { |
|
852
|
170 |
410 |
while (i+1 < nfac && p == factors[i+1]) { |
|
|
77 |
93 |
while (i+1 < nfac && p == factors[i+1]) { |
|
865
|
8 |
262 |
if (n < 8) return totient(n); |
|
866
|
9 |
253 |
if ((n & (n-1)) == 0) return n >> 2; |
|
868
|
253 |
0 |
i = ctz(n); |
|
869
|
95 |
158 |
if (i > 0) { |
|
871
|
20 |
75 |
lambda <<= (i>2) ? i-2 : i-1; |
|
874
|
347 |
253 |
for (i = 0; i < nfactors; i++) { |
|
876
|
141 |
253 |
while (i+1 < nfactors && p == fac[i+1]) { |
|
|
47 |
94 |
while (i+1 < nfactors && p == fac[i+1]) { |
|
891
|
19440 |
560 |
if (n < 561 || !(n&1)) return 0; |
|
|
9720 |
9720 |
if (n < 561 || !(n&1)) return 0; |
|
894
|
8640 |
1080 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8294 |
346 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8125 |
169 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
8058 |
67 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
47 |
8011 |
if (!(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
898
|
1333 |
6678 |
if (!(n% 5) && ((n-1) % 4 != 0)) return 0; |
|
|
666 |
667 |
if (!(n% 5) && ((n-1) % 4 != 0)) return 0; |
|
899
|
918 |
6427 |
if (!(n% 7) && ((n-1) % 6 != 0)) return 0; |
|
|
574 |
344 |
if (!(n% 7) && ((n-1) % 6 != 0)) return 0; |
|
900
|
567 |
6204 |
if (!(n%11) && ((n-1) % 10 != 0)) return 0; |
|
|
438 |
129 |
if (!(n%11) && ((n-1) % 10 != 0)) return 0; |
|
901
|
451 |
5882 |
if (!(n%13) && ((n-1) % 12 != 0)) return 0; |
|
|
349 |
102 |
if (!(n%13) && ((n-1) % 12 != 0)) return 0; |
|
902
|
355 |
5629 |
if (!(n%17) && ((n-1) % 16 != 0)) return 0; |
|
|
306 |
49 |
if (!(n%17) && ((n-1) % 16 != 0)) return 0; |
|
903
|
302 |
5376 |
if (!(n%19) && ((n-1) % 18 != 0)) return 0; |
|
|
261 |
41 |
if (!(n%19) && ((n-1) % 18 != 0)) return 0; |
|
904
|
244 |
5173 |
if (!(n%23) && ((n-1) % 22 != 0)) return 0; |
|
|
220 |
24 |
if (!(n%23) && ((n-1) % 22 != 0)) return 0; |
|
907
|
0 |
5197 |
if (n > 5000000) { |
|
908
|
0 |
0 |
if (!(n%29) && ((n-1) % 28 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%29) && ((n-1) % 28 != 0)) return 0; |
|
909
|
0 |
0 |
if (!(n%31) && ((n-1) % 30 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%31) && ((n-1) % 30 != 0)) return 0; |
|
910
|
0 |
0 |
if (!(n%37) && ((n-1) % 36 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%37) && ((n-1) % 36 != 0)) return 0; |
|
911
|
0 |
0 |
if (!(n%41) && ((n-1) % 40 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%41) && ((n-1) % 40 != 0)) return 0; |
|
912
|
0 |
0 |
if (!(n%43) && ((n-1) % 42 != 0)) return 0; |
|
|
0 |
0 |
if (!(n%43) && ((n-1) % 42 != 0)) return 0; |
|
913
|
0 |
0 |
if (!is_pseudoprime(n,2)) return 0; |
|
917
|
4664 |
533 |
if (nfactors < 3) |
|
919
|
1321 |
9 |
for (i = 0; i < nfactors; i++) { |
|
920
|
1321 |
0 |
if (exp[i] > 1 || ((n-1) % (fac[i]-1)) != 0) |
|
|
524 |
797 |
if (exp[i] > 1 || ((n-1) % (fac[i]-1)) != 0) |
|
928
|
13015 |
144 |
for (i = 0; i < nfactors; i++) { |
|
930
|
13015 |
0 |
if (d == 0 || (p % d) != 0) |
|
|
8086 |
4929 |
if (d == 0 || (p % d) != 0) |
|
942
|
68 |
5334 |
if (n < 35) return 0; |
|
945
|
4000 |
1334 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
3556 |
444 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
3414 |
142 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
3343 |
71 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
3313 |
30 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
|
20 |
3293 |
if (!(n% 4) || !(n% 9) || !(n%25) || !(n%49) || !(n%121) || !(n%169)) |
|
950
|
741 |
2552 |
if (nfactors < 2) |
|
953
|
6371 |
2518 |
for (i = 0; i < nfactors; i++) |
|
954
|
34 |
6337 |
if (exp[i] > 1) |
|
962
|
1448 |
1070 |
if (nfactors == 2) { |
|
964
|
5953 |
0 |
for (i = 0; i < (int)ndivisors; i++) { |
|
967
|
1448 |
4505 |
if (d >= spf) break; |
|
968
|
92 |
4413 |
if (is_quasi_base(nfactors, fac, n-k, k)) |
|
973
|
8453 |
1070 |
for (i = 0; i < (int)ndivisors; i++) { |
|
976
|
3693 |
4760 |
if (lpf > d && k >= spf) continue; |
|
|
3658 |
35 |
if (lpf > d && k >= spf) continue; |
|
977
|
3725 |
1070 |
if (k != 0 && is_quasi_base(nfactors, fac, n-k, k)) |
|
|
52 |
3673 |
if (k != 0 && is_quasi_base(nfactors, fac, n-k, k)) |
|
988
|
0 |
103 |
if (n < 6) return (n == 4); |
|
989
|
51 |
52 |
if (!(n&1)) return !!is_prob_prime(n>>1); |
|
990
|
16 |
36 |
if (!(n%3)) return !!is_prob_prime(n/3); |
|
991
|
6 |
30 |
if (!(n%5)) return !!is_prob_prime(n/5); |
|
994
|
244 |
2 |
for (sp = 4; sp < 60; sp++) { |
|
996
|
18 |
226 |
if (p > n3) |
|
998
|
10 |
216 |
if ((n % p) == 0) |
|
1002
|
18 |
2 |
if (is_def_prime(n)) return 0; |
|
|
11 |
9 |
if (is_def_prime(n)) return 0; |
|
1003
|
7 |
2 |
if (p > n3) return 1; |
|
1006
|
0 |
2 |
if ( pbrent_factor(n, factors, 90000, 1) == 2 |
|
1008
|
0 |
0 |
|| pminus1_factor(n, factors, 4000, 4000) == 2 |
|
1010
|
0 |
0 |
|| pbrent_factor(n, factors, 180000, 7) == 2 ) |
|
1011
|
2 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
2 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
0 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
1 |
1 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
1 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
|
1 |
0 |
return (is_def_prime(factors[0]) && is_def_prime(factors[1])); |
|
1021
|
94 |
8 |
if (r) { |
|
1022
|
47 |
47 |
if (!neg) { |
|
1024
|
6 |
3 |
case 0: return (r == 4) ? 0 : is_square_free(n >> 2); |
|
|
6 |
0 |
case 0: return (r == 4) ? 0 : is_square_free(n >> 2); |
|
1030
|
6 |
3 |
case 0: return (r == 12) ? 0 : is_square_free(n >> 2); |
|
|
5 |
1 |
case 0: return (r == 12) ? 0 : is_square_free(n >> 2); |
|
1043
|
206 |
255 |
if (n & 1) return 0; |
|
1045
|
6 |
249 |
if (n == 1) return 1; |
|
1046
|
75 |
174 |
if (n < maxd && is_prime(2*n+1)) return 1; |
|
|
19 |
56 |
if (n < maxd && is_prime(2*n+1)) return 1; |
|
1049
|
1045 |
41 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
|
871 |
174 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
|
856 |
15 |
for (i = 0, res = 0; i < ndivisors && divs[i] < maxd && res == 0; i++) { |
|
1051
|
507 |
349 |
if (!is_prime(p)) continue; |
|
1054
|
398 |
3 |
if (r == p || _totpred(r, d)) { res = 1; break; } |
|
|
13 |
385 |
if (r == p || _totpred(r, d)) { res = 1; break; } |
|
1055
|
333 |
52 |
if (r % p) break; |
|
1064
|
123 |
1 |
return (n == 0 || (n & 1)) ? (n==1) : _totpred(n,n); |
|
|
60 |
63 |
return (n == 0 || (n & 1)) ? (n==1) : _totpred(n,n); |
|
1069
|
0 |
0 |
if (n == 0) return 0; |
|
1070
|
0 |
0 |
for (v = 8; v < n-1 && fac != 0; v++) { |
|
|
0 |
0 |
for (v = 8; v < n-1 && fac != 0; v++) { |
|
1071
|
0 |
0 |
fac = (n < HALF_WORD) ? (fac*v) % n : mulmod(fac,v,n); |
|
1072
|
0 |
0 |
if (fac == n-1 && (n % v) != 1) |
|
|
0 |
0 |
if (fac == n-1 && (n % v) != 1) |
|
1083
|
261 |
28800 |
if (n <= 1) return (int)n; |
|
1084
|
26945 |
1855 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
|
20212 |
6733 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
|
17962 |
2250 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
|
17239 |
723 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
|
364 |
16875 |
if ( n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49)) ) |
|
1088
|
21568 |
17651 |
for (i = 1; i < nfactors; i++) |
|
1089
|
1079 |
20489 |
if (factors[i] == factors[i-1]) |
|
1091
|
9072 |
8579 |
return (nfactors % 2) ? -1 : 1; |
|
1096
|
6 |
14 |
if (!primepower(n,&p)) return 1; /* Not a prime power */ |
|
1107
|
6 |
69 |
if (n <= 1) return n; /* znorder(x,0) = 0, znorder(x,1) = 1 */ |
|
1108
|
3 |
66 |
if (a <= 1) return a; /* znorder(0,x) = 0, znorder(1,x) = 1 (x > 1) */ |
|
1109
|
6 |
60 |
if (gcd_ui(a,n) > 1) return 0; |
|
1115
|
219 |
60 |
for (i = 0; i < nfactors; i++) { |
|
1120
|
168 |
219 |
for (ek = 0; a1 != 1 && ek++ <= ei; a1 = powmod(a1, pi, n)) |
|
|
168 |
0 |
for (ek = 0; a1 != 1 && ek++ <= ei; a1 = powmod(a1, pi, n)) |
|
1122
|
0 |
219 |
if (ek > ei) return 0; |
|
1133
|
5 |
20 |
if (n <= 4) return (n == 0) ? 0 : n-1; |
|
|
4 |
1 |
if (n <= 4) return (n == 0) ? 0 : n-1; |
|
1134
|
1 |
19 |
if (n % 4 == 0) return 0; |
|
1136
|
3 |
16 |
on = (n&1) ? n : (n>>1); |
|
1139
|
2 |
17 |
if (!is_prob_prime(r)) return 0; /* c^a or 2c^a */ |
|
1143
|
66 |
17 |
for (i = 0; i < nfactors; i++) |
|
1145
|
870 |
0 |
for (a = 2; a < n; a++) { |
|
1147
|
859 |
11 |
if (a == 4 || a == 8 || a == 9) continue; |
|
|
852 |
7 |
if (a == 4 || a == 8 || a == 9) continue; |
|
|
7 |
845 |
if (a == 4 || a == 8 || a == 9) continue; |
|
1149
|
812 |
33 |
if (phi == n-1) { |
|
1150
|
653 |
159 |
if (kronecker_uu(a, n) != -1) continue; |
|
1152
|
16 |
17 |
if (kronecker_uu(a, n) == 0) continue; |
|
1154
|
442 |
17 |
for (i = 0; i < nfactors; i++) |
|
1155
|
159 |
283 |
if (powmod(a, exp[i], n) == 1) |
|
1157
|
17 |
159 |
if (i == nfactors) return a; |
|
1165
|
2 |
45 |
if (n <= 1) return n; |
|
1166
|
20 |
25 |
if (a >= n) a %= n; |
|
1167
|
2 |
43 |
if (gcd_ui(a,n) != 1) return 0; |
|
1168
|
19 |
24 |
s = nprime ? n-1 : totient(n); |
|
1172
|
5 |
38 |
if (i > 1 && gcd_ui(i, s) != 1) return 0; |
|
|
4 |
1 |
if (i > 1 && gcd_ui(i, s) != 1) return 0; |
|
1175
|
38 |
1 |
if ((s % 2) == 0 && powmod(a, s/2, n) == 1) return 0; |
|
|
9 |
29 |
if ((s % 2) == 0 && powmod(a, s/2, n) == 1) return 0; |
|
1178
|
25 |
5 |
if (n & 1) { |
|
1181
|
10 |
15 |
if ((s % 3) == 0 && mont_powmod(a, s/3, n) == mont1) return 0; |
|
|
1 |
9 |
if ((s % 3) == 0 && mont_powmod(a, s/3, n) == mont1) return 0; |
|
1182
|
13 |
11 |
if ((s % 5) == 0 && mont_powmod(a, s/5, n) == mont1) return 0; |
|
|
0 |
13 |
if ((s % 5) == 0 && mont_powmod(a, s/5, n) == mont1) return 0; |
|
1184
|
77 |
24 |
for (i = 0; i < nfacs; i++) { |
|
1185
|
31 |
46 |
if (fac[i] > 5 && mont_powmod(a, s/fac[i], n) == mont1) return 0; |
|
|
0 |
31 |
if (fac[i] > 5 && mont_powmod(a, s/fac[i], n) == mont1) return 0; |
|
1190
|
0 |
5 |
if ((s % 3) == 0 && powmod(a, s/3, n) == 1) return 0; |
|
|
0 |
0 |
if ((s % 3) == 0 && powmod(a, s/3, n) == 1) return 0; |
|
1191
|
1 |
4 |
if ((s % 5) == 0 && powmod(a, s/5, n) == 1) return 0; |
|
|
1 |
0 |
if ((s % 5) == 0 && powmod(a, s/5, n) == 1) return 0; |
|
1194
|
3 |
4 |
for (i = 0; i < nfacs; i++) { |
|
1195
|
0 |
3 |
if (fac[i] > 5 && powmod(a, s/fac[i], n) == 1) return 0; |
|
|
0 |
0 |
if (fac[i] > 5 && powmod(a, s/fac[i], n) == 1) return 0; |
|
1205
|
3 |
47 |
if (a == 0 && b == 0) { os = 0; t = 0; } |
|
|
1 |
2 |
if (a == 0 && b == 0) { os = 0; t = 0; } |
|
1206
|
285 |
50 |
while (r != 0) { |
|
1212
|
4 |
46 |
if (or < 0) /* correct sign */ |
|
1214
|
50 |
0 |
if (u != 0) *u = os; |
|
1215
|
50 |
0 |
if (v != 0) *v = ot; |
|
1216
|
38 |
12 |
if (cs != 0) *cs = s; |
|
1217
|
38 |
12 |
if (ct != 0) *ct = t; |
|
1225
|
3631 |
161 |
while (nr != 0) { |
|
1230
|
29 |
132 |
if (r > 1) return 0; /* No inverse */ |
|
1231
|
71 |
61 |
if (t < 0) t += n; |
|
1237
|
0 |
2 |
if (binv == 0) return 0; |
|
1243
|
183499 |
183072 |
do { d /= p; e += d; } while (d > 0); |
|
1250
|
821 |
0 |
if (n >= m || m == 1) return 0; |
|
|
1 |
820 |
if (n >= m || m == 1) return 0; |
|
1252
|
384 |
436 |
if (n <= 10) { /* Keep things simple for small n */ |
|
1253
|
1358 |
314 |
for (i = 2; i <= n && res != 0; i++) |
|
|
1288 |
70 |
for (i = 2; i <= n && res != 0; i++) |
|
1258
|
335 |
101 |
if (n > m/2 && is_prime(m)) /* Check if we can go backwards */ |
|
|
74 |
261 |
if (n > m/2 && is_prime(m)) /* Check if we can go backwards */ |
|
1260
|
14 |
422 |
if (d < 2) |
|
1261
|
7 |
7 |
return (d == 0) ? m-1 : 1; /* Wilson's Theorem: n = m-1 and n = m-2 */ |
|
1263
|
362 |
60 |
if (d == n && d > 5000000) { /* Check for composite m that leads to 0 */ |
|
|
1 |
361 |
if (d == n && d > 5000000) { /* Check for composite m that leads to 0 */ |
|
1266
|
1 |
1 |
for (j = 0; j < nfacs; j++) { |
|
1268
|
2 |
1 |
for (k = 1; (UV)k < exp[j]; k++) |
|
1270
|
0 |
1 |
if (n >= t) return 0; |
|
1275
|
197 |
225 |
if (m & 1 && d < 40000) { |
|
|
196 |
1 |
if (m & 1 && d < 40000) { |
|
1279
|
1746 |
82 |
for (i = 2; i <= d && res != 0; i++) { |
|
|
1632 |
114 |
for (i = 2; i <= d && res != 0; i++) { |
|
1281
|
0 |
1632 |
res = mont_mulmod(res,monti,m); |
|
1283
|
0 |
196 |
res = mont_recover(res, m); |
|
1286
|
225 |
1 |
if (d < 10000) { |
|
1287
|
2011 |
20 |
for (i = 2; i <= d && res != 0; i++) |
|
|
1806 |
205 |
for (i = 2; i <= d && res != 0; i++) |
|
1300
|
3 |
1 |
for (i = 1; i <= 3; i++) /* Handle 2,3,5 assume d>10*/ |
|
1302
|
7 |
0 |
while (res != 0 && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
|
6 |
1 |
while (res != 0 && next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
1303
|
348511 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
1 |
348510 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
348510 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
348511 |
20833 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
|
20834 |
6 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) |
|
1304
|
183069 |
165441 |
UV k = (p > (d>>1)) ? p : _powfactor(p, d, m); |
|
1306
|
0 |
348510 |
if (res == 0) break; |
|
1313
|
60 |
362 |
if (d != n && res != 0) { /* Handle backwards case */ |
|
|
60 |
0 |
if (d != n && res != 0) { /* Handle backwards case */ |
|
1314
|
31 |
29 |
if (!(d&1)) res = submod(m,res,m); |
|
1322
|
8 |
7 |
if (p-s < s) s = p-s; |
|
1323
|
0 |
15 |
if (mulmod(s, s, p) != a) return 0; |
|
1397
|
1 |
7 |
if ((p % 4) == 3) { |
|
1399
|
0 |
1 |
return mont_recover(b, p); |
|
1402
|
5 |
2 |
if ((p % 8) == 5) { /* Atkin's algorithm. Faster than Legendre. */ |
|
1406
|
0 |
5 |
beta = mont_mulmod(a2,mont_sqrmod(alpha,p),p); |
|
|
0 |
0 |
beta = mont_mulmod(a2,mont_sqrmod(alpha,p),p); |
|
|
0 |
5 |
beta = mont_mulmod(a2,mont_sqrmod(alpha,p),p); |
|
1408
|
0 |
5 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
|
0 |
0 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
|
0 |
5 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
1409
|
0 |
5 |
return mont_recover(b, p); |
|
1411
|
1 |
1 |
if ((p % 16) == 9) { /* Müller's algorithm extending Atkin */ |
|
1415
|
0 |
1 |
beta = mont_mulmod(a2, mont_sqrmod(alpha,p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_sqrmod(alpha,p), p); |
|
|
0 |
1 |
beta = mont_mulmod(a2, mont_sqrmod(alpha,p), p); |
|
1416
|
0 |
1 |
if (mont_sqrmod(beta,p) != submod(0,mont1,p)) { |
|
|
1 |
0 |
if (mont_sqrmod(beta,p) != submod(0,mont1,p)) { |
|
1417
|
4 |
1 |
do { d += 2; } while (kronecker_uu(d,p) != -1 && d < p); |
|
|
4 |
0 |
do { d += 2; } while (kronecker_uu(d,p) != -1 && d < p); |
|
1419
|
0 |
1 |
alpha = mont_mulmod(alpha, mont_powmod(d,(p-9)>>3,p), p); |
|
1420
|
0 |
1 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
1 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
0 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
1 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
|
0 |
1 |
beta = mont_mulmod(a2, mont_mulmod(mont_sqrmod(d,p),mont_sqrmod(alpha,p),p), p); |
|
1421
|
0 |
1 |
beta = mont_mulmod(submod(beta,mont1,p), d, p); |
|
1425
|
0 |
1 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
|
0 |
0 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
|
0 |
1 |
b = mont_mulmod(alpha, mont_mulmod(a, beta, p), p); |
|
1426
|
0 |
1 |
return mont_recover(b, p); |
|
1430
|
1 |
0 |
if ((p & 1) && mont_powmod(a,(p-1)>>1,p) != mont1) return 0; |
|
|
0 |
1 |
if ((p & 1) && mont_powmod(a,(p-1)>>1,p) != mont1) return 0; |
|
1438
|
0 |
1 |
while (kronecker_uu(t, p) != -1) { |
|
1440
|
0 |
0 |
if (t == 201) { /* exit if p looks like a composite */ |
|
1441
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
1443
|
0 |
0 |
} else if (t >= 20000) { /* should never happen */ |
|
1453
|
2 |
1 |
while (b != mont1) { |
|
1455
|
5 |
0 |
for (m = 0; m < r && t != mont1; m++) |
|
|
3 |
2 |
for (m = 0; m < r && t != mont1; m++) |
|
1456
|
0 |
3 |
t = mont_sqrmod(t, p); |
|
1457
|
0 |
2 |
if (m >= r) break; |
|
1459
|
0 |
2 |
x = mont_mulmod(x, t, p); |
|
1460
|
0 |
2 |
z = mont_mulmod(t, t, p); |
|
1461
|
0 |
2 |
b = mont_mulmod(b, z, p); |
|
1464
|
0 |
1 |
return mont_recover(x, p); |
|
1471
|
0 |
10 |
if (p == 0) return 0; |
|
1472
|
2 |
8 |
if (a >= p) a %= p; |
|
1473
|
10 |
0 |
if (p <= 2 || a <= 1) return verify_sqrtmod(a, s,a,p); |
|
|
2 |
8 |
if (p <= 2 || a <= 1) return verify_sqrtmod(a, s,a,p); |
|
1485
|
2 |
5 |
if (n == 0) return 0; |
|
1486
|
0 |
5 |
if (a >= n) a %= n; |
|
1487
|
3 |
2 |
if (n <= 2 || a <= 1) return verify_sqrtmod(a, s,a,n); |
|
|
0 |
3 |
if (n <= 2 || a <= 1) return verify_sqrtmod(a, s,a,n); |
|
1490
|
3 |
0 |
if (kronecker_uu(a, ((n%4) == 2) ? n/2 : n) == -1) return 0; |
|
|
0 |
3 |
if (kronecker_uu(a, ((n%4) == 2) ? n/2 : n) == -1) return 0; |
|
1493
|
0 |
3 |
if ((n % 4) == 0) { |
|
1494
|
0 |
0 |
if ((n % 8) == 0) { |
|
1495
|
0 |
0 |
if ((a % 8) != 1) return 0; |
|
1497
|
0 |
0 |
if ((a % 4) != 1) return 0; |
|
1503
|
0 |
3 |
if (gcdan == 1) { |
|
1504
|
0 |
0 |
if ((n % 3) == 0 && kronecker_uu(a, 3) != 1) return 0; |
|
|
0 |
0 |
if ((n % 3) == 0 && kronecker_uu(a, 3) != 1) return 0; |
|
1505
|
0 |
0 |
if ((n % 5) == 0 && kronecker_uu(a, 5) != 1) return 0; |
|
|
0 |
0 |
if ((n % 5) == 0 && kronecker_uu(a, 5) != 1) return 0; |
|
1506
|
0 |
0 |
if ((n % 7) == 0 && kronecker_uu(a, 7) != 1) return 0; |
|
|
0 |
0 |
if ((n % 7) == 0 && kronecker_uu(a, 7) != 1) return 0; |
|
1513
|
0 |
3 |
if (gcdan == 1) { |
|
1514
|
0 |
0 |
for (i = 0; i < nfactors; i++) |
|
1515
|
0 |
0 |
if (fac[i] > 7 && kronecker_uu(a, fac[i]) != 1) return 0; |
|
|
0 |
0 |
if (fac[i] > 7 && kronecker_uu(a, fac[i]) != 1) return 0; |
|
1518
|
8 |
3 |
for (i = 0; i < nfactors; i++) { |
|
1521
|
3 |
5 |
if (fac[i] == 2) { |
|
1522
|
3 |
0 |
if (exp[i] == 1) { |
|
1524
|
0 |
0 |
} else if (exp[i] == 2) { |
|
1531
|
0 |
0 |
for (j = 2; j < exp[i]; j++) { |
|
1534
|
0 |
0 |
for (k = 0; k < nthis && nnext < 254; k++) { |
|
|
0 |
0 |
for (k = 0; k < nthis && nnext < 254; k++) { |
|
1536
|
0 |
0 |
if (sqrmod(r,p) == (a % p)) |
|
1538
|
0 |
0 |
if (sqrmod(p-r,p) == (a % p)) |
|
1541
|
0 |
0 |
if (nnext == 0) return 0; |
|
1544
|
0 |
0 |
for (k = 0; k < nnext; k++) |
|
1554
|
0 |
5 |
if (!sqrtmod(&(sqr[i]), a, p)) |
|
1558
|
0 |
5 |
for (j = 1; j < exp[i]; j++) { |
|
1565
|
0 |
0 |
if (expect != 1 || sqrmod(sol,p) != (a % p)) { |
|
|
0 |
0 |
if (expect != 1 || sqrmod(sol,p) != (a % p)) { |
|
1574
|
8 |
3 |
for (i = 0; i < nfactors; i++) |
|
1578
|
3 |
0 |
return (i == 1) ? verify_sqrtmod(p, s, a, n) : 0; |
|
1587
|
0 |
4 |
if (num == 0) return 0; |
|
1589
|
8 |
0 |
for (i = 0; i < num; i++) { |
|
1592
|
3 |
5 |
if (gcd != 1) return 0; /* not coprime */ |
|
1594
|
1 |
4 |
if (ni > (UV_MAX/lcm)) return 0; /* lcm overflow */ |
|
1597
|
0 |
0 |
for (i = 0; i < num; i++) { |
|
1601
|
0 |
0 |
if (inverse == 0) return 0; /* n's coprime so should never happen */ |
|
1614
|
1 |
29 |
if (num == 0) return 0; |
|
1617
|
319 |
29 |
for (gi = 0, gap = sgaps[gi]; gap >= 1; gap = sgaps[++gi]) { |
|
1618
|
42 |
319 |
for (i = gap; i < num; i++) { |
|
1620
|
54 |
30 |
for (j = i; j >= gap && n[j-gap] < tn; j -= gap) |
|
|
42 |
12 |
for (j = i; j >= gap && n[j-gap] < tn; j -= gap) |
|
1626
|
1 |
28 |
if (n[0] > IV_MAX) return _simple_chinese(a,n,num,status); |
|
1628
|
38 |
20 |
for (i = 1; i < num; i++) { |
|
1632
|
10 |
28 |
if (gcd != 1 && ((sum % gcd) != (a[i] % gcd))) { *status = -1; return 0; } |
|
|
5 |
5 |
if (gcd != 1 && ((sum % gcd) != (a[i] % gcd))) { *status = -1; return 0; } |
|
1633
|
18 |
15 |
if (s < 0) s = -s; |
|
1634
|
15 |
18 |
if (t < 0) t = -t; |
|
1635
|
3 |
30 |
if (s > (IV)(IV_MAX/lcm)) return _simple_chinese(a,n,num,status); |
|
1637
|
14 |
16 |
if (u < 0) u += lcm; |
|
1638
|
15 |
15 |
if (v < 0) v += lcm; |
|
1649
|
9 |
9 |
UV sqrtn = which ? isqrt(n) : 0; /* for theta, p <= sqrtn always false */ |
|
1652
|
14 |
4 |
if (n < 500) { |
|
1654
|
122 |
14 |
for (pi = 1; (p = nth_prime(pi)) <= n; pi++) { |
|
1656
|
8 |
114 |
if (p <= sqrtn) logp *= floorl(logn/logp+1e-15); |
|
1666
|
2 |
2 |
if (!which) { |
|
1674
|
6 |
4 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
1675
|
213914 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
4 |
213910 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
213910 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
213914 |
11316 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
11320 |
6 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
1677
|
250 |
213660 |
if (p <= sqrtn) logp *= floorl(logn/logp+1e-15); |
|
1716
|
0 |
234 |
if (x == 0) croak("Invalid input to ExponentialIntegral: x must be != 0"); |
|
1718
|
0 |
234 |
if (x >= 12000) return INFINITY; |
|
1719
|
0 |
234 |
if (x <= -12000) return 0; |
|
1721
|
1 |
233 |
if (x < -1) { |
|
1726
|
20 |
0 |
for (n = 1; n <= 100000; n++) { |
|
1734
|
1 |
19 |
if ( fabsl(val-old) <= LDBL_EPSILON*fabsl(val) ) |
|
1737
|
5 |
228 |
} else if (x < 0) { |
|
1756
|
228 |
0 |
} else if (x < (-2 * logl(LDBL_EPSILON))) { |
|
1759
|
15320 |
0 |
for (n = 2; n <= 200; n++) { |
|
1765
|
228 |
15092 |
if (term < LDBL_EPSILON*sum) break; |
|
1771
|
0 |
0 |
} else if (x >= 24) { |
|
1787
|
0 |
0 |
for (n = 0; n <= 8; n++) |
|
1795
|
0 |
0 |
for (n = 1; n <= 200; n++) { |
|
1798
|
0 |
0 |
if (term < LDBL_EPSILON*sum) break; |
|
1799
|
0 |
0 |
if (term < last_term) { |
|
1816
|
0 |
2213 |
if (x == 0) return 0; |
|
1817
|
0 |
2213 |
if (x == 1) return -INFINITY; |
|
1818
|
0 |
2213 |
if (x == 2) return li2; |
|
1819
|
0 |
2213 |
if (x < 0) croak("Invalid input to LogarithmicIntegral: x must be >= 0"); |
|
1820
|
0 |
2213 |
if (x >= LDBL_MAX) return INFINITY; |
|
1823
|
2213 |
0 |
if (x > 1) { |
|
1829
|
89173 |
0 |
for (n = 1, k = 0; n < 200; n++) { |
|
1834
|
45234 |
89173 |
for (; k <= (n - 1) / 2; k++) |
|
1838
|
2213 |
86960 |
if (fabsl(sum - old_sum) <= LDBL_EPSILON) break; |
|
1850
|
3 |
94 |
if (x <= 2) return x + (x > 0); |
|
1852
|
376 |
55 |
for (i = 0, t = lx*logl(x); i < 4; i++) { |
|
1855
|
282 |
94 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
|
39 |
243 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
1862
|
0 |
94 |
i = (x > 4e16) ? 2048 : 128; |
|
1863
|
0 |
94 |
if (Li(r-1) >= lx) { |
|
1864
|
0 |
0 |
while (Li(r-i) >= lx) r -= i; |
|
1865
|
0 |
0 |
for (i = i/2; i > 0; i /= 2) |
|
1866
|
0 |
0 |
if (Li(r-i) >= lx) r -= i; |
|
1868
|
0 |
94 |
while (Li(r+i-1) < lx) r += i; |
|
1869
|
658 |
94 |
for (i = i/2; i > 0; i /= 2) |
|
1870
|
0 |
658 |
if (Li(r+i-1) < lx) r += i; |
|
1878
|
0 |
23 |
if (x <= 2) return x + (x > 0); |
|
1886
|
89 |
13 |
for (i = 0; i < 4; i++) { |
|
1889
|
66 |
23 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
|
10 |
56 |
if (i > 0 && fabsl(term) >= fabsl(old_term)) { t -= term/4; break; } |
|
1978
|
0 |
2895 |
if (x < 0) croak("Invalid input to RiemannZeta: x must be >= 0"); |
|
1979
|
0 |
2895 |
if (x == 1) return INFINITY; |
|
1981
|
2891 |
4 |
if (x == (unsigned int)x) { |
|
1983
|
2891 |
0 |
if ((k >= 0) && (k < (int)NPRECALC_ZETA)) |
|
|
2 |
2889 |
if ((k >= 0) && (k < (int)NPRECALC_ZETA)) |
|
1988
|
2893 |
0 |
if (x >= 0.5 && x <= 5.0) { |
|
|
2 |
2891 |
if (x >= 0.5 && x <= 5.0) { |
|
2013
|
0 |
2891 |
if (x > 17000.0) |
|
2059
|
9244 |
2 |
for (i = 2; i < 11; i++) { |
|
2062
|
2889 |
6355 |
if (fabsl(b) < fabsl(LDBL_EPSILON * s)) |
|
2067
|
19 |
0 |
for (i = 0; i < 13; i++) { |
|
2073
|
2 |
17 |
if (fabsl(t) < fabsl(LDBL_EPSILON * s)) |
|
2087
|
0 |
123 |
if (x <= 0) croak("Invalid input to ReimannR: x must be > 0"); |
|
2089
|
2 |
121 |
if (x > 1e19) { |
|
2092
|
132 |
0 |
for (k = 2; k <= 100; k++) { |
|
2093
|
50 |
82 |
if (amob[k] == 0) continue; |
|
2096
|
0 |
82 |
if (part_term > LDBL_MAX) return INFINITY; |
|
2100
|
2 |
80 |
if (fabsl(sum - old_sum) <= LDBL_EPSILON) break; |
|
2110
|
9329 |
0 |
for (k = 1; k <= 10000; k++) { |
|
2111
|
6440 |
2889 |
ki = (k-1 < NPRECALC_ZETA) ? riemann_zeta_table[k-1] : ld_riemann_zeta(k+1); |
|
2117
|
121 |
9208 |
if (fabsl(sum - old_sum) <= LDBL_EPSILON) break; |
|
2125
|
2 |
6 |
if (x < -0.060) { /* Pade(3,2) */ |
|
2127
|
0 |
2 |
long double t = (ti <= 0.0L) ? 0.0L : sqrtl(ti); |
|
2131
|
2 |
4 |
} else if (x < 1.363) { /* Winitzki 2003 section 3.5 */ |
|
2134
|
0 |
4 |
} else if (x < 3.7) { /* Modification of Vargas 2013 */ |
|
2157
|
0 |
9 |
if (x < -0.36787944117145L) |
|
2159
|
1 |
8 |
if (x == 0.0L) return 0.0L; |
|
2164
|
0 |
8 |
if (w <= -1.0L) return -1.0L + 8*LDBL_EPSILON; |
|
2166
|
1 |
7 |
if (x < -0.36783) return w; |
|
2180
|
28 |
2 |
for (i = 0; i < 6 && w != 0.0L; i++) { |
|
|
28 |
0 |
for (i = 0; i < 6 && w != 0.0L; i++) { |
|
2188
|
5 |
23 |
if (fabsl(wen) <= 64*LDBL_EPSILON) break; |
|
2210
|
0 |
987 |
if (digits <= 0) return 0; |
|
2211
|
15 |
972 |
if (digits <= DBL_DIG && digits <= 18) { |
|
|
15 |
0 |
if (digits <= DBL_DIG && digits <= 18) { |
|
2220
|
0 |
972 |
New(0, a, c, uint32_t); |
|
2221
|
1776026 |
972 |
for (b = 0; b < c; b++) a[b] = 2000; |
|
2224
|
125887 |
729 |
while ((b = c -= 14) > 0 && i < (uint32_t)digits) { |
|
|
125644 |
243 |
while ((b = c -= 14) > 0 && i < (uint32_t)digits) { |
|
2226
|
0 |
125644 |
if (b > 107000) { /* Use 64-bit intermediate while necessary. */ |
|
2227
|
0 |
0 |
for (d64 = d; --b > 107000; ) { |
|
2236
|
148341500 |
125644 |
while (--b > 0) { |
|
2244
|
0 |
125644 |
if (d4 > 9999) { |
|
2247
|
0 |
0 |
for (b=i-1; out[b] == '0'+1; b--) { out[b]='0'; out[b-1]++; } |
|
2256
|
480 |
492 |
if (out[digits-1] >= '5') out[digits-2]++; /* Round */ |
|
2257
|
70 |
972 |
for (i = digits-2; out[i] == '9'+1; i--) /* Keep rounding */ |
|
2274
|
4 |
0 |
if (b == 0 || blen == 0) croak("Parameter must be a positive integer"); |
|
|
0 |
4 |
if (b == 0 || blen == 0) croak("Parameter must be a positive integer"); |
|
2276
|
4 |
0 |
if (b[0] == '-' || b[0] == '+') { b++; blen--; } |
|
|
0 |
4 |
if (b[0] == '-' || b[0] == '+') { b++; blen--; } |
|
2277
|
4 |
0 |
while (blen > 0 && *b == '0') { b++; blen--; } |
|
|
0 |
4 |
while (blen > 0 && *b == '0') { b++; blen--; } |
|
2278
|
80 |
4 |
for (i = 0; i < blen; i++) |
|
2279
|
0 |
80 |
if (!isDIGIT(b[i])) |
|
2281
|
4 |
0 |
if (blen == 0 || i < blen) |
|
|
0 |
4 |
if (blen == 0 || i < blen) |
|
2284
|
2 |
2 |
if (a == 0) return 1; |
|
2287
|
2 |
0 |
if (a[0] == '-' || a[0] == '+') { a++; alen--; } |
|
|
0 |
2 |
if (a[0] == '-' || a[0] == '+') { a++; alen--; } |
|
2288
|
2 |
0 |
while (alen > 0 && *a == '0') { a++; alen--; } |
|
|
0 |
2 |
while (alen > 0 && *a == '0') { a++; alen--; } |
|
2290
|
0 |
2 |
if (aneg != bneg) return min ? (bneg == 1) : (aneg == 1); |
|
|
0 |
0 |
if (aneg != bneg) return min ? (bneg == 1) : (aneg == 1); |
|
2291
|
0 |
2 |
if (aneg == 1) min = !min; |
|
2292
|
0 |
2 |
if (alen != blen) return min ? (alen > blen) : (blen > alen); |
|
|
0 |
0 |
if (alen != blen) return min ? (alen > blen) : (blen > alen); |
|
2294
|
2 |
0 |
for (i = 0; i < blen; i++) |
|
2295
|
2 |
0 |
if (a[i] != b[i]) |
|
2296
|
1 |
1 |
return min ? (a[i] > b[i]) : (b[i] > a[i]); |
|
2306
|
6 |
0 |
if (s[0] == '-' || s[0] == '+') s++; |
|
|
0 |
6 |
if (s[0] == '-' || s[0] == '+') s++; |
|
2307
|
0 |
6 |
while (s[0] == '0') s++; |
|
2312
|
34 |
5 |
for (i = 0, len = strlen(s); i < len; i++) { |
|
2314
|
34 |
0 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
|
20 |
14 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
|
0 |
14 |
int d = !isalnum(c) ? 255 : (c <= '9') ? c-'0' : (c <= 'Z') ? c-'A'+10 : c-'a'+10; |
|
2315
|
0 |
34 |
if (d >= base) croak("Invalid digit for base %d", base); |
|
2316
|
1 |
33 |
if (n > max) return 0; /* Overflow */ |
|
2327
|
13 |
0 |
if (len < 0 || len > BITS_PER_WORD) |
|
|
0 |
13 |
if (len < 0 || len > BITS_PER_WORD) |
|
2329
|
63 |
13 |
for (i = 0; i < len; i++) { |
|
2331
|
0 |
63 |
if (n > (UV_MAX-d)/base) break; /* overflow */ |
|
2344
|
0 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
0 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
0 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
|
0 |
0 |
if (len < 0 || !(base == 2 || base == 10 || base == 16)) return 0; |
|
2346
|
0 |
0 |
if (r[0] >= (UV) base) return 0; /* TODO: We don't apply extended carry */ |
|
2350
|
0 |
0 |
if (base == 2 || base == 16) { |
|
|
0 |
0 |
if (base == 2 || base == 16) { |
|
2352
|
0 |
0 |
*s++ = (base == 2) ? 'b' : 'x'; |
|
2354
|
0 |
0 |
for (i = 0; i < len; i++) { |
|
2356
|
0 |
0 |
s[i] = (d < 10) ? '0'+d : 'a'+d-10; |
|
2367
|
17 |
0 |
if (base < 2 || length > 128) return -1; |
|
|
0 |
17 |
if (base < 2 || length > 128) return -1; |
|
2369
|
10 |
7 |
if (base == 2) { |
|
2370
|
77 |
10 |
for (d = 0; n; n >>= 1) |
|
2373
|
24 |
7 |
for (d = 0; n; n /= base) |
|
2376
|
11 |
6 |
if (length < 0) length = d; |
|
2377
|
26 |
17 |
while (d < length) |
|
2387
|
0 |
3 |
if (len < 0) return -1; |
|
2388
|
0 |
3 |
if (base > 36) croak("invalid base for string: %d", base); |
|
2390
|
18 |
3 |
for (i = 0; i < len; i++) { |
|
2392
|
18 |
0 |
s[i] = (dig < 10) ? '0'+dig : 'a'+dig-10; |
|
2402
|
0 |
1 |
if (hi < 0) { |
|
2414
|
19 |
1 |
} while (sum); |
|
2435
|
10 |
1 |
for (i=0; i < slen/2; i++) { |
|
2441
|
0 |
1 |
if (isneg) { |
|
2442
|
0 |
0 |
for (i = slen; i > 0; i--) |
|
2457
|
473541 |
472642 |
while (n /= p) s += n % 2; |
|
2462
|
0 |
0 |
while (n /= p) s += n % 2; |
|
2466
|
428809 |
472642 |
if (p > a) { |
|
2469
|
472642 |
0 |
UV pow = (n <= 4294967295UL) ? _catalan_v32(a<<1,p) : _catalan_v(a<<1,p); |
|
2471
|
186211 |
286431 |
: (pow == 1) ? mulmod(m,p,n) |
|
2472
|
185962 |
249 |
: mulmod(m,powmod(p,pow,n),n); |
|
2477
|
13 |
5 |
while (n /= p) |
|
2478
|
0 |
13 |
if (n % 2) |
|
2486
|
3 |
0 |
if (n < 2 || ((n % 2) == 0 && n != 2)) return 0; |
|
|
0 |
3 |
if (n < 2 || ((n % 2) == 0 && n != 2)) return 0; |
|
|
0 |
0 |
if (n < 2 || ((n % 2) == 0 && n != 2)) return 0; |
|
2487
|
0 |
3 |
if (is_prob_prime(n)) return 1; |
|
2498
|
0 |
3 |
if (nfactors == 2 && (n < UVCONST(10000000000))) |
|
|
0 |
0 |
if (nfactors == 2 && (n < UVCONST(10000000000))) |
|
2501
|
5 |
3 |
for (i = 0; i < nfactors; i++) { |
|
2502
|
0 |
5 |
if (_catalan_vtest(a << 1, factors[i])) |
|
2514
|
16 |
3 |
while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { |
|
2515
|
901445 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
3 |
901442 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
901442 |
0 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
901445 |
56364 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
|
56367 |
16 |
START_DO_FOR_EACH_SIEVE_PRIME( segment, seg_base, seg_low, seg_high ) { |
|
2521
|
1 |
2 |
return (a & 1) ? (m==(n-1)) : (m==1); |
|
2528
|
10 |
35858 |
if (x == 0) return y; |
|
2530
|
20064 |
15794 |
if (y & 1) { /* Optimize y odd */ |
|
2531
|
20064 |
0 |
x >>= ctz(x); |
|
2532
|
382102 |
20064 |
while (x != y) { |
|
2533
|
57469 |
324633 |
if (x < y) { y -= x; y >>= ctz(y); } |
|
|
57469 |
0 |
if (x < y) { y -= x; y >>= ctz(y); } |
|
2534
|
324633 |
0 |
else { x -= y; x >>= ctz(x); } |
|
2539
|
1 |
15793 |
if (y == 0) return x; |
|
2542
|
15793 |
0 |
x2 = ctz(x); |
|
2543
|
15793 |
0 |
y2 = ctz(y); |
|
2548
|
187434 |
15793 |
while (x != y) { |
|
2549
|
14545 |
172889 |
if (x < y) { |
|
2551
|
14545 |
0 |
y >>= ctz(y); |
|
2554
|
172889 |
0 |
x >>= ctz(x); |
|
2568
|
6 |
4 |
return (n < NTAU) ? tau_table[n] : 0; |
|
2575
|
4 |
401 |
if (lim*lim == b2) lim--; |
|
2576
|
43 |
362 |
if (s > lim) return 0; |
|
2578
|
337 |
25 |
if ((lim-s) < 70) { /* Iterate looking for divisors */ |
|
2579
|
6767 |
337 |
for (i = s; i <= lim; i++) |
|
2580
|
106 |
6661 |
if (b2 % i == 0) |
|
2584
|
56 |
0 |
for (i = 0; i < ndivisors && divs[i] <= lim; i++) |
|
|
31 |
25 |
for (i = 0; i < ndivisors && divs[i] <= lim; i++) |
|
2585
|
6 |
25 |
if (divs[i] >= s) |
|
2599
|
1 |
95 |
if (n == 0) return -1; |
|
2600
|
82 |
13 |
if (nmod4 == 1 || nmod4 == 2) return 0; |
|
|
8 |
74 |
if (nmod4 == 1 || nmod4 == 2) return 0; |
|
2601
|
1 |
73 |
if (n == 3) return 4; |
|
2608
|
18 |
55 |
if (b == 1) |
|
2612
|
405 |
73 |
for (; b2 = (n + b*b) >> 2, 3*b2 < n; b += 2) { |
|
2617
|
70 |
3 |
return 12*h + ((b2*3 == n) ? 4 : square && !(n&1) ? 6 : 0); |
|
|
11 |
59 |
return 12*h + ((b2*3 == n) ? 4 : square && !(n&1) ? 6 : 0); |
|
|
10 |
1 |
return 12*h + ((b2*3 == n) ? 4 : square && !(n&1) ? 6 : 0); |
|
2622
|
0 |
25300 |
MPUassert(k >= 3, "is_polygonal root < 3"); |
|
2624
|
46 |
25254 |
if (n <= 1) return n; |
|
2625
|
198 |
25056 |
if (k == 4) return is_perfect_square(n) ? isqrt(n) : 0; |
|
|
18 |
180 |
if (k == 4) return is_perfect_square(n) ? isqrt(n) : 0; |
|
2626
|
108 |
24948 |
if (k == 3) { |
|
2627
|
0 |
108 |
if (n >= UV_MAX/8) *overflow = 1; |
|
2631
|
24948 |
0 |
if (k > UV_MAX/k || n > UV_MAX/(8*k-16)) *overflow = 1; |
|
|
0 |
24948 |
if (k > UV_MAX/k || n > UV_MAX/(8*k-16)) *overflow = 1; |
|
2635
|
0 |
25056 |
if (D+R <= D) *overflow = 1; |
|
2637
|
25056 |
0 |
if (*overflow || !is_perfect_square(D)) return 0; |
|
|
24138 |
918 |
if (*overflow || !is_perfect_square(D)) return 0; |
|
2640
|
522 |
396 |
if ((D % R) != 0) return 0; |
|
2652
|
3 |
5 |
while (f == 0) /* We can handle n! overflow if we have a valid k */ |
|
2655
|
1 |
4 |
if (k/f >= (UV)n) |
|
2658
|
45 |
5 |
for (i = 0; i < n; i++) |
|
2660
|
37 |
5 |
for (i = si; i < n-1; i++) { |
|
2664
|
19 |
18 |
if (p > 0) { |
|
2665
|
47 |
19 |
for (j = i+p, t = vec[j]; j > i; j--) |
|
2677
|
2 |
4 |
if (f == 0) return 0; |
|
2678
|
38 |
4 |
for (i = 0; i < n-1; i++) { |
|
2679
|
302 |
38 |
for (j = i+1, k = 0; j < n; j++) |
|
2680
|
137 |
165 |
if (vec[j] < vec[i]) |
|
2682
|
0 |
38 |
if ((UV)k > (UV_MAX-num)/f) return 0; /* overflow */ |
|
2691
|
0 |
0 |
{ const UV *x = a, *y = b; return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; } |
|
|
0 |
0 |
{ const UV *x = a, *y = b; return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; } |
|
2706
|
0 |
3 |
if (k > n) k = n; |
|
2708
|
3 |
0 |
if (k == 0) { /* 0 of n */ |
|
2709
|
1 |
2 |
} else if (k == 1) { /* 1 of n. Pick one at random */ |
|
2711
|
0 |
2 |
} else if (k == 2 && n == 2) { /* 2 of 2. Flip a coin */ |
|
|
0 |
0 |
} else if (k == 2 && n == 2) { /* 2 of 2. Flip a coin */ |
|
2714
|
0 |
2 |
} else if (k == 2) { /* 2 of n. Pick 2 skipping dup */ |
|
2717
|
0 |
0 |
if (S[1] >= S[0]) S[1]++; |
|
2718
|
0 |
2 |
} else if (k < n/100 && k < 30) { /* k of n. Pick k with loop */ |
|
|
0 |
0 |
} else if (k < n/100 && k < 30) { /* k of n. Pick k with loop */ |
|
2719
|
0 |
0 |
for (i = 0; i < k; i++) { |
|
2722
|
0 |
0 |
for (j = 0; j < i; j++) |
|
2723
|
0 |
0 |
if (S[j] == S[i]) |
|
2725
|
0 |
0 |
} while (j < i); |
|
2727
|
0 |
2 |
} else if (k < n/100 && n > 1000000) {/* k of n. Pick k with dedup retry */ |
|
|
0 |
0 |
} else if (k < n/100 && n > 1000000) {/* k of n. Pick k with dedup retry */ |
|
2728
|
0 |
0 |
for (j = 0; j < k; ) { |
|
2729
|
0 |
0 |
for (i = j; i < k; i++) /* Fill S[j .. k-1] then sort S */ |
|
2732
|
0 |
0 |
for (j = 0, i = 1; i < k; i++) /* Find and remove dups. O(n). */ |
|
2733
|
0 |
0 |
if (S[j] != S[i]) |
|
2738
|
0 |
0 |
for (i = 0; i < k; i++) { |
|
2742
|
1 |
1 |
} else if (k < n/4) { /* k of n. Pick k with mask */ |
|
2744
|
1 |
0 |
if (n <= 32*8) mask = smask; |
|
2745
|
0 |
0 |
else Newz(0, mask, n/32 + ((n%32)?1:0), uint32_t); |
|
|
0 |
0 |
else Newz(0, mask, n/32 + ((n%32)?1:0), uint32_t); |
|
|
0 |
0 |
else Newz(0, mask, n/32 + ((n%32)?1:0), uint32_t); |
|
2746
|
4 |
1 |
for (i = 0; i < k; i++) { |
|
2749
|
0 |
4 |
} while ( mask[j>>5] & (1U << (j&0x1F)) ); |
|
2753
|
0 |
1 |
if (mask != smask) Safefree(mask); |
|
2754
|
0 |
1 |
} else if (k < n) { /* k of n. FYK shuffle n, pick k */ |
|
2756
|
0 |
0 |
New(0, T, n, UV); |
|
2757
|
0 |
0 |
for (i = 0; i < n; i++) |
|
2759
|
0 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
|
0 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
2766
|
100 |
1 |
for (i = 0; i < n; i++) |
|
2768
|
100 |
0 |
for (i = 0; i < k && i <= n-2; i++) { |
|
|
99 |
1 |
for (i = 0; i < k && i <= n-2; i++) { |