37#if !defined(DOXYGEN) &&__has_c_attribute(gnu::access) && 0
38#define NUT_ATTR_ACCESS(...) [[gnu::access(__VA_ARGS__)]]
40#define NUT_ATTR_ACCESS(...)
44#if !defined(DOXYGEN) && __has_c_attribute(clang::no_sanitize)
45#define NUT_ATTR_NO_SAN(name) [[clang::no_sanitize(name)]]
47#define NUT_ATTR_NO_SAN(name)
52#define NUT_ATTR_CONST [[gnu::const]]
59#define NUT_ATTR_PURE [[gnu::pure]]
66#define NUT_ATTR_NODISCARD [[nodiscard]]
68#define NUT_ATTR_NODISCARD
73#define NUT_ATTR_NONNULL(...) [[gnu::nonnull(__VA_ARGS__)]]
75#define NUT_ATTR_NONNULL(...)
80#define NUT_ATTR_RETURNS_NONNULL [[gnu::returns_nonnull]]
82#define NUT_ATTR_RETURNS_NONNULL
87#define NUT_ATTR_MALLOC [[gnu::malloc]]
89#define NUT_ATTR_MALLOC
94#define NUT_ATTR_ARTIFICIAL [[gnu::artificial]]
96#define NUT_ATTR_ARTIFICIAL
158int64_t
nut_i64_egcd(int64_t a, int64_t b, int64_t *restrict _t, int64_t *restrict _s);
uint64_t nut_u64_rand(uint64_t a, uint64_t b)
Generate a (strong) random integer uniformly from [a, b).
int64_t nut_i64_sqrt_cipolla(int64_t n, int64_t p)
Compute the square root of a quadratic residue mod a prime.
int64_t nut_i64_sqrt_mod(int64_t n, int64_t p)
Compute the square root of a quadratic residue mod a prime.
int64_t nut_u64_jacobi_tbl_get(uint64_t n, uint64_t p, const uint64_t is_qr[restrict static(p+63)/64])
Convenience function to get the jacobi symbol for n from a table The table should come from nut_u64_m...
int64_t nut_i64_fastmod_trunc(int64_t n, uint64_t pd, uint128_t c)
Compute n mod d, choosing the smallest signed remainder.
int64_t nut_i64_modinv(int64_t a, int64_t b)
Find the multiplicative inverse of a mod b If b is a power of 2, use nut_i64_modinv_2t Just a wrapper...
int64_t nut_i64_rand_nr_mod(int64_t p)
Compute a random number mod a prime that is not a quadratic residue.
uint128_t nut_u64_fastmod_init(uint64_t d)
Compute a constant to use to do modular division faster.
uint64_t nut_u32_fastmod_init(uint32_t d)
Compute a constant to use to do modular division faster.
unsigned __int128 uint128_t
Pretty name for unsigned 128 bit integer.
uint64_t nut_i32_fastmod_init(uint32_t pd)
Compute a constant to use to do modular division faster.
uint64_t nut_u64_powmod(uint64_t b, uint64_t e, uint64_t n)
Compute nonnegative integral power of a number modulo another using binary exponentiation.
signed __int128 int128_t
Pretty name for signed 128 bit integer.
int128_t nut_i128_crt(int64_t a, int64_t p, int64_t b, int64_t q)
Compute n mod pq st n = a mod p and n = b mod q, where p and q are coprime.
int64_t nut_i64_mod(int64_t a, int64_t n)
Compute the Euclidean remainder r = a mod n for positive n so that 0 <= r < n.
uint64_t * nut_u64_make_jacobi_tbl(uint64_t p, int64_t partial_sums[restrict static p])
Compute the Jacobi symbol for all numbers mod a prime.
int32_t nut_i32_fastmod_floor(int32_t n, uint32_t pd, uint64_t c)
Compute n mod d, choosing the euclidean remainder.
#define NUT_ATTR_ACCESS(...)
Wrapper for gcc's access function annotation - no clang equivalent, and currently disabled because it...
#define NUT_ATTR_NONNULL(...)
Wrapper for gnu::nonnull attr.
int64_t nut_i64_lcm(int64_t a, int64_t b)
Compute the least common multiple of a and b Divides the product by the gcd so can overflow for large...
int64_t nut_i64_crt(int64_t a, int64_t p, int64_t b, int64_t q)
Compute n mod pq st n = a mod p and n = b mod q, where p and q are coprime.
uint64_t nut_u64_binom_next_mod_2t(uint64_t n, uint64_t k, uint64_t t, uint64_t *restrict v2, uint64_t *restrict p2)
Compute the binomial coefficient for (n choose k) given the binomial coefficient for (n choose k-1) S...
uint64_t nut_u64_pow(uint64_t b, uint64_t e)
Compute nonnegative integral power of integer using binary exponentiation.
uint32_t nut_u32_fastmod(uint32_t n, uint32_t d, uint64_t c)
Compute n mod d faster using a precomputed constant.
uint64_t nut_u64_binom(uint64_t n, uint64_t k)
Compute single binomial coefficient semi-naively.
int64_t nut_i64_jacobi(int64_t n, int64_t k)
Compute the Jacobi symbol of n mod k.
uint128_t nut_i64_fastmod_init(uint64_t pd)
Compute a constant to use to do modular division faster.
int64_t nut_i64_egcd(int64_t a, int64_t b, int64_t *restrict _t, int64_t *restrict _s)
Compute d = gcd(a, b) and x, y st.
uint64_t nut_u64_binom_next(uint64_t n, uint64_t k, uint64_t prev)
Compute the binomial coefficient for (n choose k) given the binomial coefficient for (n choose k-1) S...
uint128_t nut_u128_pow(uint128_t b, uint64_t e)
Compute nonnegative integral power of integer using binary exponentiation.
#define NUT_ATTR_NODISCARD
Wrapper for nodiscard attr - requires return value be used.
#define NUT_ATTR_CONST
Wrapper for gnu::const attr - such a function has no side effects and cannot read memory.
#define NUT_ATTR_MALLOC
Wrapper for gnu::malloc attr - indicates the function returns a malloc'd pointer that must be free'd.
uint64_t nut_u64_modinv_2t(uint64_t a, uint64_t t)
Find the multiplicative inverse of a mod 2**t This uses a hensel/newton like iterative algorithm,...
uint64_t nut_u64_fastmod(uint64_t n, uint64_t d, uint128_t c)
Compute n mod d faster using a precomputed constant.
int64_t nut_i64_fastmod_floor(int64_t n, uint64_t pd, uint128_t c)
Compute n mod d, choosing the euclidean remainder.
int64_t nut_i64_sqrt_shanks(int64_t n, int64_t p)
Compute the square root of a quadratic residue mod a prime.
int32_t nut_i32_fastmod_trunc(int32_t n, uint32_t pd, uint64_t c)
Compute n mod d, choosing the smallest signed remainder.
uint64_t nut_u64_prand(uint64_t a, uint64_t b)
Generate a (pseudo)random integer uniformly from [a, b).