|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
#include "numth/gcd.h"#include "impl/longlong.h"#include "mparam.h"#include "numth/mat22_mul.h"#include "impl/mul_cache.h"#include "impl/tmp_alloc.h"#include "lmmp/lmmpn.h"#include "lmmp/numth.h"函数 | |
| mp_size_t | lmmp_gcd_hgcd_ (mp_ptr dst, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn) |
| 计算两个无符号整数的最大公约数(hgcd 分治,长输入优选) | |
| mp_size_t | lmmp_hgcd_ (lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, 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 与归约后的高位对)合入完整数对 | |
| 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 次模乘与模减精确重构 | |
| 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 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 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 | |
| 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 变换矩阵为单位矩阵(堆分配元素缓冲) | |
| static void | lmmp_hgcd_matrix_init_buf_ (lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc) |
| 将连续缓冲初始化为单位矩阵 | |
| 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_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 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) |
| 真除法步进的矩阵累积 | |
| mp_size_t | lmmp_hgcd_scratch_size_ (mp_size_t n) |
| Copyright (C) 2026 HJimmyK (Jericho Knox) | |
| 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 或一次(可能部分的)除法归约数对 | |
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
| dst | 结果指针(长度至少为 bn) |
| up | 第一个无符号整数数组(长度为 un 个limb) |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数数组(长度为 vn 个limb) |
| vn | 第二个无符号整数的 limb 长度 |
引用了 ALLOC_TYPE, an, bn, HGCD_RECURSE_THRESHOLD, lmmp_cmp_(), lmmp_copy, lmmp_div_(), lmmp_free(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), lmmp_gcd_norm_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_init_buf_(), lmmp_hgcd_scratch_size_(), lmmp_param_assert, LMMP_SWAP, lmmp_zero, lmmp_zero_q_() , 以及 rp.
被这些函数引用 bench_gcd_hgcd(), lmmp_gcd_(), lmmp_gcd_hgcd_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
| mp_size_t lmmp_hgcd_ | ( | lmmp_hgcd_matrix_t * | M, |
| mp_ptr | ap, | ||
| mp_ptr | bp, | ||
| mp_size_t | n ) |
半扩展欧几里得:将数对原地归约至约一半规模,并累积变换矩阵
| M | 变换矩阵(入口应为单位矩阵,出口满足 (a;b) = M*(a';b')) |
| ap | 较大分量输入兼输出数组(长度为 n 个limb,出口保证较大者位于 ap) |
| bp | 较小分量输入兼输出数组(长度为 n 个limb,允许高位零填充) |
| n | ap,bp 的公共长度 |
引用了 lmmp_hgcd_matrix_t::alloc, ALLOC_TYPE, lmmp_cmp_(), lmmp_debug_assert, lmmp_free(), lmmp_hgcd_(), lmmp_hgcd_core_(), lmmp_hgcd_scratch_size_(), lmmp_param_assert , 以及 n.
被这些函数引用 lmmp_hgcd_() , 以及 TEST_CASE().
| 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_().
|
static |
模 B^rn-1 梅森乘法版矩阵应用: new = adj(M1)*(a;b),经 4 次模乘与模减精确重构
| M1 | 子递归累积的矩阵(只读,各元素长度为 M1->n 个limb,M1->n<rn) |
| detsign | det(M1) 的符号,[1|-1] |
| dap | 分量 a 输出数组(写入 rn_out 个limb,rn_out 为返回值;返回 0 时内容无效) |
| dbp | 分量 b 输出数组(写入 rn_out 个limb) |
| ap | 源完整较大分量(只读,长度为 n 个limb) |
| bp | 源完整较小分量(只读,长度为 n 个limb) |
| n | ap,bp 的公共长度 |
| sc | 临时空间(6*rn 个limb;FFT 缓存上下文另行经由库内临时池分配) |
引用了 an, bn, lmmp_copy, lmmp_fft_gr_cache_free_(), lmmp_fft_next_size_(), lmmp_gcd_matrix_maxlen_(), lmmp_gcd_norm_(), lmmp_hgcd_apply_mod_(), lmmp_hgcd_fold_mod_(), lmmp_hgcd_salloc_(), lmmp_inc, LMMP_MAX, lmmp_mersenne_next_size_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_sub_n_(), lmmp_zero, M1, n , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 lmmp_hgcd_apply_mod_() , 以及 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_().
将 [src,sn] 折叠为模 B^rn-1 的表示:写入 [dst,rn)
| dst | 输出数组(长度为 rn 个limb) |
| src | 源数组(长度为 sn 个limb,sn 与 rn 任意大小关系) |
| sn | src 的长度 |
| rn | 模长(limb) |
引用了 lmmp_add_(), lmmp_copy, lmmp_hgcd_fold_mod_(), lmmp_inc , 以及 lmmp_zero.
被这些函数引用 lmmp_hgcd_apply_mod_() , 以及 lmmp_hgcd_fold_mod_().
|
static |
在 [ap,n] 与 [bp,n] 的 127 位顶端近似上运行小规模欧几里得,累积单 limb 矩阵 U
| pu00 | 输出矩阵元素 m00(仅返回 1 时写入) |
| pu01 | 输出矩阵元素 m01(仅返回 1 时写入) |
| pu10 | 输出矩阵元素 m10(仅返回 1 时写入) |
| pu11 | 输出矩阵元素 m11(仅返回 1 时写入) |
| ap | 较大数指针(长度为 n 个limb,ap[n-1]>0) |
| bp | 较小数指针(长度为 n 个limb,允许高位为零:窗口按 a 的顶位对齐, b 的高位零只使 y 偏小,不破坏正确性) |
| n | ap,bp 的公共长度 |
引用了 _umul64to128_(), lmmp_debug_assert, lmmp_hgcd_lehmer2_(), lmmp_limb_bits_, n, t , 以及 vh.
被这些函数引用 lmmp_hgcd_lehmer2_() , 以及 lmmp_hgcd_step_().
| void lmmp_hgcd_matrix_free_ | ( | lmmp_hgcd_matrix_t * | M | ) |
释放 hgcd 变换矩阵的元素缓冲
| M | 变换矩阵 |
引用了 lmmp_hgcd_matrix_t::alloc, lmmp_free(), lmmp_hgcd_matrix_free_(), lmmp_param_assert, lmmp_hgcd_matrix_t::m , 以及 lmmp_hgcd_matrix_t::n.
被这些函数引用 lmmp_hgcd_matrix_free_() , 以及 TEST_CASE().
| void lmmp_hgcd_matrix_init_ | ( | lmmp_hgcd_matrix_t * | M, |
| mp_size_t | alloc ) |
初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲)
| M | 变换矩阵 |
| alloc | 每元素容量(limb)。若随后用于 n limb 数对的 hgcd,需 alloc >= n+2 |
引用了 ALLOC_TYPE, lmmp_hgcd_matrix_init_(), lmmp_hgcd_matrix_init_buf_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_hgcd_matrix_init_() , 以及 TEST_CASE().
|
inlinestatic |
将连续缓冲初始化为单位矩阵
| M | 变换矩阵(写入 M->m 指针、M->n、M->alloc,并置对角元为 1) |
| buf | 连续缓冲 |
| alloc | 每元素容量(limb) |
引用了 lmmp_hgcd_matrix_t::alloc, lmmp_debug_assert, lmmp_hgcd_matrix_init_buf_(), lmmp_hgcd_matrix_t::m , 以及 lmmp_hgcd_matrix_t::n.
被这些函数引用 lmmp_gcd_hgcd_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_init_() , 以及 lmmp_hgcd_matrix_init_buf_().
|
static |
M <- M*M1(经由库内 lmmp_mat22_mul_,按元素最大长度自动分派 basecase / Winograd-Strassen 路径)
| M | 左矩阵,输入读各元素 [0,M->n[i][j]),输出写各元素与长度字段 (新长度 <= max(M->n[i][k]) + max(M1->n[k][j]) + 1) |
| M1 | 右矩阵(只读,各元素 [0,M1->n[i][j]) 有效) |
| sc | 临时空间(8*(mx(M)+mx(M1))+16 个limb) |
引用了 lmmp_hgcd_matrix_t::alloc, lmmp_copy, lmmp_debug_assert, lmmp_gcd_matrix_maxlen_(), lmmp_hgcd_matrix_mul_(), lmmp_hgcd_salloc_(), lmmp_mat22_mul_(), lmmp_hgcd_matrix_t::m, M1, lmmp_hgcd_matrix_t::n, tp , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 lmmp_hgcd_core_() , 以及 lmmp_hgcd_matrix_mul_().
|
static |
M <- M*U,U 为单 limb 元素的非负矩阵
| M | 变换矩阵:输入读各元素 [0,M->n[i][j]),输出写各元素与 M->n[i][j](新长度至多旧长度+1) |
| sc | 临时空间(max(M->n[i][j])+2 个limb) |
| detsign | det(M) 的符号,输入输出同源(乘 det(U)=[1|-1] 调整) |
| u00 | U 的元素 m00(非负且 < 2^62) |
| u01 | U 的元素 m01(非负且 < 2^62) |
| u10 | U 的元素 m10(非负且 < 2^62) |
| u11 | U 的元素 m11(非负且 < 2^62) |
引用了 _umul64to128_(), lmmp_hgcd_matrix_t::alloc, c0, c1, lmmp_add_1_(), lmmp_addmul_1_(), lmmp_copy, lmmp_debug_assert, lmmp_gcd_matrix_maxlen_(), lmmp_hgcd_matrix_mul_u_(), lmmp_hgcd_salloc_(), lmmp_mul_1_(), lmmp_zero, lmmp_hgcd_matrix_t::m, lmmp_hgcd_matrix_t::n, t , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 lmmp_hgcd_matrix_mul_u_() , 以及 lmmp_hgcd_step_().
|
static |
真除法步进的矩阵累积
| M | 变换矩阵:输入读各元素 [0,M->n[i][j]),输出写更新列各元素 与长度(另一列仅按 col 语义搬移/保持) |
| sc | 临时空间(qn+max(M->n[i][j])+1 个limb) |
| detsign | det(M) 的符号,输入输出同源(col=0 时乘 det(F)=-1 变号) |
| q | 商数组(长度为 qn 个limb,q[qn-1]>0) |
| qn | 商的 limb 长度,qn>0 |
| col | 被更新列编号,亦即右乘矩阵的选择。按本模块约定 (a;b) = M*(a';b'), 数对做一步带商 q 的欧几里得步进 a = q*b + r 后,需右乘 X 使 (a;b) = (M*X)*(新数对),两种步进方向对应: col=0(无翻转,新数对 (b; r),r 作新的较小分量): X = F(q) = / q 1 \ ,det = -1; \ 1 0 / 列语义:新 col0 = q*col0 + col1,新 col1 = 旧 col0。 验证:F(q)*(b;r) = (q*b+r; b) = (a; b) col=1(翻转,新数对 (r; b),r 作新的较大分量;部分除法中 商被压低使 r' >= b 时发生): X = E(q) = / 1 q \ ,det = +1; \ 0 1 / 列语义:新 col1 = q*col0 + col1,col0 不变。 验证:E(q)*(r;b) = (r+q*b; b) = (a; b) (E(q) = F(q)*P,P 为列交换,即数对翻转在矩阵侧的簿记) |
引用了 lmmp_add_(), lmmp_copy, lmmp_gcd_matrix_maxlen_(), lmmp_gcd_mul_(), lmmp_hgcd_matrix_update_q_(), lmmp_hgcd_salloc_(), lmmp_zero, lmmp_hgcd_matrix_t::m, lmmp_hgcd_matrix_t::n, t , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 lmmp_hgcd_matrix_update_q_() , 以及 lmmp_hgcd_step_().
Copyright (C) 2026 HJimmyK (Jericho Knox)
计算 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 | 输入长度 |
Copyright (C) 2026 HJimmyK (Jericho Knox)
| n | 输入长度 |
引用了 HGCD_RECURSE_THRESHOLD, lmmp_hgcd_scratch_size_() , 以及 n.
被这些函数引用 lmmp_gcd_hgcd_(), lmmp_gcdext_hgcd_(), lmmp_hgcd_() , 以及 lmmp_hgcd_scratch_size_().
|
static |
单步步进:用近似矩阵 U 或一次(可能部分的)除法归约数对
| M | 变换矩阵(累积):输入读各元素长度为 M->n 个limb,输出零填充至新公共长度 |
| ap | 较大分量输入兼输出数组:输入读 [ap,n)(ap[n-1]>0),输出写 [ap,nn) 并零填充至新公共长度 nn(规范序:归约后较大者写入 ap) |
| bp | 较小分量输入兼输出数组:输入读 [bp,n)(允许高位为零,[bp,n]>0), 输出写 [bp,nn) 并零填充至 nn |
| n | ap,bp 的公共长度 |
| fl | 步进下限:结果较小分量 >= B^(fl-1)。保证矩阵元素 <= B^(n-fl+1) < B^(fl-1), 使上层递归的矩阵修补非负性成立 |
| sc | 临时空间(峰值约 6n+6 个limb:除法回退路径的商/余/被除副本 与矩阵更新的嵌套需求) |
| detsign | det(M) 的符号,输入输出同源(本函数依更新矩阵调整其值) |
引用了 _umul64to128_(), an, bn, lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_div_(), lmmp_gcd_norm_(), lmmp_hgcd_lehmer2_(), lmmp_hgcd_matrix_mul_u_(), lmmp_hgcd_matrix_update_q_(), lmmp_hgcd_salloc_(), lmmp_hgcd_step_(), lmmp_inc, lmmp_mul_1_(), lmmp_submul_1_(), lmmp_zero, n, t , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 lmmp_hgcd_core_() , 以及 lmmp_hgcd_step_().