LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
binvert.c 文件参考
#include "mparam.h"
#include "impl/tmp_alloc.h"
#include "impl/inlines.h"
#include "impl/mul_cache.h"
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
binvert.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define a_binvert   (tp)
#define k   (tp + 1 * na)
#define prod   (tp)
#define prod   (tp)
#define scratch   (tp + 2 * na)
#define scratch   (tp + n + halfn)
#define scratch   (tp + 3 * halfn)
#define xhi   (dst + halfn)
#define xhi   (dst + halfn)
#define xlo   (dst)
#define xlo   (dst)

函数

static void binvert_mulhi_ (mp_ptr dst, mp_srcptr xp, mp_srcptr ap, mp_size_t n, mp_ptr tp)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_binvert_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_size_t n)
void lmmp_binvert_n_dc_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t n, mp_ptr restrict tp)
void lmmp_binvert_unbalance_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_size_t n, mp_ptr restrict tp)
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)

宏定义说明

◆ a_binvert

#define a_binvert   (tp)

◆ k

#define k   (tp + 1 * na)

被这些函数引用 __lmmp_limb_bits_(), __lmmp_limb_popcnt_(), _bpow_preinv_(), count_2facodd_factors(), dec_pow_extend_(), exp2_fixed_128(), exp2_fixed_64(), fib_pair(), k2t_limbs(), limb_bits_of(), ll_small_2_powmod(), lmmp_2factorial_(), lmmp_2factorial_size_(), lmmp_add_n_sub_n_(), lmmp_binvert_2_(), lmmp_binvert_3_(), lmmp_binvert_4_(), lmmp_binvert_unbalance_(), lmmp_binvert_unbalance_1_(), lmmp_binvert_unbalance_2_(), lmmp_cbrt_(), lmmp_cbrt_knorm_(), lmmp_cmp_(), lmmp_div_3_2_(), lmmp_fft_(), lmmp_fft_4_(), lmmp_fft_b1_(), lmmp_fft_best_k_(), lmmp_fft_next_size_(), lmmp_gcd_11_(), lmmp_huff_tree_build_(), lmmp_ifft_(), lmmp_ifft_4_(), lmmp_ifft_b1_(), lmmp_ifft_bfy_fused_(), lmmp_is_prothprime_(), lmmp_limb_bits_(), lmmp_limb_popcnt_(), lmmp_mod_4chunk_1_(), lmmp_mod_8chunk_1_(), lmmp_mod_preinv_1_(), lmmp_mul_fermat_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_fft_(), lmmp_odd_2factorial_uint_(), lmmp_odd_2factorial_ushort_(), lmmp_odd_nPr_product_(), lmmp_odd_nPr_product_(), lmmp_odd_nPr_ulong_(), lmmp_powmod_(), lmmp_powmod_(), lmmp_powmod_win_size_(), lmmp_prime_int_table_init_(), lmmp_sqr_fermat_(), lmmp_sqr_fermat_recurse_(), lmmp_sqr_mersenne_fft_(), lmmp_strong_rng_extern_(), lmmp_strong_rng_init_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2_(), lmmp_toom_eval_pm2exp_(), lmmp_zero_q_(), log2_fixed_128(), lshl_u128(), lshr_u128(), mont2_powmod_2_(), mont63_reduce(), mont63_reduce(), mont63_reduce(), mont64_reduce(), mont64_reduce(), mrs_fermat_usable_(), pcg64_le_seq_next(), pool_proth(), pow_u64_ovf(), powmod1_redc_(), powmod2b_u32(), proth_cert_g(), proth_limbs(), rotl(), run_gcdext_pair(), sp_shape_limbs(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), trialdiv_init_chunk_() , 以及 win_size().

◆ prod [1/2]

#define prod   (tp)

◆ prod [2/2]

◆ scratch [1/3]

#define scratch   (tp + 2 * na)

◆ scratch [2/3]

#define scratch   (tp + n + halfn)

◆ scratch [3/3]

#define scratch   (tp + 3 * halfn)

◆ xhi [1/2]

#define xhi   (dst + halfn)

◆ xhi [2/2]

#define xhi   (dst + halfn)

被这些函数引用 lmmp_binvert_n_dc_().

◆ xlo [1/2]

#define xlo   (dst)

◆ xlo [2/2]

#define xlo   (dst)

被这些函数引用 lmmp_binvert_n_dc_().

函数说明

◆ binvert_mulhi_()

void binvert_mulhi_ ( mp_ptr dst,
mp_srcptr xp,
mp_srcptr ap,
mp_size_t n,
mp_ptr tp )
inlinestatic

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

计算 [dst,n] = [xp,n]*[ap,n] div B^n

参数
dst结果指针
tp需要 max(2*n, mersenne_next_size(2*n)) 个 limb
警告
[xp,n] * [ap,n] mod B^n == 1

在文件 binvert.c 第 36 行定义.

36 {
38 lmmp_mul_n_(tp, xp, ap, n);
39 lmmp_copy(dst, tp + n, n);
40 } else {
42 lmmp_debug_assert(m >= 2 * n);
43 lmmp_mul_mersenne_(tp, m, xp, n, ap, n);
44 lmmp_copy(dst, tp + n, n);
45 }
46}
#define lmmp_mul_n_
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
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_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
#define xp
#define tp
#define n
#define MULHI_MERSENNE_THRESHOLD

引用了 binvert_mulhi_(), lmmp_copy, lmmp_debug_assert, lmmp_mersenne_next_size_(), lmmp_mul_mersenne_(), lmmp_mul_n_, MULHI_MERSENNE_THRESHOLD, n, tp , 以及 xp.

被这些函数引用 binvert_mulhi_() , 以及 lmmp_binvert_unbalance_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_binvert_()

void lmmp_binvert_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t na,
mp_size_t n )

在文件 binvert.c 第 236 行定义.

236 {
237 lmmp_param_assert(dst != NULL && numa != NULL);
238 lmmp_param_assert(na > 0 && n >= na);
239 lmmp_param_assert(numa[0] % 2 == 1);
240 TEMP_DECL;
241 if (n == na) {
242 mp_ptr restrict tp = TALLOC_TYPE(5 * (n + 1) / 2, mp_limb_t);
243 lmmp_binvert_n_dc_(dst, numa, na, tp);
244 } else if (na == 1) {
245 lmmp_binvert_unbalance_1_(dst, numa[0], n);
246 } else if (na == 2) {
247 lmmp_binvert_unbalance_2_(dst, numa, n);
248 } else if (4 * n >= 5 * na) {
249 // n/na >= 5/4 这是一个比较简单的调优结果
250 mp_ptr restrict tp = TALLOC_TYPE((9 * n + 5) / 2, mp_limb_t);
251 lmmp_binvert_unbalance_(dst, numa, na, n, tp);
252 } else {
254 mp_ptr restrict tp = TALLOC_TYPE((5 * n + 5) / 2, mp_limb_t);
255 lmmp_copy(ap, numa, na);
256 lmmp_zero(ap + na, n - na);
257 lmmp_binvert_n_dc_(dst, ap, n, tp);
258 }
259 TEMP_FREE;
260}
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
void lmmp_binvert_unbalance_1_(mp_ptr dst, mp_limb_t a, mp_size_t n)
计算 a 在 B^n 下的逆元
void lmmp_binvert_n_dc_(mp_ptr dst, mp_srcptr numa, mp_size_t n, mp_ptr tp)
计算 [numa,n] 在 B^n 下的逆元
void lmmp_binvert_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n, mp_ptr tp)
计算 [numa,na] 在 B^n 下的逆元
void lmmp_binvert_unbalance_2_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
计算 [numa,2] 在 B^n 下的逆元
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 lmmp_binvert_(), lmmp_binvert_n_dc_(), lmmp_binvert_unbalance_(), lmmp_binvert_unbalance_1_(), lmmp_binvert_unbalance_2_(), lmmp_copy, lmmp_param_assert, lmmp_zero, n, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

◆ lmmp_binvert_n_dc_()

void lmmp_binvert_n_dc_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t n,
mp_ptr restrict tp )

在文件 binvert.c 第 97 行定义.

97 {
98 lmmp_param_assert(dst != NULL && tp != NULL);
99 lmmp_param_assert(numa != NULL && n > 0);
100 lmmp_param_assert(numa[0] % 2 == 1);
101 if (n == 1) {
102 dst[0] = lmmp_binvert_ulong_(numa[0]);
103 } else if (n == 2) {
104 lmmp_binvert_2_(dst, numa);
105 } else if (n == 3) {
106 lmmp_binvert_3_(dst, numa);
107 } else if (n == 4) {
108 lmmp_binvert_4_(dst, numa);
109 } else if (n % 2 == 0) {
110 mp_size_t halfn = n / 2;
111
112#define xlo (dst) // [dst, halfn]
113#define xhi (dst + halfn) // [dst+halfn, halfn]
114#define prod (tp) // [tp, 3*halfn]
115#define scratch (tp + 3 * halfn) // [tp+3*halfn, 2*halfn]
116// ________________________________________________________________
117// tp : |_________________________5*(n+1)/2____________________________|
118// | prod (3*halfn) | scratch (2*halfn) |
119
120 lmmp_binvert_n_dc_(xlo, numa, halfn, tp);
121 lmmp_mul_(prod, numa, n, xlo, halfn);
122 lmmp_mullo_n_(xhi, xlo, prod + halfn, halfn, scratch);
123 lmmp_not_(xhi, xhi, halfn);
124 lmmp_inc(xhi);
125#undef xlo
126#undef xhi
127#undef prod
128#undef scratch
129 } else {
130 mp_size_t halfn = n / 2 + 1;
131 mp_size_t ahin = n - halfn;
132
133#define xlo (dst) // [dst, halfn]
134#define xhi (dst + halfn) // [dst+halfn, ahin]
135#define prod (tp) // [tp, n+halfn]
136#define scratch (tp + n + halfn) // [tp+n+halfn, 2*ahin]
137// ________________________________________________________________
138// tp : |_________________________5*(n+1)/2____________________________|
139// | prod (n+halfn) | scratch (2*ahin) | remaining |
140
141 lmmp_binvert_n_dc_(xlo, numa, halfn, tp);
142 lmmp_mul_(prod, numa, n, xlo, halfn);
143 lmmp_mullo_n_(xhi, xlo, prod + halfn, ahin, scratch);
144 lmmp_not_(xhi, xhi, ahin);
145 lmmp_inc(xhi);
146#undef xlo
147#undef xhi
148#undef prod
149#undef scratch
150 }
151}
#define xhi
#define prod
#define xlo
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)
#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]
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
#define scratch
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
void lmmp_binvert_3_(mp_ptr dst, mp_srcptr numa)
计算 [numa,3] 在 B^3 下的逆元
void lmmp_binvert_4_(mp_ptr dst, mp_srcptr numa)
计算 [numa,4] 在 B^4 下的逆元

引用了 lmmp_binvert_2_(), lmmp_binvert_3_(), lmmp_binvert_4_(), lmmp_binvert_n_dc_(), lmmp_binvert_ulong_(), lmmp_inc, lmmp_mul_(), lmmp_mullo_n_(), lmmp_not_(), lmmp_param_assert, n, prod, restrict, scratch, tp, xhi , 以及 xlo.

函数调用图:

◆ lmmp_binvert_unbalance_()

void lmmp_binvert_unbalance_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t na,
mp_size_t n,
mp_ptr restrict tp )

在文件 binvert.c 第 153 行定义.

153 {
154 lmmp_param_assert(dst != NULL && numa != NULL && tp != NULL);
155 lmmp_param_assert(numa[0] % 2 == 1);
156 lmmp_param_assert(n > na && na > 0);
157
158#define a_binvert (tp) // [tp, na]
159#define k (tp + 1 * na) // [tp+na, na]
160#define scratch (tp + 2 * na) // [tp+2*na, 5*(na+1)/2]
161
163 lmmp_copy(dst, a_binvert, na);
164 binvert_mulhi_(k, a_binvert, numa, na, scratch);
165
166 // a_binvert 低位不可能为0,故加一不会进位
169 a_binvert[0] += 1;
170
171 fft_mullo_cache mctx;
172 int mcflag = 0;
173 fft_gr_cache hctx;
174 int hcflag = 0;
175 mp_size_t i = na;
176 for (; i < n - na; i += na) {
177 if (na >= MULLO_DC_THRESHOLD) {
178 if (mcflag == 0) {
179 lmmp_mullo_fft_cache_init_(dst + i, k, a_binvert, na, scratch, &mctx);
180 mcflag = 1;
181 } else {
182 lmmp_mullo_fft_cache_(dst + i, k, scratch, &mctx);
183 }
184 } else {
185 lmmp_mullo_dc_(dst + i, k, a_binvert, scratch, na);
186 }
187 /*
188 更新 k:k' = (k + a*p) div B^na。由 p 的构造有 p*a ≡ -k (mod B^na),
189 即 k + a*p 恰为 B^na 的倍数,商即为 k'。
190 R = a*p mod B^m-1,V = R + k mod B^m-1,
191 则 V ≡ k'*B^na (mod B^m-1);将 k' 拆为低 fn=m-na 位与高位,
192 k'*B^na mod (B^m-1) 恰为两者在 m 位中的错位拼接,旋转载出即得 k'
193 */
195 lmmp_mul_n_(scratch, dst + i, numa, na);
196 // now [scratch,2*na] = a * p
197 if (lmmp_add_n_(scratch, scratch, k, na)) {
198 lmmp_inc(scratch + na);
199 }
200 lmmp_copy(k, scratch + na, na);
201 } else {
203 ? lmmp_fft_next_size_((na * 2 + 1) >> 1) /* 缓存档:仅 fft 尺寸可用 */
204 : lmmp_mersenne_next_size_((na * 2 + 1) >> 1); /* 分发档:细粒度低 padding */
205 mp_size_t fn = m - na;
206 mp_size_t sn = na - fn;
207 mp_limb_t cy;
209 /* 中档:分发入口不缓存(小尺寸 dc 主导) */
210 lmmp_mul_mersenne_(scratch, m, dst + i, na, numa, na);
211 } else if (hcflag == 0) {
212 lmmp_mul_mersenne_cache_init_(scratch, m, dst + i, na, numa, na, &hctx);
213 hcflag = 1;
214 } else {
215 lmmp_mul_mersenne_cache_(scratch, dst + i, &hctx);
216 }
217 // V = (R + k) mod B^m-1
218 cy = lmmp_add_(scratch, scratch, m, k, na);
219 if (cy)
221 lmmp_copy(k, scratch + na, fn);
222 lmmp_copy(k + fn, scratch, sn);
223 }
224 }
225
226 lmmp_mullo_n_(dst + i, a_binvert, k, n - i, scratch);
227 if (mcflag == 1)
229 if (hcflag == 1)
231#undef a_binvert
232#undef k
233#undef scratch
234}
#define k
static void binvert_mulhi_(mp_ptr dst, mp_srcptr xp, mp_srcptr ap, mp_size_t n, mp_ptr tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define a_binvert
#define MULLO_DC_THRESHOLD
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_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
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
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 第二个操作数将被缓存
定义 mullo.c:86
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 BINVERT_UNBALANCE_MODM_THRESHOLD
#define BINVERT_UNBALANCE_MODM_CACHE_THRESHOLD

引用了 a_binvert, binvert_mulhi_(), BINVERT_UNBALANCE_MODM_CACHE_THRESHOLD, BINVERT_UNBALANCE_MODM_THRESHOLD, k, lmmp_add_(), lmmp_add_n_(), lmmp_binvert_n_dc_(), lmmp_binvert_unbalance_(), lmmp_copy, lmmp_debug_assert, lmmp_fft_gr_cache_free_(), lmmp_fft_next_size_(), lmmp_inc, lmmp_mersenne_next_size_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_n_, lmmp_mullo_cache_free_(), lmmp_mullo_dc_(), lmmp_mullo_fft_cache_(), lmmp_mullo_fft_cache_init_(), lmmp_mullo_n_(), lmmp_not_(), lmmp_param_assert, MULLO_DC_THRESHOLD, n, restrict, scratch , 以及 tp.

函数调用图:

◆ lmmp_mullo_n_()

void lmmp_mullo_n_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_srcptr restrict numb,
mp_size_t n,
mp_ptr restrict tp )
inlinestatic

在文件 binvert.c 第 48 行定义.

54 {
55 if (n < MULLO_DC_THRESHOLD) {
56 lmmp_mullo_dc_(dst, numa, numb, tp, n);
57 } else {
58 lmmp_mullo_fft_(dst, numa, numb, n, tp);
59 }
60}
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
定义 mullo.c:68
#define numb

引用了 lmmp_mullo_dc_(), lmmp_mullo_fft_(), lmmp_mullo_n_(), MULLO_DC_THRESHOLD, n, numb, restrict , 以及 tp.

被这些函数引用 lmmp_binvert_n_dc_(), lmmp_binvert_unbalance_(), lmmp_divexact_divide_(), lmmp_divexact_mu_run_(), lmmp_divexact_unbalance_(), lmmp_mullo_n_(), lmmp_mullo_n_(), lmmp_mullo_n_() , 以及 lmmp_powlo_().

函数调用图:
这是这个函数的调用关系图: