/usr/include/flint/ulong_extras.h is in libflint-dev 2.5.2-17build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 | /*=============================================================================
This file is part of FLINT.
FLINT is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
FLINT is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with FLINT; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
=============================================================================*/
/******************************************************************************
Copyright (C) 2006, 2007, 2008, 2009 William Hart
Copyright (C) 2008, Peter Shrimpton
Copyright (C) 2009, Tom Boothby
Copyright (C) 2010, Fredrik Johansson
******************************************************************************/
#ifndef ULONG_EXTRAS_H
#define ULONG_EXTRAS_H
#ifdef ULONG_EXTRAS_INLINES_C
#define ULONG_EXTRAS_INLINE FLINT_DLL
#else
#define ULONG_EXTRAS_INLINE static __inline__
#endif
#include <gmp.h>
#include "flint.h"
#ifdef __cplusplus
extern "C" {
#endif
typedef struct pair_s
{
mp_limb_t x, y;
} n_pair_t;
#define FLINT_MAX_FACTORS_IN_LIMB 15
typedef struct {
int num;
int exp[FLINT_MAX_FACTORS_IN_LIMB];
mp_limb_t p[FLINT_MAX_FACTORS_IN_LIMB];
} n_factor_t;
#define FLINT_ODDPRIME_SMALL_CUTOFF 4096
#define FLINT_NUM_PRIMES_SMALL 172
#define FLINT_PRIMES_SMALL_CUTOFF 1030
#define FLINT_PSEUDOSQUARES_CUTOFF 1000
#define FLINT_FACTOR_TRIAL_PRIMES 3000
/* nth_prime(FLINT_FACTOR_TRIAL_PRIMES) */
#define FLINT_FACTOR_TRIAL_PRIMES_PRIME UWORD(27449)
#define FLINT_FACTOR_TRIAL_CUTOFF (UWORD(27449) * UWORD(27449))
#define FLINT_PRIMES_TAB_DEFAULT_CUTOFF 1000000
#define FLINT_FACTOR_SQUFOF_ITERS 50000
#define FLINT_FACTOR_ONE_LINE_MAX (UWORD(1)<<39)
#define FLINT_FACTOR_ONE_LINE_ITERS 40000
#define FLINT_PRIME_PI_ODD_LOOKUP_CUTOFF 311
#define FLINT_SIEVE_SIZE 65536
#if FLINT64
#define UWORD_MAX_PRIME UWORD(18446744073709551557)
#else
#define UWORD_MAX_PRIME UWORD(4294967291)
#endif
typedef struct
{
slong small_i;
slong small_num;
unsigned int * small_primes;
mp_limb_t sieve_a;
mp_limb_t sieve_b;
slong sieve_i;
slong sieve_num;
char * sieve;
}
n_primes_struct;
typedef n_primes_struct n_primes_t[1];
FLINT_DLL void n_primes_init(n_primes_t iter);
FLINT_DLL void n_primes_clear(n_primes_t iter);
FLINT_DLL void n_primes_extend_small(n_primes_t iter, mp_limb_t bound);
FLINT_DLL void n_primes_sieve_range(n_primes_t iter, mp_limb_t a, mp_limb_t b);
FLINT_DLL void n_primes_jump_after(n_primes_t iter, mp_limb_t n);
ULONG_EXTRAS_INLINE mp_limb_t
n_primes_next(n_primes_t iter)
{
if (iter->small_i < iter->small_num)
return iter->small_primes[(iter->small_i)++];
for (;;)
{
while (iter->sieve_i < iter->sieve_num)
if (iter->sieve[iter->sieve_i++] != 0)
return iter->sieve_a + 2 * (iter->sieve_i - 1);
if (iter->sieve_b == 0)
n_primes_jump_after(iter, iter->small_primes[iter->small_num-1]);
else
n_primes_jump_after(iter, iter->sieve_b);
}
}
extern const unsigned int flint_primes_small[];
extern FLINT_TLS_PREFIX mp_limb_t * _flint_primes[FLINT_BITS];
extern FLINT_TLS_PREFIX double * _flint_prime_inverses[FLINT_BITS];
extern FLINT_TLS_PREFIX int _flint_primes_used;
FLINT_DLL void n_compute_primes(ulong num_primes);
FLINT_DLL void n_cleanup_primes(void);
FLINT_DLL const mp_limb_t * n_primes_arr_readonly(ulong n);
FLINT_DLL const double * n_prime_inverses_arr_readonly(ulong n);
FLINT_DLL mp_limb_t n_randlimb(flint_rand_t state);
FLINT_DLL mp_limb_t n_randint(flint_rand_t state, mp_limb_t limit);
FLINT_DLL mp_limb_t n_randbits(flint_rand_t state, unsigned int bits);
FLINT_DLL mp_limb_t n_randtest_bits(flint_rand_t state, int bits);
FLINT_DLL mp_limb_t n_randtest(flint_rand_t state);
FLINT_DLL mp_limb_t n_randtest_not_zero(flint_rand_t state);
FLINT_DLL mp_limb_t n_randprime(flint_rand_t state, ulong bits, int proved);
FLINT_DLL mp_limb_t n_randtest_prime(flint_rand_t state, int proved);
FLINT_DLL mp_limb_t n_pow(mp_limb_t n, ulong exp);
FLINT_DLL mp_limb_t n_flog(mp_limb_t n, mp_limb_t b);
FLINT_DLL mp_limb_t n_clog(mp_limb_t n, mp_limb_t b);
ULONG_EXTRAS_INLINE
double n_precompute_inverse(mp_limb_t n)
{
return (double) 1 / (double) n;
}
ULONG_EXTRAS_INLINE
mp_limb_t n_preinvert_limb(mp_limb_t n)
{
mp_limb_t norm, ninv;
count_leading_zeros(norm, n);
invert_limb(ninv, n<<norm);
return ninv;
}
FLINT_DLL mp_limb_t n_mod_precomp(mp_limb_t a, mp_limb_t n, double ninv);
FLINT_DLL mp_limb_t n_mod2_precomp(mp_limb_t a, mp_limb_t n, double ninv);
FLINT_DLL mp_limb_t n_divrem2_precomp(mp_limb_t * q, mp_limb_t a,
mp_limb_t n, double npre);
FLINT_DLL mp_limb_t n_mod2_preinv(mp_limb_t a, mp_limb_t n, mp_limb_t ninv);
FLINT_DLL mp_limb_t n_ll_mod_preinv(mp_limb_t a_hi, mp_limb_t a_lo,
mp_limb_t n, mp_limb_t ninv);
FLINT_DLL mp_limb_t n_lll_mod_preinv(mp_limb_t a_hi, mp_limb_t a_mi,
mp_limb_t a_lo, mp_limb_t n, mp_limb_t ninv);
FLINT_DLL mp_limb_t n_mulmod_precomp(mp_limb_t a, mp_limb_t b,
mp_limb_t n, double ninv);
FLINT_DLL mp_limb_t n_mulmod2_preinv(mp_limb_t a, mp_limb_t b,
mp_limb_t n, mp_limb_t ninv);
FLINT_DLL mp_limb_t n_mulmod_preinv(mp_limb_t a, mp_limb_t b,
mp_limb_t n, mp_limb_t ninv, ulong norm);
FLINT_DLL mp_limb_t n_powmod_ui_precomp(mp_limb_t a, mp_limb_t exp, mp_limb_t n, double npre);
FLINT_DLL mp_limb_t n_powmod_precomp(mp_limb_t a,
mp_limb_signed_t exp, mp_limb_t n, double npre);
ULONG_EXTRAS_INLINE
mp_limb_t n_powmod(mp_limb_t a, mp_limb_signed_t exp, mp_limb_t n)
{
double npre = n_precompute_inverse(n);
return n_powmod_precomp(a, exp, n, npre);
}
FLINT_DLL mp_limb_t n_powmod2_preinv(mp_limb_t a,
mp_limb_signed_t exp, mp_limb_t n, mp_limb_t ninv);
FLINT_DLL mp_limb_t n_powmod2_ui_preinv(mp_limb_t a, mp_limb_t exp,
mp_limb_t n, mp_limb_t ninv);
FLINT_DLL mp_limb_t n_powmod_ui_preinv(mp_limb_t a, mp_limb_t exp, mp_limb_t n,
mp_limb_t ninv, ulong norm);
ULONG_EXTRAS_INLINE
mp_limb_t n_powmod2(mp_limb_t a, mp_limb_signed_t exp, mp_limb_t n)
{
mp_limb_t ninv = n_preinvert_limb(n);
return n_powmod2_preinv(a, exp, n, ninv);
}
ULONG_EXTRAS_INLINE
mp_limb_t n_addmod(mp_limb_t x, mp_limb_t y, mp_limb_t n)
{
return (n - y > x ? x + y : x + y - n);
}
ULONG_EXTRAS_INLINE
mp_limb_t n_submod(mp_limb_t x, mp_limb_t y, mp_limb_t n)
{
return (y > x ? x - y + n : x - y);
}
ULONG_EXTRAS_INLINE
mp_limb_t n_negmod(mp_limb_t x, mp_limb_t n)
{
return n_submod(0, x, n);
}
FLINT_DLL mp_limb_t n_sqrtmod(mp_limb_t a, mp_limb_t p);
FLINT_DLL slong n_sqrtmod_2pow(mp_limb_t ** sqrt, mp_limb_t a, slong exp);
FLINT_DLL slong n_sqrtmod_primepow(mp_limb_t ** sqrt, mp_limb_t a,
mp_limb_t p, slong exp);
FLINT_DLL slong n_sqrtmodn(mp_limb_t ** sqrt, mp_limb_t a, n_factor_t * fac);
FLINT_DLL mp_limb_t n_gcd(mp_limb_t x, mp_limb_t y);
#define n_gcd_full n_gcd
FLINT_DLL mp_limb_t n_xgcd(mp_limb_t * a, mp_limb_t * b, mp_limb_t x, mp_limb_t y);
FLINT_DLL mp_limb_t n_invmod(mp_limb_t x, mp_limb_t y);
FLINT_DLL mp_limb_t n_gcdinv(mp_limb_t * a, mp_limb_t x, mp_limb_t y);
FLINT_DLL ulong n_revbin(ulong in, ulong bits);
FLINT_DLL int n_jacobi(mp_limb_signed_t x, mp_limb_t y);
FLINT_DLL int n_jacobi_unsigned(mp_limb_t x, mp_limb_t y);
FLINT_DLL mp_limb_t n_sqrt(mp_limb_t a);
FLINT_DLL mp_limb_t n_sqrtrem(mp_limb_t * r, mp_limb_t a);
FLINT_DLL int n_is_square(mp_limb_t x);
FLINT_DLL double n_cbrt_estimate(double a);
FLINT_DLL mp_limb_t n_cbrt(mp_limb_t a);
FLINT_DLL mp_limb_t n_cbrt_binary_search(mp_limb_t x);
FLINT_DLL mp_limb_t n_cbrt_newton_iteration(mp_limb_t n);
FLINT_DLL mp_limb_t n_cbrt_chebyshev_approx(mp_limb_t n);
FLINT_DLL mp_limb_t n_cbrtrem(mp_limb_t* remainder, mp_limb_t n);
FLINT_DLL int n_is_perfect_power235(mp_limb_t n);
FLINT_DLL int n_is_oddprime_small(mp_limb_t n);
FLINT_DLL int n_is_oddprime_binary(mp_limb_t n);
FLINT_DLL int n_is_probabprime_fermat(mp_limb_t n, mp_limb_t i);
FLINT_DLL int n_is_probabprime_fibonacci(mp_limb_t n);
FLINT_DLL int n_is_probabprime_lucas(mp_limb_t n);
FLINT_DLL int n_is_probabprime_BPSW(mp_limb_t n);
FLINT_DLL int n_is_strong_probabprime_precomp(mp_limb_t n,
double npre, mp_limb_t a, mp_limb_t d);
FLINT_DLL int n_is_strong_probabprime2_preinv(mp_limb_t n,
mp_limb_t ninv, mp_limb_t a, mp_limb_t d);
FLINT_DLL int n_is_probabprime(mp_limb_t n);
FLINT_DLL int n_is_prime_pseudosquare(mp_limb_t n);
FLINT_DLL int n_is_prime_pocklington(mp_limb_t n, ulong iterations);
FLINT_DLL int n_is_prime(mp_limb_t n);
FLINT_DLL mp_limb_t n_nth_prime(ulong n);
FLINT_DLL void n_nth_prime_bounds(mp_limb_t *lo, mp_limb_t *hi, ulong n);
FLINT_DLL ulong n_prime_pi(mp_limb_t n);
FLINT_DLL void n_prime_pi_bounds(ulong *lo, ulong *hi, mp_limb_t n);
FLINT_DLL int n_remove(mp_limb_t * n, mp_limb_t p);
FLINT_DLL int n_remove2_precomp(mp_limb_t * n, mp_limb_t p, double ppre);
ULONG_EXTRAS_INLINE
void n_factor_init(n_factor_t * factors)
{
factors->num = UWORD(0);
}
FLINT_DLL void n_factor_insert(n_factor_t * factors, mp_limb_t p, ulong exp);
FLINT_DLL mp_limb_t n_factor_trial_range(n_factor_t * factors,
mp_limb_t n, ulong start, ulong num_primes);
FLINT_DLL mp_limb_t n_factor_trial_partial(n_factor_t * factors, mp_limb_t n,
mp_limb_t * prod, ulong num_primes, mp_limb_t limit);
FLINT_DLL mp_limb_t n_factor_trial(n_factor_t * factors,
mp_limb_t n, ulong num_primes);
FLINT_DLL mp_limb_t n_factor_partial(n_factor_t * factors,
mp_limb_t n, mp_limb_t limit, int proved);
FLINT_DLL mp_limb_t n_factor_power235(ulong *exp, mp_limb_t n);
FLINT_DLL mp_limb_t n_factor_one_line(mp_limb_t n, ulong iters);
FLINT_DLL mp_limb_t n_factor_lehman(mp_limb_t n);
FLINT_DLL mp_limb_t n_factor_SQUFOF(mp_limb_t n, ulong iters);
FLINT_DLL void n_factor(n_factor_t * factors, mp_limb_t n, int proved);
FLINT_DLL mp_limb_t n_factor_pp1(mp_limb_t n, ulong B1, ulong c);
FLINT_DLL int n_is_squarefree(mp_limb_t n);
FLINT_DLL int n_moebius_mu(mp_limb_t n);
FLINT_DLL void n_moebius_mu_vec(int * mu, ulong len);
FLINT_DLL mp_limb_t n_euler_phi(mp_limb_t n);
FLINT_DLL int n_sizeinbase(mp_limb_t n, int base);
FLINT_DLL mp_limb_t n_nextprime(mp_limb_t n, int proved);
FLINT_DLL mp_limb_t n_factorial_mod2_preinv(ulong n, mp_limb_t p, mp_limb_t pinv);
FLINT_DLL mp_limb_t n_factorial_fast_mod2_preinv(ulong n, mp_limb_t p, mp_limb_t pinv);
FLINT_DLL mp_limb_t n_primitive_root_prime_prefactor(mp_limb_t p, n_factor_t * factors);
FLINT_DLL mp_limb_t n_primitive_root_prime(mp_limb_t p);
FLINT_DLL mp_limb_t n_discrete_log_bsgs(mp_limb_t b, mp_limb_t a, mp_limb_t n);
FLINT_DLL mp_limb_t n_root_estimate(double a, int n);
FLINT_DLL mp_limb_t n_rootrem(mp_limb_t* remainder, mp_limb_t n, mp_limb_t root);
FLINT_DLL mp_limb_t n_root(mp_limb_t n, mp_limb_t root);
#ifdef __cplusplus
}
#endif
#endif
|