23#ifndef __LMMP_IMPL_GCD_H__
24#define __LMMP_IMPL_GCD_H__
33#define HGCD_RECURSE_THRESHOLD 64
50 while (
n > 0 && p[
n - 1] == 0) {
80 M->
m[0][1] = buf + alloc;
81 M->
m[1][0] = buf + 2 * alloc;
82 M->
m[1][1] = buf + 3 * alloc;
100#define GCD_LEHMER_MIN_V 0x100000000ll
101#define GCD_LEHMER_EXACT_BITS 63
156 }
else if (un == vn + 1) {
212 while (*
n > 0 && dst[*
n - 1] == 0)
mp_size_t lmmp_hgcd_scratch_size_(mp_size_t n)
计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
static void lmmp_gcd_lehmer_step_(slong u, slong v, lmmp_gcd_lehmer_t *M)
static void lmmp_gcd_lehmer_extract_(mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, slong *restrict a, slong *restrict b)
static void lmmp_gcdext_smag_(mp_ptr dst, mp_size_t *n, int *neg, mp_srcptr x, mp_size_t xn, int xneg, mp_srcptr y, mp_size_t yn, int yneg)
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 实现注)
#define GCD_LEHMER_EXACT_BITS
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 与归约后的高位对)合入完整数对
mp_size_t lmmp_gcdext_derive_(mp_ptr dst, int *tneg, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sn, int sneg, mp_srcptr xp, mp_size_t xn, mp_srcptr yp, mp_size_t yn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除)
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)
void lmmp_gcdext_emit_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sun, int suneg, int sw, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
发射:g 与 S(值序大者系数)按 sw 映射到 (dsts,dstt),另一系数经恒等式导出
static void lmmp_gcd_matrix_init_buf_(lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc)
static void lmmp_gcd_matrix_swap_cols_(lmmp_hgcd_matrix_t *M)
#define LMMP_SWAP(x, y, type)
交换两个变量的值
#define lmmp_copy(dst, src, n)
#define lmmp_debug_assert(x)
const mp_limb_t * mp_srcptr
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]
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]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, 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]
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)