40 for (i = 0; i < nn - 1; i++) {
67 mp_limb_t ddinv0 = dinv[0], ddinv1 = dinv[1];
70 for (i = 0; i < nn - 2; i += 2) {
71 s = _u128load(np + i);
76 dst[i + 1] = _u128high(q);
78 c += _u128load(
t + 2);
80 s = _u128load(np + i);
89 for (; i < nn - 4; i += 2) {
90 s = _u128load(np + i);
95 dst[i + 1] = _u128high(q);
97 c += _u128load(
t + 2);
100 s = _u128load(np + i);
104 dst[i] = _u128low(q);
105 dst[i + 1] = _u128high(q);
146#define prod (tp + dn)
170 }
else if (ms_mode == 1) {
200 }
else if (ms_mode == 1) {
289 const mp_limb_t ninv2 = ninv1 * e + dp[1] * ninv1 * ninv1;
294#define LMMP_DIVX_PUT(k, qv) \
296 mp_limb_t _q_ = (qv); \
297 dst[k] = ~_q_ + negc; \
298 negc &= (mp_limb_t)(_q_ == 0); \
305 for (; qn - i >=
D + 2; i += 2, up += 2) {
308 q[1] = qh + up[0] * ninv2 + up[1] * ninv1;
326 if (qn - i ==
D + 1) {
336 for (
mp_size_t w = qn - i; w >= 2; w -= 2, i += 2, up += 2) {
339 q[1] = qh + up[0] * ninv2 + up[1] * ninv1;
394 }
else if (dn == 2) {
406 }
else if (qn < dn) {
static void lmmp_mullo_n_(mp_ptr restrict dst, mp_srcptr restrict numa, mp_srcptr restrict numb, mp_size_t n, mp_ptr restrict tp)
static void lmmp_divexact_mu_run_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr restrict dp, mp_size_t dn, mp_srcptr restrict dinv, mp_size_t in, mp_ptr restrict tp)
#define LMMP_DIVX_PUT(k, qv)
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
#define lmmp_debug_assert(x)
const mp_limb_t * mp_srcptr
#define lmmp_param_assert(x)
#define MULLO_DC_THRESHOLD
void lmmp_mul_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
mp_limb_t lmmp_addmul_2_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_srcptr bp)
乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]
void lmmp_mullo_dc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_ptr tp, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
#define lmmp_inc(p)
加1宏(预期无进位)
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
void lmmp_mullo_fft_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch)
低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
mp_limb_t lmmp_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
static __uint128_t _umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)
void lmmp_mul_mersenne_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static void lmmp_mullo_cache_free_(fft_mullo_cache *ctx)
释放 mullo 缓存上下文
void lmmp_mullo_fft_cache_(mp_ptr dst, mp_srcptr numa, mp_ptr scratch, fft_mullo_cache *ctx)
低位乘法(缓存版) [dst,n] = [numa,n] * 缓存numb mod B^n
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
void lmmp_mullo_fft_cache_init_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch, fft_mullo_cache *ctx)
低位乘法(缓存版) [dst,n] = [numa,n] * [numb,n] mod B^n 第二个操作数将被缓存
void lmmp_mul_mersenne_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1 第二个操作数将被缓存
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define DIVEXACT_NN_THRESHOLD
#define DIVEXACT_MERSENNE_CACHE_THRESHOLD
#define DIVEXACT_MERSENNE_THRESHOLD
#define DIVEXACT_BASECASE_THRESHOLD
void lmmp_divexact_unbalance_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_ptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
void lmmp_binvert_n_dc_(mp_ptr dst, mp_srcptr numa, mp_size_t n, mp_ptr tp)
计算 [numa,n] 在 B^n 下的逆元
void lmmp_divexact_basecase_(mp_ptr dst, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
void lmmp_divexact_1_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_limb_t d, mp_limb_t dinv)
精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
void lmmp_divexact_2_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_srcptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0)
void lmmp_divexact_divide_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TALLOC_TYPE(n, type)