217 xl = (ap[
n - 1] << 63) | (ap[
n - 2] >> 1);
219 yl = (bp[
n - 1] << 63) | (bp[
n - 2] >> 1);
220 }
else if (kz == 63) {
227 xh = (ap[
n - 1] << sh) | (ap[
n - 2] >> (64 - sh));
228 xl = (ap[
n - 2] << sh) | (ap[
n - 3] >> (64 - sh));
229 yh = (bp[
n - 1] << sh) | (bp[
n - 2] >> (64 - sh));
230 yl = (bp[
n - 2] << sh) | (bp[
n - 3] >> (64 - sh));
232 if (xh == yh && xl == yl) {
240 mp_limb_t u00 = 1, u01 = 0, u10 = 0, u11 = 1;
249 rh = uh - al - bh - (ul < bl);
251 while (rh >
vh || (rh ==
vh && rl >= vl)) {
255 int borrow = rl < vl;
257 rh = rh -
vh - borrow;
276 if (u00 == 1 && u01 == 0 && u10 == 0 && u11 == 1) {
314 *detsign *= (dhi > ehi || (dhi == ehi && dlo >= elo)) ? 1 : -1;
320 for (
int row = 0; row < 2; ++row) {
329 if (u01 == 0 || l0 == 0) {
330 if (u11 == 0 || l1 == 0) {
337 }
else if (u11 == 0 || l1 == 0) {
352 l1n = L + (
t[L] != 0);
353 if (
t[l1n - 1] == 0 && l1n > 1) {
356 if (
t[l1n - 1] == 0 && l1n > 1) {
362 if (u00 == 0 || l0 == 0) {
363 if (u10 == 0 || l1 == 0) {
370 }
else if (u10 == 0 || l1 == 0) {
382 l0n = L + (
c0[L] != 0);
383 if (
c0[l0n - 1] == 0 && l0n > 1) {
386 if (
c0[l0n - 1] == 0 && l0n > 1) {
434 *detsign = -*detsign;
445 for (
int row = 0; row < 2; ++row) {
457 lt = qn + l0 - (
t[qn + l0 - 1] == 0);
471 lt = m + (carry != 0);
473 if (
t[lt - 1] == 0 && lt > 1) {
476 if (
t[lt - 1] == 0 && lt > 1) {
481 int dst = col == 0 ? 0 : 1;
503 M->
m[0][1] = buf + alloc;
504 M->
m[1][0] = buf + 2 * alloc;
505 M->
m[1][1] = buf + 3 * alloc;
528 if (M->
n[0][0] == 1 && M->
m[0][0][0] == 1
529 && M->
n[1][1] == 1 && M->
m[1][1][0] == 1
530 && M->
n[0][1] == 0 && M->
n[1][0] == 0) {
532 for (
int i = 0; i < 2; ++i) {
533 for (
int j = 0; j < 2; ++j) {
535 M->
n[i][j] =
M1->n[i][j];
577 if (
n - p < mn ||
n < p + mn) {
590 mp_size_t n11 =
M1->n[1][1], n10 =
M1->n[1][0], n01 =
M1->n[0][1], n00 =
M1->n[0][0];
620 mp_ptr adda = det > 0 ? t0 : t2;
621 mp_ptr suba = det > 0 ? t2 : t0;
622 mp_ptr addb = det > 0 ? t3 : t1;
623 mp_ptr subb = det > 0 ? t1 : t3;
644 carry =
lmmp_add_(dbp + p, dbp + p,
n - p, addb + p, mn);
649 borrow =
lmmp_sub_(dbp, dbp,
n, subb, p + mn);
662 while (la > 0 && dap[la - 1] == 0) {
666 while (lb > 0 && dbp[lb - 1] == 0) {
719 int det = (dhi > ehi || (dhi == ehi && dlo >= elo)) ? 1 : -1;
746 if (
an < fl ||
bn < fl) {
855 lmmp_zero(dst + (sn <= rn ? sn : rn), rn - (sn <= rn ? sn : rn));
910 if (
bn - m10 < un) un =
bn > m10 ?
bn - m10 : 1;
912 if (
bn > m11 &&
bn - m11 < vn) vn =
bn - m11;
983 if (alen > nn || lb > nn) {
989 mp_size_t rn_out = alen > lb ? alen : lb;
1064 rn =
lmmp_hgcd_adjust_(&
M1, dsub, sa, sb, &blen, ha, hb, nn, ap, bp, n0, p, sc);
1067 if (rn > 0 && rn < n0 && blen > maxlen) {
1094 return success ?
n : 0;
1142 rn =
lmmp_hgcd_adjust_(&
M1, dsub, sa, sb, &blen, ha, hb, nn, ap, bp,
n, p2, sc);
1145 if (rn > 0 && rn < n && blen > maxlen) {
1173 return success ?
n : 0;
1178 return success ?
n : 0;
1195 M->
n[0][0] = M->
n[0][1] = M->
n[1][0] = M->
n[1][1] = 0;
1227 mp_ptr pre0 = NULL, pre1 = NULL;
1233 while (un >= 2 * vn) {
1234 mp_ptr rp = (vp == pre0) ? pre1 : pre0;
1237 while (rn > 0 &&
rp[rn - 1] == 0) {
1276 }
else if (cmp < 0) {
1295 if (nn == 0 || nn >= cur) {
mp_size_t lmmp_hgcd_scratch_size_(mp_size_t n)
计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
mp_size_t lmmp_hgcd_core_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n, lmmp_hgcd_scratch_t *sc, int *detsign, int appr)
hgcd 递归核:将数对归约至约 n/2 规模并累积变换矩阵(详见 hgcd.c 实现注)
static mp_size_t lmmp_gcd_norm_(mp_srcptr p, mp_size_t n)
mp_size_t lmmp_hgcd_adjust_(lmmp_hgcd_matrix_t *M1, int detsign, mp_ptr dap, mp_ptr dbp, mp_size_t *blen, mp_srcptr ha, mp_srcptr hb, mp_size_t hn0, mp_srcptr ap, mp_srcptr bp, mp_size_t n, mp_size_t p, lmmp_hgcd_scratch_t *sc)
高位直写 + 低位修补:将子递归成果(矩阵 M1 与归约后的高位对)合入完整数对
#define HGCD_RECURSE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
static mp_ptr lmmp_hgcd_salloc_(lmmp_hgcd_scratch_t *sc, mp_size_t n)
static mp_size_t lmmp_gcd_matrix_maxlen_(const lmmp_hgcd_matrix_t *M)
static void lmmp_gcd_mul_(mp_ptr dst, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)
static void lmmp_gcd_matrix_swap_cols_(lmmp_hgcd_matrix_t *M)
static int lmmp_hgcd_lehmer2_(mp_limb_t *pu00, mp_limb_t *pu01, mp_limb_t *pu10, mp_limb_t *pu11, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
在 [ap,n] 与 [bp,n] 的 127 位顶端近似上运行小规模欧几里得,累积单 limb 矩阵 U
static void lmmp_hgcd_matrix_init_buf_(lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc)
将连续缓冲初始化为单位矩阵
static void lmmp_hgcd_fold_mod_(mp_ptr dst, mp_srcptr src, mp_size_t sn, mp_size_t rn)
将 [src,sn] 折叠为模 B^rn-1 的表示:写入 [dst,rn)
static void lmmp_hgcd_matrix_mul_u_(lmmp_hgcd_matrix_t *M, lmmp_hgcd_scratch_t *sc, int *detsign, mp_limb_t u00, mp_limb_t u01, mp_limb_t u10, mp_limb_t u11)
M <- M*U,U 为单 limb 元素的非负矩阵
static mp_size_t lmmp_hgcd_apply_mod_(lmmp_hgcd_matrix_t *M1, int detsign, mp_ptr dap, mp_ptr dbp, mp_size_t *blen, mp_srcptr ap, mp_srcptr bp, mp_size_t n, int use_cache, lmmp_hgcd_scratch_t *sc)
模 B^rn-1 梅森乘法版矩阵应用: new = adj(M1)*(a;b),经 4 次模乘与模减精确重构
static mp_size_t lmmp_hgcd_step_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n, mp_size_t fl, lmmp_hgcd_scratch_t *sc, int *detsign)
单步步进:用近似矩阵 U 或一次(可能部分的)除法归约数对
static void lmmp_hgcd_matrix_mul_(lmmp_hgcd_matrix_t *M, const lmmp_hgcd_matrix_t *M1, lmmp_hgcd_scratch_t *sc)
M <- M*M1(经由库内 lmmp_mat22_mul_,按元素最大长度自动分派 basecase / Winograd-Strassen 路径)
static void lmmp_hgcd_matrix_update_q_(lmmp_hgcd_matrix_t *M, lmmp_hgcd_scratch_t *sc, int *detsign, mp_srcptr q, mp_size_t qn, int col)
真除法步进的矩阵累积
#define LMMP_SWAP(x, y, type)
交换两个变量的值
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
#define lmmp_debug_assert(x)
const mp_limb_t * mp_srcptr
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define LMMP_MAX(h, i)
返回两个数中的较大值
#define LMMP_VECT_CONSERVATIVE
#define lmmp_param_assert(x)
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
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
#define lmmp_dec(p)
减1宏(预期无借位)
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
#define lmmp_inc(p)
加1宏(预期无进位)
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
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_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
mp_limb_t lmmp_submul_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_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
void lmmp_mat22_mul_(lmmp_mat22_t *dst, const lmmp_mat22_t *a, const lmmp_mat22_t *b, mp_ptr tp)
计算 D <- A*B(2x2 非负矩阵乘法)
Copyright (C) 2026 HJimmyK (Jericho Knox)
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_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
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 HGCD_MODMUL_CACHE_THRESHOLD
#define HGCD_MODMUL_THRESHOLD
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
mp_size_t lmmp_hgcd_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n)
半扩展欧几里得:将数对原地归约至约一半规模,并累积变换矩阵
mp_size_t lmmp_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
void lmmp_hgcd_matrix_free_(lmmp_hgcd_matrix_t *M)
释放 hgcd 变换矩阵的元素缓冲
void lmmp_hgcd_matrix_init_(lmmp_hgcd_matrix_t *M, mp_size_t alloc)
初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲)
#define ALLOC_TYPE(n, type)