LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
binvert.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#include "mparam.h"
24#include "impl/tmp_alloc.h"
25#include "impl/inlines.h"
26#include "impl/mul_cache.h"
27#include "lmmp/lmmpn.h"
28#include "lmmp/numth.h"
29
30/**
31 * @brief 计算 [dst,n] = [xp,n]*[ap,n] div B^n
32 * @param dst 结果指针
33 * @param tp 需要 max(2*n, mersenne_next_size(2*n)) 个 limb
34 * @warning [xp,n] * [ap,n] mod B^n == 1
35 */
36static inline void binvert_mulhi_(mp_ptr dst, mp_srcptr xp, mp_srcptr ap, mp_size_t n, mp_ptr tp) {
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}
47
48static inline void lmmp_mullo_n_(
49 mp_ptr restrict dst,
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}
61
62/*
63balanced:
64 a := [numa,2*n]
65 we neead to find x such that x * a == 1 mod B^2n
66 we know that a == a_lo + a_hi * B^n
67 and x_lo == a_lo ^ -1 mod B^n
68 means x_lo * a_lo == 1 + k * B^n and k < B^n
69
70 x = x_lo * (2 - a * x_lo) mod B^2n
71 = x_lo * (2 - a_lo * x_lo - a_hi * x_lo * B^n) mod B^2n
72 = x_lo * (1 - k * B^n - a_hi * x_lo * B^n) mod B^2n
73 = x_lo - (k * x_lo + a_hi * x_lo^2) * B^n mod B^2n
74-----------------------------------------------------------------------------
75unbalanced:
76 a := [numa,na]
77 我们需要求x,使得x * a == 1 mod B^n ,同时n远远大于na
78 我们可以求出 x0 = a ^ -1 mod B^na,这是一个平衡的逆元
79 接下来,我们使用线性递推法来求,我们以na个limb为基本处理单元
80 假定现在已经求出 t 个,即 Xt = X0 + X1*B^na + X2*B^2na +... + X{t-1}*B^(t-1)*na
81 且满足 a*Xt == 1 mod B^t*na
82 可以写成 a*Xt = 1 + k * B^t*na, k < B^na
83 我们需要求出下一个 p,使得X{t+1} = X{t} + p*B^na
84 我们代入 a*X{t+1} = 1 mod B^(t+1)*na
85 可以得到
86 1 + k * B^t*na + a*p*B^t*na = 1 mod B^(t+1)*na
87 k + a*p = 0 mod B^na
88 p = -k * a^-1 mod B^na
89 此时,我们已经有了新的X{t+1},我们需要更新 k 为 k'
90 我们需要 k' 满足
91 a*X{t+1} = 1 + k' * B^(t+1)*na, k' < B^na
92 k' * B^na = k + a*p
93 k' = (k + a*p) / B^na
94*/
95
96
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}
152
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}
235
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}
#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 xhi
#define a_binvert
#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_mul_n_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#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
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
#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]
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=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
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
mp_size_t lmmp_mersenne_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 xp
#define numb
#define tp
#define n
#define scratch
#define BINVERT_UNBALANCE_MODM_THRESHOLD
#define MULHI_MERSENNE_THRESHOLD
#define BINVERT_UNBALANCE_MODM_CACHE_THRESHOLD
void lmmp_binvert_unbalance_1_(mp_ptr dst, mp_limb_t a, mp_size_t n)
计算 a 在 B^n 下的逆元
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
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_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 下的逆元
void lmmp_binvert_unbalance_2_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
计算 [numa,2] 在 B^n 下的逆元
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)