LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom42.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#include "lmmp/lmmpn.h"
27
29
30
31#define lmmp_mul_n_(dst, numa, numb, n) \
32 if ((n) < MUL_TOOM22_THRESHOLD) \
33 lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
34 else if ((n) < MUL_TOOM33_THRESHOLD) \
35 lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
36 else \
37 lmmp_mul_toom33_((dst), (numa), (n), (numb), (n))
38
39/*
40Evaluate in: -1, 0, +1, +2, +inf
41
42 <-s-><--n--><--n--><--n-->
43 |a3-|---a2-|---a1-|---a0-|
44 |-b1-|---b0-|
45 <-t--><--n-->
46
47v0 = a0 * b0 # A(0)*B(0)
48v1 = (a0+ a1+ a2+ a3)*(b0+ b1) # A(1)*B(1) ah <= 3 bh <= 1
49vm1 = (a0- a1+ a2- a3)*(b0- b1) # A(-1)*B(-1) |ah| <= 1 bh = 0
50v2 = (a0+2a1+4a2+8a3)*(b0+2b1) # A(2)*B(2) ah <= 14 bh <= 2
51vinf= a3 * b1 # A(inf)*B(inf)
52*/
53
55 lmmp_param_assert(nb >= 20);
56 lmmp_param_assert(4 * nb > na);
57 lmmp_param_assert(3 * na > 2 * nb);
59 mp_size_t n = na >= 2 * nb ? (na + 3) >> 2 : (nb + 1) >> 1, s = na - 3 * n, t = nb - n;
62 int vm1_neg;
63 mp_limb_t cy, vinf0, am1h;
65
66#define a0 numa
67#define a1 (numa + n)
68#define a2 (numa + 2 * n)
69#define a3 (numa + 3 * n)
70#define b0 numb
71#define b1 (numb + n)
72
73#define v0 dst //[dst,2*n]
74#define v1 (dst + 2 * n) //[dst+2*n,2*n+1]
75#define vinf (dst + 4 * n) //[dst+4*n,s+t]
76#define vm1 tp //[tp,2*n+1]
77#define v2 (tp + 2 * n + 2) //[tp+2*n+2,2*n+1]
78
79#define bm1 dst //[dst,n]
80#define am1 (dst + n) //[dst+n,n+1]
81#define ap1 tp //[tp,n+1]
82#define bp1 (tp + n + 1) //[tp+n+1,n+1]
83#define ap2 ap1 // same space
84#define bp2 bp1 // same space
85#define a13 bp1 // temporary use
86
87 // ap1,am1
88 ap1[n] = lmmp_add_n_(ap1, a0, a2, n);
89 a13[n] = lmmp_add_(a13, a1, n, a3, s);
90 vm1_neg = lmmp_cmp_(ap1, a13, n + 1) < 0;
91 if (vm1_neg)
93 else
95 am1h = am1[n]; // overlap with v1
96
97 // bp1,bm1
98 if (t == n) {
99 if (lmmp_cmp_(b0, b1, n) < 0) {
100 bp1[n] = lmmp_add_n_sub_n_(bp1, bm1, b1, b0, n) >> 1;
101 vm1_neg ^= 1;
102 } else {
103 bp1[n] = lmmp_add_n_sub_n_(bp1, bm1, b0, b1, n) >> 1;
104 }
105 } else {
106 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
107 cy = lmmp_add_n_sub_n_(bp1, bm1, b1, b0, t);
108 lmmp_zero(bm1 + t, n - t);
109 vm1_neg ^= 1;
110 } else {
111 cy = lmmp_add_n_sub_n_(bp1, bm1, b0, b1, t);
112 lmmp_sub_1_(bm1 + t, b0 + t, n - t, cy & 1);
113 }
114 bp1[n] = lmmp_add_1_(bp1 + t, b0 + t, n - t, cy >> 1);
115 }
116
117 // vinf=a3*b1
118 if (s > t)
119 lmmp_mul_(vinf, a3, s, b1, t);
120 else
121 lmmp_mul_(vinf, b1, t, a3, s);
122 vinf0 = vinf[0]; // overlap with v1
123 cy = vinf[1]; // overlap with v1
124
125 // v1=ap1*bp1
126 lmmp_mul_n_(v1, ap1, bp1, n + 1);
127 vinf[1] = cy; // restore, since v1[2*n+1]==0.
128
129 // ap2
130 cy = lmmp_addshl1_n_(ap2, a2, a3, s);
131 if (s != n)
132 cy = lmmp_add_1_(ap2 + s, a2 + s, n - s, cy);
133 cy = 2 * cy + lmmp_addshl1_n_(ap2, a1, ap2, n);
134 cy = 2 * cy + lmmp_addshl1_n_(ap2, a0, ap2, n);
135 ap2[n] = cy;
136
137 // bp2=bp1+b1
138 lmmp_add_(bp2, bp1, n + 1, b1, t);
139
140 // v2=ap2*bp2
141 lmmp_mul_n_(v2, ap2, bp2, n + 1);
142
143 // vm1=am1*bm1
144 lmmp_mul_n_(vm1, am1, bm1, n);
145 if (am1h)
146 vm1[2 * n] = lmmp_add_n_(vm1 + n, vm1 + n, bm1, n);
147 else
148 vm1[2 * n] = 0;
149
150 // v0=a0*b0
151 lmmp_mul_n_(v0, a0, b0, n);
152
153 lmmp_toom_interp5_(dst, v2, vm1, n, s + t, vm1_neg, vinf0);
155#undef a0
156#undef a1
157#undef a2
158#undef a3
159#undef b0
160#undef b1
161
162#undef v0
163#undef v1
164#undef vinf
165#undef vm1
166#undef v2
167
168#undef bm1
169#undef am1
170#undef ap1
171#undef bp1
172#undef ap2
173#undef bp2
174#undef a13
175}
176
186
188 mp_ptr restrict dst,
189 mp_srcptr restrict numa,
190 toom42_cache_t* cache
191) {
192#define numb (cache->numb)
193#define n (cache->n)
194#define s (cache->s)
195#define t (cache->t)
196#define _bp1 (cache->_bp1)
197#define _bm1 (cache->_bm1)
198#define tp (cache->tp)
199
200 int vm1_neg, flag = 0;
201 mp_limb_t cy, vinf0, am1h;
202
203#define a0 numa
204#define a1 (numa + n)
205#define a2 (numa + 2 * n)
206#define a3 (numa + 3 * n)
207#define b0 numb
208#define b1 (numb + n)
209
210#define v0 dst //[dst,2*n]
211#define v1 (dst + 2 * n) //[dst+2*n,2*n+1]
212#define vinf (dst + 4 * n) //[dst+4*n,s+t]
213#define vm1 tp //[tp,2*n+1]
214#define v2 (tp + 2 * n + 2) //[tp+2*n+2,2*n+1]
215
216#define bm1 _bm1 //[dst,n]
217#define am1 (dst + n) //[dst+n,n+1]
218#define ap1 tp //[tp,n+1]
219#define bp1 _bp1 //[TH._bp1,n+1]
220#define ap2 ap1 // same space
221#define bp2 (tp + n + 1) //[tp+n+1,n+1]
222#define a13 (tp + n + 1) // same space
223
224 // ap1,am1
225 ap1[n] = lmmp_add_n_(ap1, a0, a2, n);
226 a13[n] = lmmp_add_(a13, a1, n, a3, s);
227 vm1_neg = lmmp_cmp_(ap1, a13, n + 1) < 0;
228 if (vm1_neg)
229 lmmp_add_n_sub_n_(ap1, am1, a13, ap1, n + 1);
230 else
231 lmmp_add_n_sub_n_(ap1, am1, ap1, a13, n + 1);
232 am1h = am1[n]; // overlap with v1
233
234 if (t == n) {
235 if (lmmp_cmp_(b0, b1, n) < 0) {
236 bp1[n] = lmmp_add_n_sub_n_(bp1, bm1, b1, b0, n) >> 1;
237 vm1_neg ^= 1;
238 flag = 1;
239 } else {
240 bp1[n] = lmmp_add_n_sub_n_(bp1, bm1, b0, b1, n) >> 1;
241 }
242 } else {
243 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
244 cy = lmmp_add_n_sub_n_(bp1, bm1, b1, b0, t);
245 lmmp_zero(bm1 + t, n - t);
246 vm1_neg ^= 1;
247 flag = 1;
248 } else {
249 cy = lmmp_add_n_sub_n_(bp1, bm1, b0, b1, t);
250 lmmp_sub_1_(bm1 + t, b0 + t, n - t, cy & 1);
251 }
252 bp1[n] = lmmp_add_1_(bp1 + t, b0 + t, n - t, cy >> 1);
253 }
254
255 // vinf=a3*b1
256 if (s > t)
257 lmmp_mul_(vinf, a3, s, b1, t);
258 else
259 lmmp_mul_(vinf, b1, t, a3, s);
260 vinf0 = vinf[0]; // overlap with v1
261 cy = vinf[1]; // overlap with v1
262
263 // v1=ap1*bp1
264 lmmp_mul_n_(v1, ap1, bp1, n + 1);
265 vinf[1] = cy; // restore, since v1[2*n+1]==0.
266
267 // ap2
268 cy = lmmp_addshl1_n_(ap2, a2, a3, s);
269 if (s != n)
270 cy = lmmp_add_1_(ap2 + s, a2 + s, n - s, cy);
271 cy = 2 * cy + lmmp_addshl1_n_(ap2, a1, ap2, n);
272 cy = 2 * cy + lmmp_addshl1_n_(ap2, a0, ap2, n);
273 ap2[n] = cy;
274
275 // bp2=bp1+b1
276 lmmp_add_(bp2, bp1, n + 1, b1, t);
277
278 // v2=ap2*bp2
279 lmmp_mul_n_(v2, ap2, bp2, n + 1);
280
281 // vm1=am1*bm1
282 lmmp_mul_n_(vm1, am1, bm1, n);
283 if (am1h)
284 vm1[2 * n] = lmmp_add_n_(vm1 + n, vm1 + n, bm1, n);
285 else
286 vm1[2 * n] = 0;
287
288 // v0=a0*b0
289 lmmp_mul_n_(v0, a0, b0, n);
290
291 lmmp_toom_interp5_(dst, v2, vm1, n, s + t, vm1_neg, vinf0);
292 return flag;
293#undef a0
294#undef a1
295#undef a2
296#undef a3
297#undef b0
298#undef b1
299
300#undef v0
301#undef v1
302#undef vinf
303#undef vm1
304#undef v2
305
306#undef bm1
307#undef am1
308#undef ap1
309#undef bp1
310#undef ap2
311#undef bp2
312#undef a13
313
314#undef numb
315#undef n
316#undef s
317#undef t
318#undef _bp1
319#undef _bm1
320#undef tp
321}
322
324 mp_ptr restrict dst,
325 mp_srcptr restrict numa,
326 const toom42_cache_t* cache,
327 int flag
328) {
329#define numb (cache->numb)
330#define n (cache->n)
331#define s (cache->s)
332#define t (cache->t)
333#define _bp1 (cache->_bp1)
334#define _bm1 (cache->_bm1)
335#define tp (cache->tp)
336
337 int vm1_neg;
338 mp_limb_t cy, vinf0, am1h;
339
340#define a0 numa
341#define a1 (numa + n)
342#define a2 (numa + 2 * n)
343#define a3 (numa + 3 * n)
344#define b0 numb
345#define b1 (numb + n)
346
347#define v0 dst //[dst,2*n]
348#define v1 (dst + 2 * n) //[dst+2*n,2*n+1]
349#define vinf (dst + 4 * n) //[dst+4*n,s+t]
350#define vm1 tp //[tp,2*n+1]
351#define v2 (tp + 2 * n + 2) //[tp+2*n+2,2*n+1]
352
353#define bm1 _bm1 //[dst,n]
354#define am1 (dst + n) //[dst+n,n+1]
355#define ap1 tp //[tp,n+1]
356#define bp1 _bp1 //[TH._bp1,n+1]
357#define ap2 ap1 // same space
358#define bp2 (tp + n + 1) //[tp+n+1,n+1]
359#define a13 (tp + n + 1) // same space
360
361 // ap1,am1
362 ap1[n] = lmmp_add_n_(ap1, a0, a2, n);
363 a13[n] = lmmp_add_(a13, a1, n, a3, s);
364 vm1_neg = lmmp_cmp_(ap1, a13, n + 1) < 0;
365 if (vm1_neg)
366 lmmp_add_n_sub_n_(ap1, am1, a13, ap1, n + 1);
367 else
368 lmmp_add_n_sub_n_(ap1, am1, ap1, a13, n + 1);
369 am1h = am1[n]; // overlap with v1
370
371 if (flag)
372 vm1_neg ^= 1;
373
374 // vinf=a3*b1
375 if (s > t)
376 lmmp_mul_(vinf, a3, s, b1, t);
377 else
378 lmmp_mul_(vinf, b1, t, a3, s);
379 vinf0 = vinf[0]; // overlap with v1
380 cy = vinf[1]; // overlap with v1
381
382 // v1=ap1*bp1
383 lmmp_mul_n_(v1, ap1, bp1, n + 1);
384 vinf[1] = cy; // restore, since v1[2*n+1]==0.
385
386 // ap2
387 cy = lmmp_addshl1_n_(ap2, a2, a3, s);
388 if (s != n)
389 cy = lmmp_add_1_(ap2 + s, a2 + s, n - s, cy);
390 cy = 2 * cy + lmmp_addshl1_n_(ap2, a1, ap2, n);
391 cy = 2 * cy + lmmp_addshl1_n_(ap2, a0, ap2, n);
392 ap2[n] = cy;
393
394 // bp2=bp1+b1
395 lmmp_add_(bp2, bp1, n + 1, b1, t);
396
397 // v2=ap2*bp2
398 lmmp_mul_n_(v2, ap2, bp2, n + 1);
399
400 // vm1=am1*bm1
401 lmmp_mul_n_(vm1, am1, bm1, n);
402 if (am1h)
403 vm1[2 * n] = lmmp_add_n_(vm1 + n, vm1 + n, bm1, n);
404 else
405 vm1[2 * n] = 0;
406
407 // v0=a0*b0
408 lmmp_mul_n_(v0, a0, b0, n);
409
410 lmmp_toom_interp5_(dst, v2, vm1, n, s + t, vm1_neg, vinf0);
411
412#undef numb
413#undef n
414#undef s
415#undef t
416#undef _bp1
417#undef _bm1
418#undef tp
419}
420
422 mp_ptr restrict dst,
423 mp_srcptr restrict numa,
424 mp_size_t na,
426 mp_size_t nb
427) {
428 lmmp_param_assert(na >= 3 * nb);
429 lmmp_param_assert(nb >= 20);
432
433 toom42_cache_t cache;
434 cache.numb = numb;
435 cache.n = (2 * nb + 3) >> 2;
436 cache.s = 2 * nb - 3 * cache.n;
437 cache.t = nb - cache.n;
438 cache.tp = SALLOC_TYPE(4 * cache.n + 4, mp_limb_t);
439 cache._bp1 = SALLOC_TYPE(2 * cache.n + 1, mp_limb_t);
440 cache._bm1 = cache._bp1 + cache.n + 1;
441
442 int flag = lmmp_mul_toom42_cache_init_(dst, numa, &cache);
443 dst += 2 * nb;
444 numa += 2 * nb;
445 na -= 2 * nb;
446 lmmp_copy(ws, dst, nb);
447 while (2 * na >= 5 * nb) {
448 lmmp_mul_toom42_cache_(dst, numa, &cache, flag);
449 if (lmmp_add_n_(dst, dst, ws, nb))
450 lmmp_inc(dst + nb);
451 dst += 2 * nb;
452 numa += 2 * nb;
453 na -= 2 * nb;
454 lmmp_copy(ws, dst, nb);
455 }
456 // 0.5 nb <= na < 2.5 nb
457 if (na >= nb)
458 lmmp_mul_(dst, numa, na, numb, nb);
459 else
460 lmmp_mul_(dst, numb, nb, numa, na);
461 if (lmmp_add_n_(dst, dst, ws, nb))
462 lmmp_inc(dst + nb);
464}
#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
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]
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
void lmmp_mul_toom42_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-42乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_toom42_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-42不平衡乘法运算 [dst,na+nb] = [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
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_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])
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
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 vinf
#define am1
#define ap1
#define bp1
#define vm1
#define bm1
#define a2
#define v1
#define ap2
#define v2
#define bp2
#define t
mp_ptr restrict tp
#define a3
#define numb
static void lmmp_mul_toom42_cache_(mp_ptr restrict dst, mp_srcptr restrict numa, const toom42_cache_t *cache, int flag)
static int lmmp_mul_toom42_cache_init_(mp_ptr restrict dst, mp_srcptr restrict numa, toom42_cache_t *cache)
#define a13
mp_srcptr restrict numb
mp_ptr restrict _bp1
mp_ptr restrict _bm1
#define tp
#define s
#define n
void lmmp_toom_interp5_(mp_ptr dst, mp_ptr v2, mp_ptr vm1, mp_size_t n, mp_size_t spt, int vm1_neg, mp_limb_t vinf0)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TEMP_S_FREE