LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
powlo.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 "impl/tmp_alloc.h"
24#include "impl/longlong.h"
25#include "impl/inlines.h"
26#include "mparam.h"
27#include "lmmp/lmmpn.h"
28#include "lmmp/numth.h"
29
30
31static inline void lmmp_sqrlo_n_(
32 mp_ptr restrict dst,
36) {
37 if (n < MULLO_DC_THRESHOLD) {
38 lmmp_sqrlo_dc_(dst, numa, tp, n);
39 } else {
40 lmmp_mullo_fft_(dst, numa, numa, n, tp);
41 }
42}
43
44static inline void lmmp_mullo_n_(
45 mp_ptr restrict dst,
50) {
51 if (n < MULLO_DC_THRESHOLD) {
52 lmmp_mullo_dc_(dst, numa, numb, tp, n);
53 } else {
54 lmmp_mullo_fft_(dst, numa, numb, n, tp);
55 }
56}
57
58static inline mp_size_t win_size(mp_size_t eb) {
60 static mp_bitcnt_t x[] = {7, 25, 81, 241, 673, 1793, 4609, 11521, 28161, ~(mp_bitcnt_t)0};
61 for (k = 0; eb > x[k++];);
62 return k;
63}
64
65#define getbit(p, bi) ((p[(bi - 1) / LIMB_BITS] >> (bi - 1) % LIMB_BITS) & 1)
66
67static inline mp_limb_t getbits(const mp_limb_t* p, mp_bitcnt_t bi, mp_bitcnt_t nbits) {
68 mp_bitcnt_t nbits_in_r;
69 mp_limb_t r;
70 mp_size_t i;
71
72 if (bi <= nbits) {
73 return p[0] & (((mp_limb_t)1 << bi) - 1);
74 } else {
75 bi -= nbits; /* bit index of low bit to extract */
76 i = bi / LIMB_BITS; /* word index of low bit to extract */
77 bi %= LIMB_BITS; /* bit index in low word */
78 r = p[i] >> bi; /* extract (low) bits */
79 nbits_in_r = LIMB_BITS - bi; /* number of bits now in r */
80 if (nbits_in_r < nbits) /* did we get enough bits? */
81 r += p[i + 1] << nbits_in_r; /* prepend bits from higher word */
82 return r & (((mp_limb_t)1 << nbits) - 1);
83 }
84}
85
87 return (n - 1) * LIMB_BITS + lmmp_limb_bits_(p[n - 1]);
88}
89
91 lmmp_param_assert(ep[en - 1] > 0);
92 lmmp_param_assert(n > 0 && en > 0);
93 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL);
94 if (n == 1) {
95 lmmp_powlo_1_(dst, bp, ep, en);
96 return;
97 }
98 if (n == 2) {
99 lmmp_powlo_2_(dst, bp, ep, en);
100 return;
101 }
102 mp_bitcnt_t cnt, ebi;
103 unsigned windowsize, this_windowsize;
104 mp_limb_t expbits;
105 mp_limb_t* pp;
106 long i;
107 int flipflop;
108 TEMP_DECL;
110 mp_ptr restrict scratch = tp + 3 * n;
111
112 ebi = count_bits(ep, en);
113
114 /* 指数为 1:[bp,n] mod B^n 即截断本身,免去建表与梯子 */
115 if (ebi == 1) {
116 lmmp_copy(dst, bp, n);
117 TEMP_FREE;
118 return;
119 }
120
121 windowsize = win_size(ebi);
122 if (windowsize > 1) {
123 mp_limb_t *this_pp, *last_pp;
124 lmmp_debug_assert(windowsize < ebi);
125
126 pp = TALLOC_TYPE((n << (windowsize - 1)), mp_limb_t);
127
128 this_pp = pp;
129
130 lmmp_copy(this_pp, bp, n);
131
132 /* Store b^2 in tp. */
133 lmmp_sqrlo_n_(tp, bp, n, scratch);
134
135 /* Precompute odd powers of b and put them in the temporary area at pp. */
136 i = (1 << (windowsize - 1)) - 1;
137 do {
138 last_pp = this_pp;
139 this_pp += n;
140 lmmp_mullo_n_(this_pp, last_pp, tp, n, scratch);
141 } while (--i != 0);
142
143 expbits = getbits(ep, ebi, windowsize);
144 ebi -= windowsize;
145
146 ctz_shr_u64(expbits, expbits, cnt);
147 ebi += cnt;
148
149 lmmp_copy(dst, pp + n * (expbits >> 1), n);
150 } else {
151 pp = tp + n;
152 lmmp_copy(pp, bp, n);
153 lmmp_copy(dst, bp, n);
154 --ebi;
155 }
156
157 flipflop = 0;
158
159 do {
160 while (getbit(ep, ebi) == 0) {
161 lmmp_sqrlo_n_(tp, dst, n, scratch);
162 LMMP_SWAP(dst, tp, mp_ptr);
163 flipflop = !flipflop;
164 if (--ebi == 0)
165 goto done;
166 }
167
168 /* The next bit of the exponent is 1. Now extract the largest block of
169 bits <= windowsize, and such that the least significant bit is 1. */
170
171 expbits = getbits(ep, ebi, windowsize);
172 this_windowsize = LMMP_MIN(windowsize, ebi);
173
174 ctz_shr_u64(expbits, expbits, cnt);
175 this_windowsize -= cnt;
176 ebi -= this_windowsize;
177
178 while (this_windowsize > 1) {
179 lmmp_sqrlo_n_(tp, dst, n, scratch);
180 lmmp_sqrlo_n_(dst, tp, n, scratch);
181 this_windowsize -= 2;
182 }
183
184 if (this_windowsize != 0)
185 lmmp_sqrlo_n_(tp, dst, n, scratch);
186 else {
187 LMMP_SWAP(dst, tp, mp_ptr);
188 flipflop = !flipflop;
189 }
190 lmmp_mullo_n_(dst, tp, pp + n * (expbits >> 1), n, scratch);
191 } while (ebi != 0);
192
193done:
194 if (flipflop)
195 lmmp_copy(tp, dst, n);
196 TEMP_FREE;
197}
198
199/*
200 模 B 与模 B^2 的特化梯子。
201
202 模 B^n 的乘法无需归约(截断低位即取模),小 n 时全积与窗口表退化为
203 标量运算:1 limb 为 u64 自然回绕乘;2 limb 借 longlong.h 的 128 位
204 低位积内联 _umul128to128_。梯子结构与泛型版一致(滑窗 + 首窗口),
205 仅指数为 1 时提前截断返回。
206*/
207
209 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL);
210 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
211 mp_limb_t u = bp[0];
212 mp_bitcnt_t ebi = count_bits(ep, en);
213
214 /* 指数为 1:b mod B 即 [bp,1] 本身 */
215 if (ebi == 1) {
216 dst[0] = u;
217 return;
218 }
219
220 unsigned windowsize = win_size(ebi);
221 lmmp_debug_assert(windowsize < ebi);
222 mp_bitcnt_t cnt;
223 unsigned this_windowsize;
224 mp_limb_t expbits;
225 TEMP_DECL;
226 mp_ptr restrict pp = TALLOC_TYPE((mp_size_t)1 << (windowsize - 1), mp_limb_t);
227
228 pp[0] = u;
229 if (windowsize > 1) {
230 mp_limb_t b2 = u * u; /* b^2 mod B:u64 回绕乘 */
231 for (mp_size_t i = 1; i < ((mp_size_t)1 << (windowsize - 1)); i++)
232 pp[i] = pp[i - 1] * b2;
233
234 expbits = getbits(ep, ebi, windowsize);
235 ebi -= windowsize;
236
237 ctz_shr_u64(expbits, expbits, cnt);
238 ebi += cnt;
239
240 u = pp[expbits >> 1];
241 } else {
242 --ebi;
243 }
244
245 while (ebi != 0) {
246 while (getbit(ep, ebi) == 0) {
247 u *= u;
248 if (--ebi == 0)
249 goto done;
250 }
251
252 /* The next bit of the exponent is 1. Now extract the largest block of
253 bits <= windowsize, and such that the least significant bit is 1. */
254
255 expbits = getbits(ep, ebi, windowsize);
256 this_windowsize = LMMP_MIN(windowsize, ebi);
257
258 ctz_shr_u64(expbits, expbits, cnt);
259 this_windowsize -= cnt;
260 ebi -= this_windowsize;
261
262 while (this_windowsize > 1) {
263 u *= u;
264 u *= u;
265 this_windowsize -= 2;
266 }
267
268 if (this_windowsize != 0)
269 u *= u;
270 u *= pp[expbits >> 1];
271 }
272
273done:
274 dst[0] = u;
275 TEMP_FREE;
276}
277
279 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL);
280 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
281 u128 u = _u128load(bp);
282 mp_bitcnt_t ebi = count_bits(ep, en);
283
284 /* 指数为 1:b mod B^2 即 [bp,2] 本身 */
285 if (ebi == 1) {
286 _u128store(dst, u);
287 return;
288 }
289
290 unsigned windowsize = win_size(ebi);
291 lmmp_debug_assert(windowsize < ebi);
292 mp_bitcnt_t cnt;
293 unsigned this_windowsize;
294 mp_limb_t expbits;
295 TEMP_DECL;
296 u128* restrict pp = TALLOC_TYPE((mp_size_t)1 << (windowsize - 1), u128);
297
298 pp[0] = u;
299 if (windowsize > 1) {
300 u128 b2 = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u)); /* b^2 mod B^2 */
301 for (mp_size_t i = 1; i < ((mp_size_t)1 << (windowsize - 1)); i++)
302 pp[i] = _umul128to128_(_u128high(pp[i - 1]), _u128low(pp[i - 1]), _u128high(b2), _u128low(b2));
303
304 expbits = getbits(ep, ebi, windowsize);
305 ebi -= windowsize;
306
307 ctz_shr_u64(expbits, expbits, cnt);
308 ebi += cnt;
309
310 u = pp[expbits >> 1];
311 } else {
312 --ebi;
313 }
314
315 while (ebi != 0) {
316 while (getbit(ep, ebi) == 0) {
317 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u));
318 if (--ebi == 0)
319 goto done;
320 }
321
322 /* The next bit of the exponent is 1. Now extract the largest block of
323 bits <= windowsize, and such that the least significant bit is 1. */
324
325 expbits = getbits(ep, ebi, windowsize);
326 this_windowsize = LMMP_MIN(windowsize, ebi);
327
328 ctz_shr_u64(expbits, expbits, cnt);
329 this_windowsize -= cnt;
330 ebi -= this_windowsize;
331
332 while (this_windowsize > 1) {
333 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u));
334 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u));
335 this_windowsize -= 2;
336 }
337
338 if (this_windowsize != 0)
339 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(u), _u128low(u));
340 u = _umul128to128_(_u128high(u), _u128low(u), _u128high(pp[expbits >> 1]), _u128low(pp[expbits >> 1]));
341 }
342
343done:
344 _u128store(dst, u);
345 TEMP_FREE;
346}
#define k
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_limb_bits_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
size_t mp_bitcnt_t
定义 lmmp.h:98
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_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define MULLO_DC_THRESHOLD
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_sqrlo_dc_(mp_ptr dst, mp_srcptr numa, mp_ptr tp, mp_size_t n)
低位平方 [dst,n] = [numa,n]^2 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 ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static __uint128_t _umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)
#define b2
#define numb
#define tp
#define n
#define scratch
void lmmp_powlo_(mp_ptr dst, mp_srcptr bp, mp_size_t n, mp_srcptr ep, mp_size_t en)
计算 [bp,n]^[ep,en] mod B^n,并将结果写入 [dst,n]
void lmmp_powlo_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,2]^[ep,en] mod B^2,并将结果写入 [dst,2](lmmp_powlo_ 的 2 limb 特化)
void lmmp_powlo_1_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,1]^[ep,en] mod B,并将结果写入 [dst,1](lmmp_powlo_ 的 1 limb 特化)
static mp_size_t win_size(mp_size_t eb)
定义 powlo.c:58
#define getbit(p, bi)
定义 powlo.c:65
static mp_bitcnt_t count_bits(mp_srcptr p, mp_size_t n)
定义 powlo.c:86
static mp_limb_t getbits(const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
定义 powlo.c:67
static void lmmp_sqrlo_n_(mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t n, mp_ptr restrict tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 powlo.c:31
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)