LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
div.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/longlong.h"
24#include "impl/inlines.h"
25#include "lmmp/lmmpn.h"
26
27
29 mp_limb_t q;
31 mp_limb_t a[3] = {numa[0], numa[1], numa[2]};
32 _udiv_qr_3by2(q, r1, r0, a[2], a[1], a[0], numb[1], numb[0], inv21);
33 numa[1] = r1;
34 numa[0] = r0;
35 return q;
36}
37
39 mp_limb_t ah, al;
40 if (na == 1) {
41 ah = numa[0];
42 return ah % x;
43 }
44 mp_limb_t t = numa[na - 2], q, r;
45 const int shift = lmmp_leading_zeros_(x);
46 if (shift > 0) {
47 const int rshift = LIMB_BITS - shift;
48 ah = numa[na - 1] >> rshift;
49 t = numa[na - 2];
50 al = (numa[na - 1] << shift) | (t >> rshift);
51 x <<= shift;
52 const mp_limb_t inv = lmmp_inv_1_(x);
53 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
54 na -= 2;
55 while (na-- > 0) {
56 ah = r;
57 al = t << shift;
58 t = numa[na];
59 al |= t >> rshift;
60 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
61 }
62 ah = r;
63 al = t << shift;
64 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
65 (void)q;
66 return r >> shift;
67 } else {
68 ah = 0;
69 t = numa[na - 2];
70 al = numa[na - 1];
71 const mp_limb_t inv = lmmp_inv_1_(x);
72 q = al / x;
73 r = al % x;
74 na -= 2;
75 while (na-- > 0) {
76 ah = r;
77 al = t;
78 t = numa[na];
79 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
80 }
81 ah = r;
82 al = t;
83 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
84 (void)q;
85 return r;
86 }
87}
88
90 mp_limb_t ah, al;
91 if (na == 1) {
92 ah = numa[0];
93 return ah % x;
94 }
95 mp_limb_t t = numa[na - 2], q, r;
96 if (k > 0) {
97 const mp_limb_t rshift = LIMB_BITS - k;
98 ah = numa[na - 1] >> rshift;
99 t = numa[na - 2];
100 al = (numa[na - 1] << k) | (t >> rshift);
101 x <<= k;
102 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
103 na -= 2;
104 while (na-- > 0) {
105 ah = r;
106 al = t << k;
107 t = numa[na];
108 al |= t >> rshift;
109 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
110 }
111 ah = r;
112 al = t << k;
113 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
114 (void)q;
115 return r >> k;
116 } else {
117 ah = 0;
118 t = numa[na - 2];
119 al = numa[na - 1];
120 q = al / x;
121 r = al % x;
122 na -= 2;
123 while (na-- > 0) {
124 ah = r;
125 al = t;
126 t = numa[na];
127 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
128 }
129 ah = r;
130 al = t;
131 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
132 (void)q;
133 return r;
134 }
135}
136
138 mp_limb_t ah, al;
139 if (na == 1) {
140 ah = numa[0];
141 if (dstq)
142 dstq[0] = ah / x;
143 return ah % x;
144 }
145 if (dstq) {
146 mp_limb_t t = numa[na - 2], q = 0, r = 0;
147 const int shift = lmmp_leading_zeros_(x);
148 if (shift > 0) {
149 /*
150 ah al
151 X|XXXtttX|XXXmmmX|XXXnnnX|XXX----|
152 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
153 t numa[na]
154
155 ah al
156 X|XXXtttX|XXXmmmX|XXXnnnX|XXX----|
157 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
158 t
159 numa[na]
160 */
161 const int rshift = LIMB_BITS - shift;
162 ah = numa[na - 1] >> rshift;
163 t = numa[na - 2];
164 al = (numa[na - 1] << shift) | (t >> rshift);
165 x <<= shift;
166 const mp_limb_t inv = lmmp_inv_1_(x);
167 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
168 dstq[na - 1] = q;
169 na -= 2;
170 while (na-- > 0) {
171 ah = r;
172 al = t << shift;
173 t = numa[na];
174 al |= t >> rshift;
175 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
176 dstq[na + 1] = q;
177 }
178 ah = r;
179 al = t << shift;
180 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
181 dstq[0] = q;
182 return r >> shift;
183 } else {
184 /*
185 ah al
186 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
187 t numa[na]
188 */
189 ah = 0;
190 t = numa[na - 2];
191 al = numa[na - 1];
192 const mp_limb_t inv = lmmp_inv_1_(x);
193 q = al / x;
194 r = al % x;
195 dstq[na - 1] = q;
196 na -= 2;
197 while (na-- > 0) {
198 ah = r;
199 al = t;
200 t = numa[na];
201 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
202 dstq[na + 1] = q;
203 }
204 ah = r;
205 al = t;
206 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
207 dstq[0] = q;
208 return r;
209 }
210 } else {
211 return lmmp_mod_1_(numa, na, x);
212 }
213}
214
216 mp_limb_t q, r1, r0, a2, a1, a0, b1, b0;
217 b1 = numb[1];
218 b0 = numb[0];
219 if (na == 2) {
220 int shift = lmmp_leading_zeros_(b1);
221 if (shift > 0) {
222 const int rshift = LIMB_BITS - shift;
223 b1 = (b1 << shift) | (b0 >> rshift);
224 b0 <<= shift;
225 a2 = numa[1] >> rshift;
226 a1 = (numa[1] << shift) | (numa[0] >> rshift);
227 a0 = (numa[0] << shift);
229 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
230 numb[0] = (r0 >> shift) | (r1 << rshift);
231 numb[1] = r1 >> shift;
232 return;
233 } else {
234 u128 a = _u128load(numa), b = _u128load(numb);
235 if (a < b) {
236 _u128store(numb, a);
237 return;
238 } else {
239 _u128store(numb, a - b);
240 return;
241 }
242 }
243 } else {
244 int shift = lmmp_leading_zeros_(b1);
245 if (shift > 0) {
246 const int rshift = LIMB_BITS - shift;
247 b1 = (b1 << shift) | (b0 >> rshift);
248 b0 <<= shift;
249 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
250 a2 = numa[na - 1] >> rshift;
251 a1 = (numa[na - 1] << shift) | (numa[na - 2] >> rshift);
252 a0 = (numa[na - 2] << shift) | (numa[na - 3] >> rshift);
253 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
254 na -= 2;
255 while (na-- > 1) {
256 a2 = r1;
257 a1 = r0;
258 a0 = (numa[na] << shift) | (numa[na - 1] >> rshift);
259 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
260 }
261
262 a2 = r1;
263 a1 = r0;
264 a0 = (numa[na] << shift);
265 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
266 numb[0] = (r0 >> shift) | (r1 << rshift);
267 numb[1] = r1 >> shift;
268 return;
269 } else {
270 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
271 a2 = 0;
272 a1 = numa[na - 1];
273 a0 = numa[na - 2];
274 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
275 na -= 2;
276 while (na-- > 1) {
277 a2 = r1;
278 a1 = r0;
279 a0 = numa[na];
280 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
281 }
282 a2 = r1;
283 a1 = r0;
284 a0 = numa[na];
285 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
286 numb[0] = r0;
287 numb[1] = r1;
288 return;
289 }
290 }
291}
292
293
295 mp_limb_t q, r1, r0, a2, a1, a0, b1, b0;
296 b1 = numb[1];
297 b0 = numb[0];
298 if (na == 2) {
299 int shift = lmmp_leading_zeros_(b1);
300 if (shift > 0) {
301 const int rshift = LIMB_BITS - shift;
302 b1 = (b1 << shift) | (b0 >> rshift);
303 b0 <<= shift;
304 a2 = numa[1] >> rshift;
305 a1 = (numa[1] << shift) | (numa[0] >> rshift);
306 a0 = (numa[0] << shift);
308 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
309 if (dstq)
310 dstq[0] = q;
311 numb[0] = (r0 >> shift) | (r1 << rshift);
312 numb[1] = r1 >> shift;
313 return;
314 } else {
315 u128 a = _u128load(numa), b = _u128load(numb);
316 if (a < b) {
317 _u128store(numb, a);
318 if (dstq)
319 dstq[0] = 0;
320 return;
321 } else {
322 _u128store(numb, a - b);
323 if (dstq)
324 dstq[0] = 1;
325 return;
326 }
327 }
328 }
329 if (dstq) {
330 int shift = lmmp_leading_zeros_(b1);
331 if (shift > 0) {
332 /*
333 a2 a1 a0
334 X|XXXtttX|XXXmmmX|XXXnnnX|XXX----|
335 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
336 numa[na]
337 */
338 const int rshift = LIMB_BITS - shift;
339 b1 = (b1 << shift) | (b0 >> rshift);
340 b0 <<= shift;
341 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
342 a2 = numa[na - 1] >> rshift;
343 a1 = (numa[na - 1] << shift) | (numa[na - 2] >> rshift);
344 a0 = (numa[na - 2] << shift) | (numa[na - 3] >> rshift);
345 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
346 dstq[na - 2] = q;
347 na -= 2;
348 while (na-- > 1) {
349 a2 = r1;
350 a1 = r0;
351 a0 = (numa[na] << shift) | (numa[na - 1] >> rshift);
352 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
353 dstq[na] = q;
354 }
355
356 a2 = r1;
357 a1 = r0;
358 a0 = (numa[na] << shift);
359 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
360 dstq[0] = q;
361 numb[0] = (r0 >> shift) | (r1 << rshift);
362 numb[1] = r1 >> shift;
363 return;
364 } else {
365 /*
366 a2 a1 a0
367 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
368 numa[na]
369 */
370 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
371 a2 = 0;
372 a1 = numa[na - 1];
373 a0 = numa[na - 2];
374 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
375 dstq[na - 2] = q;
376 na -= 2;
377 while (na-- > 1) {
378 a2 = r1;
379 a1 = r0;
380 a0 = numa[na];
381 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
382 dstq[na] = q;
383 }
384 a2 = r1;
385 a1 = r0;
386 a0 = numa[na];
387 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
388 dstq[0] = q;
389 numb[0] = r0;
390 numb[1] = r1;
391 return;
392 }
393 } else {
394 int shift = lmmp_leading_zeros_(b1);
395 if (shift > 0) {
396 const int rshift = LIMB_BITS - shift;
397 b1 = (b1 << shift) | (b0 >> rshift);
398 b0 <<= shift;
399 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
400 a2 = numa[na - 1] >> rshift;
401 a1 = (numa[na - 1] << shift) | (numa[na - 2] >> rshift);
402 a0 = (numa[na - 2] << shift) | (numa[na - 3] >> rshift);
403 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
404 na -= 2;
405 while (na-- > 1) {
406 a2 = r1;
407 a1 = r0;
408 a0 = (numa[na] << shift) | (numa[na - 1] >> rshift);
409 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
410 }
411
412 a2 = r1;
413 a1 = r0;
414 a0 = (numa[na] << shift);
415 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
416 numb[0] = (r0 >> shift) | (r1 << rshift);
417 numb[1] = r1 >> shift;
418 return;
419 } else {
420 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
421 a2 = 0;
422 a1 = numa[na - 1];
423 a0 = numa[na - 2];
424 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
425 na -= 2;
426 while (na-- > 1) {
427 a2 = r1;
428 a1 = r0;
429 a0 = numa[na];
430 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
431 }
432 a2 = r1;
433 a1 = r0;
434 a0 = numa[na];
435 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
436 numb[0] = r0;
437 numb[1] = r1;
438 return;
439 }
440 }
441}
442
444 mp_limb_t ah, al;
445 mp_limb_t t = numa[na - 2], q = 0, r = 0;
446 /*
447 ah al
448 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
449 t numa[na]
450 */
451 ah = 0;
452 t = numa[na - 2];
453 al = numa[na - 1];
454 const mp_limb_t inv = lmmp_inv_1_(x);
455 q = al / x;
456 r = al % x;
457 const mp_limb_t qh = q;
458 na -= 2;
459 while (na-- > 0) {
460 ah = r;
461 al = t;
462 t = numa[na];
463 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
464 dstq[na + 1] = q;
465 }
466 ah = r;
467 al = t;
468 _udiv_qrnnd_preinv(q, r, ah, al, x, inv);
469 dstq[0] = q;
470 numa[0] = r;
471 return qh;
472}
473
475 mp_limb_t q, r1, r0, a2, a1, a0, b1, b0;
476 b1 = numb[1];
477 b0 = numb[0];
478 /*
479 a2 a1 a0
480 |000XXXX|tttXXXX|mmmXXXX|nnnXXXX|
481 numa[na]
482 */
483 const mp_limb_t inv = lmmp_inv_2_1_(b1, b0);
484 a2 = 0;
485 a1 = numa[na - 1];
486 a0 = numa[na - 2];
487 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
488 const mp_limb_t qh = q;
489 na -= 2;
490 while (na-- > 1) {
491 a2 = r1;
492 a1 = r0;
493 a0 = numa[na];
494 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
495 dstq[na] = q;
496 }
497 a2 = r1;
498 a1 = r0;
499 a0 = numa[na];
500 _udiv_qr_3by2(q, r1, r0, a2, a1, a0, b1, b0, inv);
501 dstq[0] = q;
502 numa[0] = r0;
503 numa[1] = r1;
504 return qh;
505}
#define k
#define lmmp_leading_zeros_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
mp_limb_t lmmp_div_3_2_(mp_ptr numa, mp_srcptr numb, mp_limb_t inv21)
3/2位除法运算 [numa,2]=[numa,3] mod [numb,2]
mp_limb_t lmmp_div_1_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_limb_t x)
单精度数除法(除数为1个limb)
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
void lmmp_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
定义 div.c:294
mp_limb_t lmmp_mod_preinv_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x, mp_limb_t inv, mp_limb_t k)
单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_
定义 div.c:89
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
void lmmp_mod_2_(mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数取余 (除数为2个limb)
定义 div.c:215
mp_limb_t lmmp_div_2_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb)
双精度数除法(除数为2个limb)
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
定义 inv.c:27
#define _udiv_qrnnd_preinv(q, r, nh, nl, d, di)
#define _udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)
#define b0
#define b1
#define a0
#define a1
#define r1
#define a2
#define r0
#define t
#define numb
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)