LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom62.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/mul_hard.h"
24#include "mparam.h"
25#include "lmmpn/toom_interp.h"
26
28
29
30#define lmmp_mul_n_(dst, numa, numb, n) \
31 if ((n) < MUL_TOOM22_THRESHOLD) \
32 lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
33 else if ((n) < MUL_TOOM33_THRESHOLD) \
34 lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
35 else if ((n) < MUL_TOOM44_THRESHOLD) \
36 lmmp_mul_toom33_((dst), (numa), (n), (numb), (n)); \
37 else \
38 lmmp_mul_toom44_((dst), (numa), (n), (numb), (n))
39
40/*
41Evaluate in:
42 0, +1, -1, +2, -2, 1/2, +inf
43
44 <-s-><--n--><--n--><--n--><--n--><--n-->
45 |a5-|--a4--|--a3--|--a2--|--a1--|--a0--|
46 |-b1-|--b0--|
47 <-t--><--n-->
48
49 v0 = a0 * b0 # A(0)*B(0)
50 v1 = ( a0+ a1+ a2+ a3+ a4+ a5)*( b0+ b1) # A(1)*B(1) ah <= 5 bh <= 1
51 vm1 = ( a0- a1+ a2- a3+ a4- a5)*( b0- b1) # A(-1)*B(-1) |ah| <= 2 bh = 0
52 v2 = ( a0+ 2a1+4a2+8a3+16a4+32a5)*( b0+2b1) # A(2)*B(2) ah <= 62 bh <= 2
53 vm2 = ( a0- 2a1+4a2-8a3+16a4-32a5)*( b0-2b1) # A(-2)*B(-2) -41<=ah<=20 -1<=bh<=0
54 vh = (32a0+16a1+8a2+4a3+ 2a4+ a5)*(2b0+ b1) # A(1/2)*B(1/2) ah <= 62 bh <= 2
55 vinf= a5 * b1 # A(inf)*B(inf)
56*/
57
59 lmmp_param_assert(6 * nb > na);
60 lmmp_param_assert(2 * na > 5 * nb);
61
62 mp_size_t n, s, t;
63 mp_limb_t cy;
64 mp_ptr as1, asm1, as2, asm2, ash;
66 mp_ptr gp;
67 enum toom7_flags aflags, bflags;
69
70#define a0 numa
71#define a1 (numa + n)
72#define a2 (numa + 2 * n)
73#define a3 (numa + 3 * n)
74#define a4 (numa + 4 * n)
75#define a5 (numa + 5 * n)
76#define b0 numb
77#define b1 (numb + n)
78
79 n = 1 + (na >= 3 * nb ? (na - 1) / (mp_size_t)6 : (nb - 1) >> 1);
80 lmmp_param_assert(na > 5 * n && nb > n);
81 s = na - 5 * n;
82 t = nb - n;
83
84 lmmp_param_assert(0 < s && s <= n);
85 lmmp_param_assert(0 < t && t <= n);
86
88
90 as1 = tmp;
91 asm1 = as1 + n + 1;
92 as2 = asm1 + n + 1;
93 asm2 = as2 + n + 1;
94 ash = asm2 + n + 1;
95 bs1 = ash + n + 1;
96 bsm1 = bs1 + n + 1;
97 bs2 = bsm1 + n;
98 bsm2 = bs2 + n + 1;
99 bsh = bsm2 + n + 1;
100
101 gp = dst;
102
103 /* Compute as1 and asm1. */
104 aflags = (enum toom7_flags)(toom7_w3_neg & lmmp_toom_eval_pm1_(as1, asm1, 5, numa, n, s, gp));
105
106 /* Compute as2 and asm2. */
107 aflags = (enum toom7_flags)(aflags | (toom7_w1_neg & lmmp_toom_eval_pm2_(as2, asm2, 5, numa, n, s, gp)));
108
109 /* Compute ash = 32 a0 + 16 a1 + 8 a2 + 4 a3 + 2 a4 + a5
110 = 2*(2*(2*(2*(2*a0 + a1) + a2) + a3) + a4) + a5 */
111
112 cy = lmmp_addshl1_n_(ash, a1, a0, n);
113 cy = 2 * cy + lmmp_addshl1_n_(ash, a2, ash, n);
114 cy = 2 * cy + lmmp_addshl1_n_(ash, a3, ash, n);
115 cy = 2 * cy + lmmp_addshl1_n_(ash, a4, ash, n);
116 if (s < n) {
117 mp_limb_t cy2;
118 cy2 = lmmp_addshl1_n_(ash, a5, ash, s);
119 ash[n] = 2 * cy + lmmp_shl_(ash + s, ash + s, n - s, 1);
120 lmmp_inc_1(ash + s, cy2);
121 } else
122 ash[n] = 2 * cy + lmmp_addshl1_n_(ash, a5, ash, n);
123
124 /* Compute bs1 and bsm1. */
125 if (t == n) {
126 if (lmmp_cmp_(b0, b1, n) < 0) {
127 cy = lmmp_add_n_sub_n_(bs1, bsm1, b1, b0, n);
128 bflags = toom7_w3_neg;
129 } else {
130 cy = lmmp_add_n_sub_n_(bs1, bsm1, b0, b1, n);
131 bflags = (enum toom7_flags)0;
132 }
133 bs1[n] = cy >> 1;
134 } else {
135 bs1[n] = lmmp_add_(bs1, b0, n, b1, t);
136 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
137 lmmp_sub_n_(bsm1, b1, b0, t);
138 lmmp_zero(bsm1 + t, n - t);
139 bflags = toom7_w3_neg;
140 } else {
141 lmmp_sub_(bsm1, b0, n, b1, t);
142 bflags = (enum toom7_flags)0;
143 }
144 }
145
146 /* Compute bs2 and bsm2. Recycling bs1 and bsm1; bs2=bs1+b1, bsm2 =
147 bsm1 - b1 */
148 lmmp_add_(bs2, bs1, n + 1, b1, t);
149 if (bflags & toom7_w3_neg) {
150 bsm2[n] = lmmp_add_(bsm2, bsm1, n, b1, t);
151 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
152 } else {
153 if (t < n) {
154 if (lmmp_zero_q_(bsm1 + t, n - t) && lmmp_cmp_(bsm1, b1, t) < 0) {
156 lmmp_zero(bsm2 + t, n + 1 - t);
157 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
158 } else {
159 lmmp_sub_(bsm2, bsm1, n, b1, t);
160 bsm2[n] = 0;
161 }
162 } else {
163 if (lmmp_cmp_(bsm1, b1, n) < 0) {
165 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
166 } else {
168 }
169 bsm2[n] = 0;
170 }
171 }
172
173 /* Compute bsh, recycling bs1. bsh=bs1+b0; */
174 bsh[n] = bs1[n] + lmmp_add_n_(bsh, bs1, b0, n);
175
176 lmmp_debug_assert(as1[n] <= 5);
177 lmmp_debug_assert(bs1[n] <= 1);
178 lmmp_debug_assert(asm1[n] <= 2);
179 lmmp_debug_assert(as2[n] <= 62);
180 lmmp_debug_assert(bs2[n] <= 2);
181 lmmp_debug_assert(asm2[n] <= 41);
182 lmmp_debug_assert(bsm2[n] <= 1);
183 lmmp_debug_assert(ash[n] <= 62);
184 lmmp_debug_assert(bsh[n] <= 2);
185
186#define v0 dst /* 2n */
187#define v1 (dst + 2 * n) /* 2n+1 */
188#define vinf (dst + 6 * n) /* s+t */
189#define v2 scratch /* 2n+1 */
190#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
191#define vh (scratch + 4 * n + 2) /* 2n+1 */
192#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
193#define scratch_out (scratch + 8 * n + 4) /* 2n+1 */
194 /* Total scratch need: 10*n+5 */
195
196 /* Must be in allocation order, as they overwrite one limb beyond
197 * 2n+1. */
198 lmmp_mul_n_(v2, as2, bs2, n + 1); /* v2, 2n+1 limbs */
199 lmmp_mul_n_(vm2, asm2, bsm2, n + 1); /* vm2, 2n+1 limbs */
200 lmmp_mul_n_(vh, ash, bsh, n + 1); /* vh, 2n+1 limbs */
201
202 /* vm1, 2n+1 limbs */
204 cy = 0;
205 if (asm1[n] == 1) {
206 cy = lmmp_add_n_(vm1 + n, vm1 + n, bsm1, n);
207 } else if (asm1[n] == 2) {
208 cy = lmmp_addshl1_n_(vm1 + n, vm1 + n, bsm1, n);
209 }
210 vm1[2 * n] = cy;
211
212 /* v1, 2n+1 limbs */
213 lmmp_mul_n_(v1, as1, bs1, n);
214 if (as1[n] == 1) {
215 cy = bs1[n] + lmmp_add_n_(v1 + n, v1 + n, bs1, n);
216 } else if (as1[n] == 2) {
217 cy = 2 * bs1[n] + lmmp_addshl1_n_(v1 + n, v1 + n, bs1, n);
218 } else if (as1[n] != 0) {
219 cy = as1[n] * bs1[n] + lmmp_addmul_1_(v1 + n, bs1, n, as1[n]);
220 } else
221 cy = 0;
222 if (bs1[n] != 0)
223 cy += lmmp_add_n_(v1 + n, v1 + n, as1, n);
224 v1[2 * n] = cy;
225
226 lmmp_mul_n_(v0, a0, b0, n); /* v0, 2n limbs */
227
228 /* vinf, s+t limbs */
229 if (s > t)
230 lmmp_mul_(vinf, a5, s, b1, t);
231 else
232 lmmp_mul_(vinf, b1, t, a5, s);
233
234 lmmp_toom_interp7_(dst, n, (enum toom7_flags)(aflags ^ bflags), vm2, vm1, v2, vh, s + t, scratch_out);
235
237}
238
252
254 mp_ptr restrict dst,
255 mp_srcptr restrict numa,
256 toom62_cache_t* cache
257) {
258#define numb (cache->numb)
259#define n (cache->n)
260#define s (cache->s)
261#define t (cache->t)
262#define scratch (cache->scratch)
263#define tmp (cache->tmp)
264#define bs1 (cache->bs1)
265#define bsm1 (cache->bsm1)
266#define bs2 (cache->bs2)
267#define bsm2 (cache->bsm2)
268#define bsh (cache->bsh)
269
270 mp_limb_t cy;
271 mp_ptr restrict as1, asm1, as2, asm2, ash;
272 enum toom7_flags aflags, bflags;
273
274#define a0 numa
275#define a1 (numa + n)
276#define a2 (numa + 2 * n)
277#define a3 (numa + 3 * n)
278#define a4 (numa + 4 * n)
279#define a5 (numa + 5 * n)
280#define b0 numb
281#define b1 (numb + n)
282
283
284 as1 = tmp;
285 asm1 = as1 + n + 1;
286 as2 = asm1 + n + 1;
287 asm2 = as2 + n + 1;
288 ash = asm2 + n + 1;
289
290
291 /* Compute as1 and asm1. */
292 aflags = (enum toom7_flags)(toom7_w3_neg & lmmp_toom_eval_pm1_(as1, asm1, 5, numa, n, s, dst));
293
294 /* Compute as2 and asm2. */
295 aflags = (enum toom7_flags)(aflags | (toom7_w1_neg & lmmp_toom_eval_pm2_(as2, asm2, 5, numa, n, s, dst)));
296
297 /* Compute ash = 32 a0 + 16 a1 + 8 a2 + 4 a3 + 2 a4 + a5
298 = 2*(2*(2*(2*(2*a0 + a1) + a2) + a3) + a4) + a5 */
299
300 cy = lmmp_addshl1_n_(ash, a1, a0, n);
301 cy = 2 * cy + lmmp_addshl1_n_(ash, a2, ash, n);
302 cy = 2 * cy + lmmp_addshl1_n_(ash, a3, ash, n);
303 cy = 2 * cy + lmmp_addshl1_n_(ash, a4, ash, n);
304 if (s < n) {
305 mp_limb_t cy2;
306 cy2 = lmmp_addshl1_n_(ash, a5, ash, s);
307 ash[n] = 2 * cy + lmmp_shl_(ash + s, ash + s, n - s, 1);
308 lmmp_inc_1(ash + s, cy2);
309 } else
310 ash[n] = 2 * cy + lmmp_addshl1_n_(ash, a5, ash, n);
311
312 /* Compute bs1 and bsm1. */
313 if (t == n) {
314 if (lmmp_cmp_(b0, b1, n) < 0) {
315 cy = lmmp_add_n_sub_n_(bs1, bsm1, b1, b0, n);
316 bflags = toom7_w3_neg;
317 } else {
318 cy = lmmp_add_n_sub_n_(bs1, bsm1, b0, b1, n);
319 bflags = (enum toom7_flags)0;
320 }
321 bs1[n] = cy >> 1;
322 } else {
323 bs1[n] = lmmp_add_(bs1, b0, n, b1, t);
324 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
325 lmmp_sub_n_(bsm1, b1, b0, t);
326 lmmp_zero(bsm1 + t, n - t);
327 bflags = toom7_w3_neg;
328 } else {
329 lmmp_sub_(bsm1, b0, n, b1, t);
330 bflags = (enum toom7_flags)0;
331 }
332 }
333
334 /* Compute bs2 and bsm2. Recycling bs1 and bsm1; bs2=bs1+b1, bsm2 =
335 bsm1 - b1 */
336 lmmp_add_(bs2, bs1, n + 1, b1, t);
337 if (bflags & toom7_w3_neg) {
338 bsm2[n] = lmmp_add_(bsm2, bsm1, n, b1, t);
339 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
340 } else {
341 if (t < n) {
342 if (lmmp_zero_q_(bsm1 + t, n - t) && lmmp_cmp_(bsm1, b1, t) < 0) {
344 lmmp_zero(bsm2 + t, n + 1 - t);
345 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
346 } else {
347 lmmp_sub_(bsm2, bsm1, n, b1, t);
348 bsm2[n] = 0;
349 }
350 } else {
351 if (lmmp_cmp_(bsm1, b1, n) < 0) {
353 bflags = (enum toom7_flags)(bflags | toom7_w1_neg);
354 } else {
356 }
357 bsm2[n] = 0;
358 }
359 }
360
361 /* Compute bsh, recycling bs1. bsh=bs1+b0; */
362 bsh[n] = bs1[n] + lmmp_add_n_(bsh, bs1, b0, n);
363
364 lmmp_debug_assert(as1[n] <= 5);
365 lmmp_debug_assert(bs1[n] <= 1);
366 lmmp_debug_assert(asm1[n] <= 2);
367 lmmp_debug_assert(as2[n] <= 62);
368 lmmp_debug_assert(bs2[n] <= 2);
369 lmmp_debug_assert(asm2[n] <= 41);
370 lmmp_debug_assert(bsm2[n] <= 1);
371 lmmp_debug_assert(ash[n] <= 62);
372 lmmp_debug_assert(bsh[n] <= 2);
373
374#define v0 dst /* 2n */
375#define v1 (dst + 2 * n) /* 2n+1 */
376#define vinf (dst + 6 * n) /* s+t */
377#define v2 scratch /* 2n+1 */
378#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
379#define vh (scratch + 4 * n + 2) /* 2n+1 */
380#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
381#define scratch_out (scratch + 8 * n + 4) /* 2n+1 */
382 /* Total scratch need: 10*n+5 */
383
384 /* Must be in allocation order, as they overwrite one limb beyond
385 * 2n+1. */
386 lmmp_mul_n_(v2, as2, bs2, n + 1); /* v2, 2n+1 limbs */
387 lmmp_mul_n_(vm2, asm2, bsm2, n + 1); /* vm2, 2n+1 limbs */
388 lmmp_mul_n_(vh, ash, bsh, n + 1); /* vh, 2n+1 limbs */
389
390 /* vm1, 2n+1 limbs */
392 cy = 0;
393 if (asm1[n] == 1) {
394 cy = lmmp_add_n_(vm1 + n, vm1 + n, bsm1, n);
395 } else if (asm1[n] == 2) {
396 cy = lmmp_addshl1_n_(vm1 + n, vm1 + n, bsm1, n);
397 }
398 vm1[2 * n] = cy;
399
400 /* v1, 2n+1 limbs */
401 lmmp_mul_n_(v1, as1, bs1, n);
402 if (as1[n] == 1) {
403 cy = bs1[n] + lmmp_add_n_(v1 + n, v1 + n, bs1, n);
404 } else if (as1[n] == 2) {
405 cy = 2 * bs1[n] + lmmp_addshl1_n_(v1 + n, v1 + n, bs1, n);
406 } else if (as1[n] != 0) {
407 cy = as1[n] * bs1[n] + lmmp_addmul_1_(v1 + n, bs1, n, as1[n]);
408 } else
409 cy = 0;
410 if (bs1[n] != 0)
411 cy += lmmp_add_n_(v1 + n, v1 + n, as1, n);
412 v1[2 * n] = cy;
413
414 lmmp_mul_n_(v0, a0, b0, n); /* v0, 2n limbs */
415
416 /* vinf, s+t limbs */
417 if (s > t)
418 lmmp_mul_(vinf, a5, s, b1, t);
419 else
420 lmmp_mul_(vinf, b1, t, a5, s);
421
422 lmmp_toom_interp7_(dst, n, (enum toom7_flags)(aflags ^ bflags), vm2, vm1, v2, vh, s + t, scratch_out);
423
424 return bflags;
425#undef numb
426#undef n
427#undef s
428#undef t
429#undef scratch
430#undef tmp
431#undef bs1
432#undef bsm1
433#undef bs2
434#undef bsm2
435#undef bsh
436}
437
439 mp_ptr restrict dst,
440 mp_srcptr restrict numa,
441 const toom62_cache_t* cache,
442 enum toom7_flags bflags
443) {
444#define numb (cache->numb)
445#define n (cache->n)
446#define s (cache->s)
447#define t (cache->t)
448#define scratch (cache->scratch)
449#define tmp (cache->tmp)
450#define bs1 (cache->bs1)
451#define bsm1 (cache->bsm1)
452#define bs2 (cache->bs2)
453#define bsm2 (cache->bsm2)
454#define bsh (cache->bsh)
455
456 mp_limb_t cy;
457 mp_ptr as1, asm1, as2, asm2, ash;
458 enum toom7_flags aflags;
459
460#define a0 numa
461#define a1 (numa + n)
462#define a2 (numa + 2 * n)
463#define a3 (numa + 3 * n)
464#define a4 (numa + 4 * n)
465#define a5 (numa + 5 * n)
466#define b0 numb
467#define b1 (numb + n)
468
469 as1 = tmp;
470 asm1 = as1 + n + 1;
471 as2 = asm1 + n + 1;
472 asm2 = as2 + n + 1;
473 ash = asm2 + n + 1;
474
475
476 /* Compute as1 and asm1. */
477 aflags = (enum toom7_flags)(toom7_w3_neg & lmmp_toom_eval_pm1_(as1, asm1, 5, numa, n, s, dst));
478
479 /* Compute as2 and asm2. */
480 aflags = (enum toom7_flags)(aflags | (toom7_w1_neg & lmmp_toom_eval_pm2_(as2, asm2, 5, numa, n, s, dst)));
481
482 /* Compute ash = 32 a0 + 16 a1 + 8 a2 + 4 a3 + 2 a4 + a5
483 = 2*(2*(2*(2*(2*a0 + a1) + a2) + a3) + a4) + a5 */
484
485 cy = lmmp_addshl1_n_(ash, a1, a0, n);
486 cy = 2 * cy + lmmp_addshl1_n_(ash, a2, ash, n);
487 cy = 2 * cy + lmmp_addshl1_n_(ash, a3, ash, n);
488 cy = 2 * cy + lmmp_addshl1_n_(ash, a4, ash, n);
489 if (s < n) {
490 mp_limb_t cy2;
491 cy2 = lmmp_addshl1_n_(ash, a5, ash, s);
492 ash[n] = 2 * cy + lmmp_shl_(ash + s, ash + s, n - s, 1);
493 lmmp_inc_1(ash + s, cy2);
494 } else
495 ash[n] = 2 * cy + lmmp_addshl1_n_(ash, a5, ash, n);
496
497 lmmp_debug_assert(as1[n] <= 5);
498 lmmp_debug_assert(asm1[n] <= 2);
499 lmmp_debug_assert(as2[n] <= 62);
500 lmmp_debug_assert(asm2[n] <= 41);
501 lmmp_debug_assert(ash[n] <= 62);
502
503#define v0 dst /* 2n */
504#define v1 (dst + 2 * n) /* 2n+1 */
505#define vinf (dst + 6 * n) /* s+t */
506#define v2 scratch /* 2n+1 */
507#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
508#define vh (scratch + 4 * n + 2) /* 2n+1 */
509#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
510#define scratch_out (scratch + 8 * n + 4) /* 2n+1 */
511 /* Total scratch need: 10*n+5 */
512
513 /* Must be in allocation order, as they overwrite one limb beyond
514 * 2n+1. */
515 lmmp_mul_n_(v2, as2, bs2, n + 1); /* v2, 2n+1 limbs */
516 lmmp_mul_n_(vm2, asm2, bsm2, n + 1); /* vm2, 2n+1 limbs */
517 lmmp_mul_n_(vh, ash, bsh, n + 1); /* vh, 2n+1 limbs */
518
519 /* vm1, 2n+1 limbs */
521 cy = 0;
522 if (asm1[n] == 1) {
523 cy = lmmp_add_n_(vm1 + n, vm1 + n, bsm1, n);
524 } else if (asm1[n] == 2) {
525 cy = lmmp_addshl1_n_(vm1 + n, vm1 + n, bsm1, n);
526 }
527 vm1[2 * n] = cy;
528
529 /* v1, 2n+1 limbs */
530 lmmp_mul_n_(v1, as1, bs1, n);
531 if (as1[n] == 1) {
532 cy = bs1[n] + lmmp_add_n_(v1 + n, v1 + n, bs1, n);
533 } else if (as1[n] == 2) {
534 cy = 2 * bs1[n] + lmmp_addshl1_n_(v1 + n, v1 + n, bs1, n);
535 } else if (as1[n] != 0) {
536 cy = as1[n] * bs1[n] + lmmp_addmul_1_(v1 + n, bs1, n, as1[n]);
537 } else
538 cy = 0;
539 if (bs1[n] != 0)
540 cy += lmmp_add_n_(v1 + n, v1 + n, as1, n);
541 v1[2 * n] = cy;
542
543 lmmp_mul_n_(v0, a0, b0, n); /* v0, 2n limbs */
544
545 /* vinf, s+t limbs */
546 if (s > t)
547 lmmp_mul_(vinf, a5, s, b1, t);
548 else
549 lmmp_mul_(vinf, b1, t, a5, s);
550
551 lmmp_toom_interp7_(dst, n, (enum toom7_flags)(aflags ^ bflags), vm2, vm1, v2, vh, s + t, scratch_out);
552
553#undef numb
554#undef n
555#undef s
556#undef t
557#undef scratch
558#undef tmp
559#undef bs1
560#undef bsm1
561#undef bs2
562#undef bsm2
563#undef bsh
564}
565
567 mp_ptr restrict dst,
568 mp_srcptr restrict numa,
569 mp_size_t na,
571 mp_size_t nb
572) {
573 lmmp_param_assert(na >= 5 * nb);
574 TEMP_DECL;
576
577 toom62_cache_t cache;
578 cache.numb = numb;
579 cache.n = 1 + (3 * nb - 1) / (mp_size_t)6;
580 cache.s = 3 * nb - 5 * cache.n;
581 cache.t = nb - cache.n;
582 cache.scratch = BALLOC_TYPE(20 * cache.n + 20, mp_limb_t);
583 cache.tmp = cache.scratch + 10 * cache.n + 10;
584 cache.bs1 = cache.tmp + 5 * cache.n + 5;
585 cache.bsm1 = cache.bs1 + cache.n + 1;
586 cache.bs2 = cache.bsm1 + cache.n;
587 cache.bsm2 = cache.bs2 + cache.n + 1;
588 cache.bsh = cache.bsm2 + cache.n + 1;
589
590 enum toom7_flags bflags = lmmp_mul_toom62_cache_init_(dst, numa, &cache);
591 dst += 3 * nb;
592 numa += 3 * nb;
593 na -= 3 * nb;
594 lmmp_copy(ws, dst, nb);
595 while (na >= 5 * nb) {
596 lmmp_mul_toom62_cache_(dst, numa, &cache, bflags);
597 if (lmmp_add_n_(dst, dst, ws, nb))
598 lmmp_inc(dst + nb);
599 dst += 3 * nb;
600 numa += 3 * nb;
601 na -= 3 * nb;
602 lmmp_copy(ws, dst, nb);
603 }
604 // 0 <= na < 2 nb
605 if (na >= nb)
606 lmmp_mul_(dst, numa, na, numb, nb);
607 else
608 lmmp_mul_(dst, numb, nb, numa, na);
609 if (lmmp_add_n_(dst, dst, ws, nb))
610 lmmp_inc(dst + nb);
611 TEMP_FREE;
612}
#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_VECT_CONSERVATIVE
定义 lmmp.h:201
#define lmmp_param_assert(x)
定义 lmmp.h:509
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]
#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_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
定义 shl.c:53
void lmmp_mul_toom62_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
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
mp_limb_t lmmp_add_n_sub_n_(mp_ptr dsta, mp_ptr dstb, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
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_mul_toom62_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
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
#define b0
#define b1
#define a0
#define a1
#define v0
#define bsm1
#define asm1
#define vinf
#define vm1
#define a2
#define v1
#define v2
#define t
#define a3
#define numb
#define s
#define n
#define bs1
#define bs2
#define as2
#define asm2
#define bsm2
#define as1
#define vm2
#define vh
#define a4
#define scratch_out
mp_srcptr restrict numb
mp_ptr restrict bsm1
static void lmmp_mul_toom62_cache_(mp_ptr restrict dst, mp_srcptr restrict numa, const toom62_cache_t *cache, enum toom7_flags bflags)
mp_ptr restrict bsm2
#define a5
#define scratch
mp_ptr restrict scratch
mp_ptr restrict tmp
mp_ptr restrict bsh
#define tmp
#define bsh
mp_ptr restrict bs1
mp_ptr restrict bs2
static enum toom7_flags lmmp_mul_toom62_cache_init_(mp_ptr restrict dst, mp_srcptr restrict numa, toom62_cache_t *cache)
int lmmp_toom_eval_pm2_(mp_ptr xp2, mp_ptr xm2, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, mp_ptr tp)
通用高阶 Toom 求值:k次多项式在 x = +2 和 x = -2 处求值
int lmmp_toom_eval_pm1_(mp_ptr xp1, mp_ptr xm1, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, mp_ptr tp)
通用高阶 Toom 求值:k次多项式在 x = +1 和 x = -1 处求值
void lmmp_toom_interp7_(mp_ptr dst, mp_size_t n, enum toom7_flags flags, mp_ptr w1, mp_ptr w3, mp_ptr w4, mp_ptr w5, mp_size_t w6n, mp_ptr tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_S_FREE
toom7_flags
@ toom7_w1_neg
@ toom7_w3_neg