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

浏览该文件的源代码.

宏定义

#define LMMP_DIVX_PUT(k, qv)
#define prod   (tp + dn)
#define rp   (tp)

函数

void lmmp_divexact_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr restrict dp, mp_size_t dn)
void lmmp_divexact_1_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_limb_t d, mp_limb_t dinv)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_divexact_2_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr restrict dp, mp_srcptr restrict dinv)
void lmmp_divexact_basecase_ (mp_ptr dst, mp_ptr np, mp_size_t nn, mp_srcptr restrict dp, mp_size_t dn)
void lmmp_divexact_divide_ (mp_ptr restrict dst, mp_srcptr restrict np, mp_size_t nn, mp_srcptr restrict dp, mp_size_t dn)
static void lmmp_divexact_mu_run_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr restrict dp, mp_size_t dn, mp_srcptr restrict dinv, mp_size_t in, mp_ptr restrict tp)
void lmmp_divexact_unbalance_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr restrict dp, mp_size_t dn, mp_ptr restrict dinv)
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)

宏定义说明

◆ LMMP_DIVX_PUT

#define LMMP_DIVX_PUT ( k,
qv )
值:
do { \
mp_limb_t _q_ = (qv); \
dst[k] = ~_q_ + negc; \
negc &= (mp_limb_t)(_q_ == 0); \
} while (0)
#define k
uint64_t mp_limb_t
定义 lmmp.h:92

被这些函数引用 lmmp_divexact_basecase_().

◆ prod

#define prod   (tp + dn)

◆ rp

函数说明

◆ lmmp_divexact_()

void lmmp_divexact_ ( mp_ptr dst,
mp_srcptr np,
mp_size_t nn,
mp_srcptr restrict dp,
mp_size_t dn )

在文件 divexact.c 第 385 行定义.

385 {
386 lmmp_param_assert(dst != NULL && np != NULL && dp != NULL);
387 lmmp_param_assert(dn > 0);
388 lmmp_param_assert(nn >= dn);
389 lmmp_param_assert((dp[0] & 1) != 0);
390
391 if (dn == 1) {
392 mp_limb_t dinv = lmmp_binvert_ulong_(dp[0]);
393 lmmp_divexact_1_(dst, np, nn, dp[0], dinv);
394 } else if (dn == 2) {
395 mp_limb_t dinv[2];
396 lmmp_binvert_2_(dinv, dp);
397 lmmp_divexact_2_(dst, np, nn, dp, dinv);
398 } else {
399 mp_size_t qn = nn - dn + 1;
401 TEMP_DECL;
403 lmmp_copy(tp, np, nn);
404 lmmp_divexact_basecase_(dst, tp, nn, dp, dn);
405 TEMP_FREE;
406 } else if (qn < dn) {
407 TEMP_DECL;
409 if (dst == np) {
410 tp = TALLOC_TYPE(nn, mp_limb_t);
411 lmmp_copy(tp, np, nn);
412 np = tp;
413 }
414 lmmp_divexact_divide_(dst, np, nn, dp, dn);
415 TEMP_FREE;
416 } else {
417 lmmp_divexact_unbalance_(dst, np, nn, dp, dn, NULL);
418 }
419 }
420}
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define tp
#define DIVEXACT_NN_THRESHOLD
#define DIVEXACT_BASECASE_THRESHOLD
void lmmp_divexact_unbalance_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_ptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
void lmmp_divexact_basecase_(mp_ptr dst, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
void lmmp_divexact_1_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_limb_t d, mp_limb_t dinv)
精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
void lmmp_divexact_2_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_srcptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0)
void lmmp_divexact_divide_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 DIVEXACT_BASECASE_THRESHOLD, DIVEXACT_NN_THRESHOLD, lmmp_binvert_2_(), lmmp_binvert_ulong_(), lmmp_copy, lmmp_divexact_(), lmmp_divexact_1_(), lmmp_divexact_2_(), lmmp_divexact_basecase_(), lmmp_divexact_divide_(), lmmp_divexact_unbalance_(), lmmp_param_assert, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

◆ lmmp_divexact_1_()

void lmmp_divexact_1_ ( mp_ptr dst,
mp_srcptr np,
mp_size_t nn,
mp_limb_t d,
mp_limb_t dinv )

Copyright (C) 2026 HJimmyK (Jericho Knox)

精确除法([dst,nn]=[np,nn]/d,且余数必须为0)

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

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst结果指针(长度为 nn 个limb)
np被除数指针(长度为 nn 个limb)
nn被除数的 limb 长度
d除数
dinv除数的逆元(d*dinv==1 mod 2^64)
警告
d%2==1, d*dinv==1 mod 2^64, nn>0, dst!=NULL, np!=NULL, eqsep(dst,np)

在文件 divexact.c 第 32 行定义.

32 {
33 lmmp_param_assert(d % 2 == 1);
34 lmmp_param_assert(dinv * d == 1);
35 lmmp_param_assert(nn > 0);
36 lmmp_debug_assert(dst != NULL && np != NULL);
37 mp_limb_t c = 0;
38 mp_limb_t l, s, lo, hi, q;
39 mp_size_t i;
40 for (i = 0; i < nn - 1; i++) {
41 s = np[i];
42 l = s - c;
43 c = l > s;
44 q = l * dinv;
45 dst[i] = q;
46 _umul64to128_(q, d, &lo, &hi);
47 c += hi;
48 }
49 s = np[i];
50 l = s - c;
51 c = l > s;
52 q = l * dinv;
53 dst[i] = q;
54 lmmp_debug_assert(c == 0);
55}
#define lmmp_debug_assert(x)
定义 lmmp.h:498
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
#define s
#define lo

引用了 _umul64to128_(), lmmp_debug_assert, lmmp_divexact_1_(), lmmp_param_assert, lo , 以及 s.

被这些函数引用 lmmp_binvert_(), lmmp_divexact_(), lmmp_divexact_1_(), lmmp_divexact_basecase_() , 以及 TEST_CASE().

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

◆ lmmp_divexact_2_()

void lmmp_divexact_2_ ( mp_ptr dst,
mp_srcptr np,
mp_size_t nn,
mp_srcptr restrict dp,
mp_srcptr restrict dinv )

在文件 divexact.c 第 57 行定义.

57 {
58 lmmp_param_assert(nn > 1);
59 lmmp_param_assert(dst != NULL && np != NULL);
60 lmmp_param_assert(dp != NULL && dinv != NULL);
61 lmmp_param_assert(dp[0] % 2 == 1);
62 u128 c = 0;
63 u128 l, s, q;
64 mp_limb_t t[4];
65 mp_size_t i;
66 mp_limb_t d0 = dp[0], d1 = dp[1];
67 mp_limb_t ddinv0 = dinv[0], ddinv1 = dinv[1];
68
69 if (nn % 2 == 0) {
70 for (i = 0; i < nn - 2; i += 2) {
71 s = _u128load(np + i);
72 l = s - c;
73 c = (u128)(s < l); // 借位(原 c 非 0 时成立)
74 q = _umul128to128_(_u128high(l), _u128low(l), ddinv1, ddinv0);
75 dst[i] = _u128low(q);
76 dst[i + 1] = _u128high(q);
77 _umul128to256_(_u128high(q), _u128low(q), d1, d0, t);
78 c += _u128load(t + 2);
79 }
80 s = _u128load(np + i);
81 l = s - c;
82 c = (u128)(s < l);
83 q = _umul128to128_(_u128high(l), _u128low(l), ddinv1, ddinv0);
84 dst[i] = _u128low(q);
85 // 商最高 limb 为 0 时 c 可能为 1;函数结果仍然正确。
86 } else {
87 i = 0;
88 if (nn >= 5) {
89 for (; i < nn - 4; i += 2) {
90 s = _u128load(np + i);
91 l = s - c;
92 c = (u128)(s < l);
93 q = _umul128to128_(_u128high(l), _u128low(l), ddinv1, ddinv0);
94 dst[i] = _u128low(q);
95 dst[i + 1] = _u128high(q);
96 _umul128to256_(_u128high(q), _u128low(q), d1, d0, t);
97 c += _u128load(t + 2);
98 }
99 }
100 s = _u128load(np + i);
101 l = s - c;
102 c = (u128)(s < l);
103 q = _umul128to128_(_u128high(l), _u128low(l), ddinv1, ddinv0);
104 dst[i] = _u128low(q);
105 dst[i + 1] = _u128high(q);
106 // 商最高 limb 为 0 时 c 可能为 1;函数结果仍然正确。
107 }
108}
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
static __uint128_t _umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)
#define t

引用了 _umul128to128_(), _umul128to256_(), lmmp_divexact_2_(), lmmp_param_assert, restrict, s , 以及 t.

函数调用图:

◆ lmmp_divexact_basecase_()

void lmmp_divexact_basecase_ ( mp_ptr dst,
mp_ptr np,
mp_size_t nn,
mp_srcptr restrict dp,
mp_size_t dn )

在文件 divexact.c 第 268 行定义.

268 {
269 lmmp_param_assert(dst != NULL && np != NULL && dp != NULL);
270 lmmp_param_assert(dn > 0);
271 lmmp_param_assert(nn >= dn);
272 lmmp_param_assert((dp[0] & 1) != 0);
273
274 const mp_size_t qn = nn - dn + 1;
275
276 if (dn == 1) {
277 lmmp_divexact_1_(dst, np, nn, dp[0], lmmp_binvert_ulong_(dp[0]));
278 if (dst != np) {
279 lmmp_zero(np, nn);
280 }
281 return;
282 }
283
284 /* 有效宽度:商 Q = N*D^(-1) mod B^qn 只需 d 的低 min(dn, qn) limb */
285 const mp_size_t D = dn < qn ? dn : qn;
286
287 const mp_limb_t ninv1 = 0 - lmmp_binvert_ulong_(dp[0]);
288 const mp_limb_t e = _umul64to64hi_(dp[0], ninv1) + 1;
289 const mp_limb_t ninv2 = ninv1 * e + dp[1] * ninv1 * ninv1;
290 lmmp_debug_assert(dp[0] * ninv1 == ~(mp_limb_t)0);
291
292 /* 商流式取负:Q_true = -Q mod B^qn = ~Q + 1,negc 为借位链 */
293 mp_limb_t negc = 1;
294#define LMMP_DIVX_PUT(k, qv) \
295 do { \
296 mp_limb_t _q_ = (qv); \
297 dst[k] = ~_q_ + negc; \
298 negc &= (mp_limb_t)(_q_ == 0); \
299 } while (0)
300
301 mp_ptr up = np;
302 mp_size_t i = 0;
303 mp_limb_t cy = 0;
304
305 for (; qn - i >= D + 2; i += 2, up += 2) {
306 mp_limb_t q[2], qh;
307 _umul64to128_(up[0], ninv1, &q[0], &qh);
308 q[1] = qh + up[0] * ninv2 + up[1] * ninv1;
309 const mp_limb_t sv = up[D];
310 const mp_limb_t chi = lmmp_addmul_2_(up, dp, D, q);
311 mp_limb_t s = sv + up[D];
312 mp_limb_t c = s < sv;
313 s += cy;
314 c += s < cy;
315 up[D] = s;
316 mp_limb_t t = up[D + 1] + chi;
317 cy = t < chi;
318 t += c;
319 cy += t < c;
320 up[D + 1] = t;
321 lmmp_debug_assert(up[0] == 0 && up[1] == 0);
322 LMMP_DIVX_PUT(i, q[0]);
323 LMMP_DIVX_PUT(i + 1, q[1]);
324 }
325
326 if (qn - i == D + 1) {
327 const mp_limb_t q = up[0] * ninv1;
328 const mp_limb_t hi = lmmp_addmul_1_(up, dp, D, q);
329 up[D] += hi + cy;
330 lmmp_debug_assert(up[0] == 0);
331 LMMP_DIVX_PUT(i, q);
332 i++;
333 up++;
334 }
335
336 for (mp_size_t w = qn - i; w >= 2; w -= 2, i += 2, up += 2) {
337 mp_limb_t q[2], qh;
338 _umul64to128_(up[0], ninv1, &q[0], &qh);
339 q[1] = qh + up[0] * ninv2 + up[1] * ninv1;
340 lmmp_addmul_2_(up, dp, w, q);
341 lmmp_debug_assert(up[0] == 0 && up[1] == 0);
342 LMMP_DIVX_PUT(i, q[0]);
343 LMMP_DIVX_PUT(i + 1, q[1]);
344 }
345 if (i < qn) {
346 const mp_limb_t q = up[0] * ninv1;
347 up[0] = 0;
348 LMMP_DIVX_PUT(i, q);
349 }
350#undef LMMP_DIVX_PUT
351
352 lmmp_zero(np + qn, nn - qn);
353}
#define LMMP_DIVX_PUT(k, qv)
#define D
#define lmmp_zero(dst, n)
定义 lmmp.h:476
mp_limb_t lmmp_addmul_2_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_srcptr bp)
乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]
定义 mul_1.c:99
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
定义 mul_1.c:76
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)

引用了 _umul64to128_(), _umul64to64hi_(), D, lmmp_addmul_1_(), lmmp_addmul_2_(), lmmp_binvert_ulong_(), lmmp_debug_assert, lmmp_divexact_1_(), lmmp_divexact_basecase_(), LMMP_DIVX_PUT, lmmp_param_assert, lmmp_zero, restrict, s , 以及 t.

函数调用图:

◆ lmmp_divexact_divide_()

void lmmp_divexact_divide_ ( mp_ptr restrict dst,
mp_srcptr restrict np,
mp_size_t nn,
mp_srcptr restrict dp,
mp_size_t dn )

在文件 divexact.c 第 355 行定义.

355 {
356 lmmp_param_assert(dst != NULL && np != NULL && dp != NULL);
357 lmmp_param_assert(dn > 0);
358 lmmp_param_assert(nn >= dn);
359 lmmp_param_assert((dp[0] & 1) != 0);
360
361 mp_size_t qn = nn - dn + 1;
362 lmmp_param_assert(qn <= dn);
363 mp_size_t rn = qn - qn / 2;
364 qn = qn / 2;
365
366 TEMP_DECL;
369 lmmp_binvert_n_dc_(dinv, dp, rn, tp);
370 lmmp_mullo_n_(dst, np, dinv, rn, tp);
371 if (qn == 0) {
372 TEMP_FREE;
373 return;
374 }
375
376 lmmp_debug_assert(3 * rn >= qn + rn);
377 lmmp_mul_(tp, dp, qn + rn, dst, rn);
378
379 // 即使存在错位,高位的np也一定可以将其约减去,因此无需进行任何处理
380 lmmp_sub_n_(tp, np + rn, tp + rn, qn);
381 lmmp_mullo_n_(dst + rn, tp, dinv, qn, tp + rn);
382 TEMP_FREE;
383}
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)
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]
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]
定义 sub_n.c:84
void lmmp_binvert_n_dc_(mp_ptr dst, mp_srcptr numa, mp_size_t n, mp_ptr tp)
计算 [numa,n] 在 B^n 下的逆元

引用了 lmmp_binvert_n_dc_(), lmmp_debug_assert, lmmp_divexact_divide_(), lmmp_mul_(), lmmp_mullo_n_(), lmmp_param_assert, lmmp_sub_n_(), restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

◆ lmmp_divexact_mu_run_()

void lmmp_divexact_mu_run_ ( mp_ptr dst,
mp_srcptr np,
mp_size_t nn,
mp_srcptr restrict dp,
mp_size_t dn,
mp_srcptr restrict dinv,
mp_size_t in,
mp_ptr restrict tp )
static

在文件 divexact.c 第 124 行定义.

133 {
134 mp_size_t qn = nn - dn + 1;
135 mp_size_t pn = dn + in;
136
137 int ms_mode = dn >= DIVEXACT_MERSENNE_CACHE_THRESHOLD ? 2 : (dn >= DIVEXACT_MERSENNE_THRESHOLD ? 1 : 0);
138 mp_size_t m = ms_mode == 2 ? lmmp_fft_next_size_(pn) : (ms_mode == 1 ? lmmp_mersenne_next_size_(pn) : 0);
139 int use_lcache = in >= MULLO_DC_THRESHOLD;
140 fft_gr_cache mctx;
141 int mflag = 0;
142 fft_mullo_cache lctx;
143 int lflag = 0;
144
145#define rp (tp) // [tp, dn]
146#define prod (tp + dn) // [tp+dn, 3*dn+2*in]
147
148 mp_limb_t cy = 0;
149 mp_ptr qp = dst;
150
151 lmmp_copy(rp, np, dn);
152 np += dn;
153 if (use_lcache) {
154 lmmp_mullo_fft_cache_init_(qp, rp, dinv, in, prod, &lctx);
155 lflag = 1;
156 } else {
157 lmmp_mullo_n_(qp, rp, dinv, in, prod);
158 }
159 qn -= in;
160
161 while (qn > in) {
162 /* prod[0..pn) = dp × qp 块 */
163 if (ms_mode == 2) {
164 if (mflag == 0) {
165 lmmp_mul_mersenne_cache_init_(prod, m, qp, in, dp, dn, &mctx);
166 mflag = 1;
167 } else {
168 lmmp_mul_mersenne_cache_(prod, qp, &mctx);
169 }
170 } else if (ms_mode == 1) {
171 lmmp_mul_mersenne_(prod, m, qp, in, dp, dn);
172 } else {
173 lmmp_mul_(prod, dp, dn, qp, in);
174 }
175 qp += in;
176 if (dn != in) {
177 cy += lmmp_sub_n_(rp, rp + in, prod + in, dn - in);
178 if (cy == 2) {
179 lmmp_inc(prod + dn);
180 cy = 1;
181 }
182 }
183 cy = lmmp_sub_nc_(rp + dn - in, np, prod + dn, in, cy);
184 np += in;
185 if (use_lcache) {
186 lmmp_mullo_fft_cache_(qp, rp, prod, &lctx);
187 } else {
188 lmmp_mullo_n_(qp, rp, dinv, in, prod);
189 }
190 qn -= in;
191 }
192
193 if (ms_mode == 2) {
194 if (mflag == 0) {
195 lmmp_mul_mersenne_cache_init_(prod, m, qp, in, dp, dn, &mctx);
196 mflag = 1;
197 } else {
198 lmmp_mul_mersenne_cache_(prod, qp, &mctx);
199 }
200 } else if (ms_mode == 1) {
201 lmmp_mul_mersenne_(prod, m, qp, in, dp, dn);
202 } else {
203 lmmp_mul_(prod, dp, dn, qp, in);
204 }
205 qp += in;
206 if (dn != in) {
207 cy += lmmp_sub_n_(rp, rp + in, prod + in, dn - in);
208 if (cy == 2) {
209 lmmp_inc(prod + dn);
210 cy = 1;
211 }
212 }
213 lmmp_sub_nc_(rp + dn - in, np, prod + dn, qn - (dn - in), cy);
214 lmmp_mullo_n_(qp, rp, dinv, qn, prod);
215
216 if (mflag == 1)
218 if (lflag == 1)
220
221#undef rp
222#undef prod
223}
#define prod
#define rp
#define MULLO_DC_THRESHOLD
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
#define lmmp_inc(p)
加1宏(预期无进位)
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
mp_limb_t lmmp_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
定义 sub_n.c:67
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
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 DIVEXACT_MERSENNE_CACHE_THRESHOLD
#define DIVEXACT_MERSENNE_THRESHOLD

引用了 DIVEXACT_MERSENNE_CACHE_THRESHOLD, DIVEXACT_MERSENNE_THRESHOLD, lmmp_copy, lmmp_divexact_mu_run_(), lmmp_fft_gr_cache_free_(), lmmp_fft_next_size_(), lmmp_inc, lmmp_mersenne_next_size_(), lmmp_mul_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mullo_cache_free_(), lmmp_mullo_fft_cache_(), lmmp_mullo_fft_cache_init_(), lmmp_mullo_n_(), lmmp_sub_n_(), lmmp_sub_nc_(), MULLO_DC_THRESHOLD, prod, restrict, rp , 以及 tp.

被这些函数引用 lmmp_divexact_mu_run_() , 以及 lmmp_divexact_unbalance_().

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

◆ lmmp_divexact_unbalance_()

void lmmp_divexact_unbalance_ ( mp_ptr dst,
mp_srcptr np,
mp_size_t nn,
mp_srcptr restrict dp,
mp_size_t dn,
mp_ptr restrict dinv )

在文件 divexact.c 第 225 行定义.

232 {
233 lmmp_param_assert(dst != NULL && np != NULL && dp != NULL);
234 lmmp_param_assert(dn > 0);
235 lmmp_param_assert(nn >= dn);
236 lmmp_param_assert((dp[0] & 1) != 0);
237
238 TEMP_DECL;
239 mp_size_t qn = nn - dn + 1;
240
241 if (qn <= dn) {
243 mp_ptr restrict t2 = TALLOC_TYPE(3 * qn, mp_limb_t);
244 if (dinv == NULL) {
245 dinv = TALLOC_TYPE(qn, mp_limb_t);
246 lmmp_binvert_n_dc_(dinv, dp, qn, t2);
247 }
248 lmmp_copy(l, np, qn);
249 lmmp_mullo_n_(dst, l, dinv, qn, t2);
250 TEMP_FREE;
251 return;
252 }
253 mp_size_t b = (qn - 1) / dn + 1;
254 mp_size_t in = (qn - 1) / b + 1;
255 mp_size_t pn = dn + in;
256
257 mp_ptr restrict tp = TALLOC_TYPE(dn + 2 * pn, mp_limb_t);
258 if (dinv == NULL) {
259 dinv = TALLOC_TYPE(in, mp_limb_t);
260 lmmp_binvert_n_dc_(dinv, dp, in, tp);
261 }
262
263 lmmp_divexact_mu_run_(dst, np, nn, dp, dn, dinv, in, tp);
264
265 TEMP_FREE;
266}
static void lmmp_divexact_mu_run_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr restrict dp, mp_size_t dn, mp_srcptr restrict dinv, mp_size_t in, mp_ptr restrict tp)

引用了 lmmp_binvert_n_dc_(), lmmp_copy, lmmp_divexact_mu_run_(), lmmp_divexact_unbalance_(), lmmp_mullo_n_(), lmmp_param_assert, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 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

在文件 divexact.c 第 110 行定义.

116 {
117 if (n < MULLO_DC_THRESHOLD) {
118 lmmp_mullo_dc_(dst, numa, numb, tp, n);
119 } else {
120 lmmp_mullo_fft_(dst, numa, numb, n, tp);
121 }
122}
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
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
#define n

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

函数调用图: