|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
结构体 | |
| struct | lmmp_gcd_lehmer_t |
| struct | lmmp_hgcd_scratch_t |
宏定义 | |
| #define | A (M->m11) |
| #define | B (M->m12) |
| #define | C (M->m21) |
| #define | D (M->m22) |
| #define | GCD_LEHMER_EXACT_BITS 63 |
| #define | GCD_LEHMER_MIN_V 0x100000000ll |
| #define | HGCD_RECURSE_THRESHOLD 64 |
| Copyright (C) 2026 HJimmyK (Jericho Knox) | |
| struct lmmp_gcd_lehmer_t |
| struct lmmp_hgcd_scratch_t |
| #define A (M->m11) |
| #define B (M->m12) |
| #define C (M->m21) |
被这些函数引用 lmmp_gcd_lehmer_step_(), lmmp_lehmer_mul_() , 以及 lmmp_xoshiro256pp_srandom().
| #define D (M->m22) |
被这些函数引用 lmmp_divexact_basecase_(), lmmp_gcd_lehmer_step_() , 以及 lmmp_lehmer_mul_().
| #define GCD_LEHMER_EXACT_BITS 63 |
被这些函数引用 lmmp_gcd_lehmer_extract_().
| #define GCD_LEHMER_MIN_V 0x100000000ll |
被这些函数引用 lmmp_gcd_lehmer_step_().
| #define HGCD_RECURSE_THRESHOLD 64 |
Copyright (C) 2026 HJimmyK (Jericho Knox)
This file is part of LMMP.
LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
This library 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 Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.
SPDX-License-Identifier: LGPL-3.0-or-later
被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_core_() , 以及 lmmp_hgcd_scratch_size_().
|
inlinestatic |
引用了 GCD_LEHMER_EXACT_BITS, LIMB_BITS, lmmp_gcd_lehmer_extract_(), lmmp_limb_bits_ , 以及 restrict.
被这些函数引用 lmmp_gcd_lehmer_(), lmmp_gcd_lehmer_extract_() , 以及 lmmp_gcdext_lehmer_().
|
inlinestatic |
引用了 A, B, C, D, GCD_LEHMER_MIN_V, lmmp_gcd_lehmer_step_() , 以及 t.
被这些函数引用 lmmp_gcd_lehmer_(), lmmp_gcd_lehmer_step_() , 以及 lmmp_gcdext_lehmer_().
|
inlinestatic |
引用了 lmmp_hgcd_matrix_t::alloc, lmmp_debug_assert, lmmp_gcd_matrix_init_buf_(), lmmp_hgcd_matrix_t::m , 以及 lmmp_hgcd_matrix_t::n.
被这些函数引用 lmmp_gcd_matrix_init_buf_() , 以及 lmmp_gcdext_hgcd_().
|
inlinestatic |
引用了 lmmp_gcd_matrix_maxlen_() , 以及 lmmp_hgcd_matrix_t::n.
被这些函数引用 gcdext_row_mul_(), lmmp_gcd_matrix_maxlen_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_adjust_(), lmmp_hgcd_apply_mod_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_mul_(), lmmp_hgcd_matrix_mul_u_() , 以及 lmmp_hgcd_matrix_update_q_().
|
inlinestatic |
引用了 lmmp_gcd_matrix_swap_cols_(), LMMP_SWAP, lmmp_hgcd_matrix_t::m , 以及 lmmp_hgcd_matrix_t::n.
被这些函数引用 lmmp_gcd_matrix_swap_cols_(), lmmp_gcdext_hgcd_() , 以及 lmmp_hgcd_core_().
|
inlinestatic |
引用了 an, bn, lmmp_gcd_mul_() , 以及 lmmp_mul_().
被这些函数引用 gcdext_row_mul_(), lmmp_gcd_mul_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_adjust_() , 以及 lmmp_hgcd_matrix_update_q_().
引用了 lmmp_gcd_norm_() , 以及 n.
被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcd_norm_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_apply_mod_() , 以及 lmmp_hgcd_step_().
| 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 侧系数,恒等式保证整除)
| dst | 输出(容量 >= xn+2) |
| tneg | 出参,tv 的符号 |
| gp | g(归一化) |
| gn | g 的长度 |
| sp | S 的幅度(归一化) |
| sn | S 的幅度长 |
| sneg | S 的符号 |
| xp | 值序大者原对(归一化) |
| xn | 其长度 |
| yp | 值序小者原对(归一化) |
| yn | 其长度 |
| nb | 全乘积暂存(容量 >= xn+yn+2) |
| yt | Y 奇化暂存(容量 >= yn+1) |
| qt | 整商暂存(容量 >= xn+2;lmmp_divexact_ 写入长 nn-yn2+1 可超 出 dst 公开容量,先落此处再按归一化长度拷出) |
引用了 ctz_shr_u64, lmmp_add_(), lmmp_copy, lmmp_debug_assert, lmmp_divexact_(), lmmp_gcdext_derive_(), lmmp_mul_(), lmmp_shr_(), lmmp_sub_(), xn , 以及 xp.
被这些函数引用 lmmp_gcdext_derive_() , 以及 lmmp_gcdext_emit_().
| 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),另一系数经恒等式导出
| dstg | 结果 g 输出(容量 >= gn) |
| dsts | u 侧系数输出(容量 >= max(un,vn)+1) |
| sn | 输出 s 的带符号长度 |
| dstt | v 侧系数输出(容量 >= max(un,vn)+1,可为 NULL 表示不需要) |
| tn | 输出 t 的带符号长度(dstt==NULL 时忽略,可为 NULL) |
| gp | g(归一化) |
| gn | g 的长度 |
| sp | S 的幅度(归一化) |
| sun | S 的幅度长 |
| suneg | S 的符号 |
| sw | 值序归一化的交换标志(1 表示 up/vp 已交换,S 为 vp 侧系数) |
| up | 值序大者原对 |
| un | 其长度 |
| vp | 值序小者原对 |
| vn | 其长度 |
| nb | 导出全乘积暂存(容量 >= 2*max(un,vn)+4) |
| yt | 导出奇化暂存(容量 >= max(un,vn)+2) |
| qt | 导出整商暂存(容量 >= max(un,vn)+2) |
引用了 lmmp_copy, lmmp_gcdext_derive_() , 以及 lmmp_gcdext_emit_().
被这些函数引用 lmmp_gcdext_emit_(), lmmp_gcdext_hgcd_() , 以及 lmmp_gcdext_lehmer_().
|
inlinestatic |
引用了 lmmp_add_(), lmmp_cmp_(), lmmp_copy, lmmp_gcdext_smag_(), lmmp_sub_(), n , 以及 xn.
被这些函数引用 lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_() , 以及 lmmp_gcdext_smag_().
| 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 与归约后的高位对)合入完整数对
| M1 | 子递归累积的矩阵(各元素输入长度为 M1->n 个limb) |
| detsign | det(M1) 的符号,[1|-1] |
| dap | 分量 a 输出数组(写入 n 个limb,返回 0 时内容无效) |
| dbp | 分量 b 输出数组(写入 n 个limb,返回 0 时内容无效) |
| blen | 出参,分量 b 合入后的真实长度(供上层校验) |
| ha | 子递归归约后的高位 a(长度为 hn0 个limb,可为 ap+p 原地) |
| hb | 子递归归约后的高位 b(长度为 hn0 个limb) |
| hn0 | 子递归返回的公共长度,hn0<=n-p |
| ap | 源完整较大分量(长度为 n 个limb,低 p 位参与修补) |
| bp | 源完整较小分量(长度为 n 个limb) |
| n | ap,bp 的公共长度 |
| p | 高低位分裂点 |
| sc | 临时空间(4*(p+M1->n+1) 个limb) |
引用了 lmmp_add_(), lmmp_copy, lmmp_gcd_matrix_maxlen_(), lmmp_gcd_mul_(), lmmp_hgcd_adjust_(), lmmp_hgcd_salloc_(), lmmp_sub_(), lmmp_zero, M1, n , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 lmmp_gcdext_hgcd_(), lmmp_hgcd_adjust_() , 以及 lmmp_hgcd_core_().
| 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 实现注)
| M | 变换矩阵:入口应为单位矩阵,出口累积全部归约变换 |
| ap | 较大分量输入兼输出数组(输入读 [ap,n),ap[n-1]>0;输出写 [ap,rn) 并零填充至 rn) |
| bp | 较小分量输入兼输出数组(允许高位为零,输出零填充至 rn) |
| n | ap,bp 的公共输入长度 |
| sc | 临时空间(容量由 lmmp_hgcd_scratch_size_ 给出) |
| detsign | 出参,返回 det(M) 的符号 |
| appr | 1 表示近似模式(仅矩阵累积,数对停留在约 3n/4;见 hgcd.c 实现注) |
引用了 lmmp_hgcd_matrix_t::alloc, HGCD_MODMUL_CACHE_THRESHOLD, HGCD_MODMUL_THRESHOLD, HGCD_RECURSE_THRESHOLD, lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_gcd_matrix_maxlen_(), lmmp_gcd_matrix_swap_cols_(), lmmp_hgcd_adjust_(), lmmp_hgcd_apply_mod_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_init_buf_(), lmmp_hgcd_matrix_mul_(), lmmp_hgcd_salloc_(), lmmp_hgcd_step_(), lmmp_zero_q_(), M1, n, s , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_() , 以及 lmmp_hgcd_core_().
|
inlinestatic |
引用了 lmmp_hgcd_scratch_t::base, lmmp_debug_assert, lmmp_hgcd_salloc_(), n , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 gcdext_row_mul_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_adjust_(), lmmp_hgcd_apply_mod_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_mul_(), lmmp_hgcd_matrix_mul_u_(), lmmp_hgcd_matrix_update_q_(), lmmp_hgcd_salloc_() , 以及 lmmp_hgcd_step_().
计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
Copyright (C) 2026 HJimmyK (Jericho Knox)
| n | 输入长度 |
计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
This file is part of LMMP.
LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
This library 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 Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.
SPDX-License-Identifier: LGPL-3.0-or-later
计算 hgcd 内部临时空间大小
| n | 输入长度 |
引用了 HGCD_RECURSE_THRESHOLD, lmmp_hgcd_scratch_size_() , 以及 n.
被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_() , 以及 lmmp_hgcd_scratch_size_().