LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom52.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
27#define lmmp_mul_n_(dst, numa, numb, n) \
28 if ((n) < MUL_TOOM22_THRESHOLD) \
29 lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
30 else if ((n) < MUL_TOOM33_THRESHOLD) \
31 lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
32 else if ((n) < MUL_TOOM44_THRESHOLD) \
33 lmmp_mul_toom33_((dst), (numa), (n), (numb), (n)); \
34 else \
35 lmmp_mul_toom44_((dst), (numa), (n), (numb), (n))
36
37/*
38Evaluate in: -2, -1, 0, +1, +2, +inf
39
40 <-s-><--n--><--n--><--n--><--n-->
41 |a4-|--a3--|--a2--|--a1--|--a0--|
42 |b1|--b0--|
43 <t-><--n-->
44
45 v0 = a0 * b0 # A(0)*B(0)
46 v1 = (a0+ a1+ a2+ a3+ a4)*(b0+ b1) # A(1)*B(1) ah <= 4 bh <= 1
47 vm1 = (a0- a1+ a2- a3+ a4)*(b0- b1) # A(-1)*B(-1) |ah| <= 2 bh = 0
48 v2 = (a0+2a1+4a2+8a3+16a4)*(b0+2b1) # A(2)*B(2) ah <= 30 bh <= 2
49 vm2 = (a0-2a1+4a2-8a3+16a4)*(b0-2b1) # A(-2)*B(-2) |ah| <= 20 |bh|<= 1
50 vinf= a4 * b1 # A(inf)*B(inf)
51
52 Some slight optimization in evaluation are taken from the paper:
53 "Towards Optimal Toom-Cook Multiplication for Univariate and
54 Multivariate Polynomials in Characteristic 2 and 0."
55*/
56
58 lmmp_param_assert(5 * nb > na);
59 lmmp_param_assert(na > 2 * nb);
60 mp_size_t n, s, t;
61 enum toom6_flags flags;
62
63#define a0 numa
64#define a1 (numa + n)
65#define a2 (numa + 2 * n)
66#define a3 (numa + 3 * n)
67#define a4 (numa + 4 * n)
68#define b0 numb
69#define b1 (numb + n)
70
71 n = 1 + (2 * na >= 5 * nb ? (na - 1) / (mp_size_t)5 : (nb - 1) >> 1);
74
75 s = na - 4 * n;
76 t = nb - n;
77
78 lmmp_param_assert(0 < s && s <= n);
79 lmmp_param_assert(0 < t && t <= n);
80
81 /* Ensures that 5 values of n+1 limbs each fits in the product area.
82 Borderline cases are na = 32, nb = 8, n = 7, and na = 36, bn = 9,
83 n = 8. */
84 lmmp_param_assert(s + t >= 5);
85
86#define v0 dst /* 2n */
87#define vm1 (scratch) /* 2n+1 */
88#define v1 (dst + 2 * n) /* 2n+1 */
89#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
90#define v2 (scratch + 4 * n + 2) /* 2n+1 */
91#define vinf (dst + 5 * n) /* s+t */
92#define bs1 dst /* n+1 */
93#define bsm1 (scratch + 2 * n + 2) /* n */
94#define asm1 (scratch + 3 * n + 3) /* n+1 */
95#define asm2 (scratch + 4 * n + 4) /* n+1 */
96#define bsm2 (dst + n + 1) /* n+1 */
97#define bs2 (dst + 2 * n + 2) /* n+1 */
98#define as2 (dst + 3 * n + 3) /* n+1 */
99#define as1 (dst + 4 * n + 4) /* n+1 */
100
101#define a0a2 scratch
102#define a1a3 asm1
103
104 /* Compute as2 and asm2. */
105 flags = (enum toom6_flags)(toom6_vm2_neg & lmmp_toom_eval_pm2_(as2, asm2, 4, numa, n, s, a1a3));
106
107 /* Compute bs1 and bsm1. */
108 if (t == n) {
109 mp_limb_t cy;
110 if (lmmp_cmp_(b0, b1, n) < 0) {
111 cy = lmmp_add_n_sub_n_(bs1, bsm1, b1, b0, n);
112 flags = (enum toom6_flags)(flags ^ toom6_vm1_neg);
113 } else {
114 cy = lmmp_add_n_sub_n_(bs1, bsm1, b0, b1, n);
115 }
116 bs1[n] = cy >> 1;
117 } else {
118 bs1[n] = lmmp_add_(bs1, b0, n, b1, t);
119 if (lmmp_zero_q_(b0 + t, n - t) && lmmp_cmp_(b0, b1, t) < 0) {
120 lmmp_sub_n_(bsm1, b1, b0, t);
121 lmmp_zero(bsm1 + t, n - t);
122 flags = (enum toom6_flags)(flags ^ toom6_vm1_neg);
123 } else {
124 lmmp_sub_(bsm1, b0, n, b1, t);
125 }
126 }
127
128 /* Compute bs2 and bsm2, recycling bs1 and bsm1. bs2=bs1+b1; bsm2=bsm1-b1 */
129 lmmp_add_(bs2, bs1, n + 1, b1, t);
130 if (flags & toom6_vm1_neg) {
131 bsm2[n] = lmmp_add_(bsm2, bsm1, n, b1, t);
132 flags = (enum toom6_flags)(flags ^ toom6_vm2_neg);
133 } else {
134 bsm2[n] = 0;
135 if (t == n) {
136 if (lmmp_cmp_(bsm1, b1, n) < 0) {
138 flags = (enum toom6_flags)(flags ^ toom6_vm2_neg);
139 } else {
141 }
142 } else {
143 if (lmmp_zero_q_(bsm1 + t, n - t) && lmmp_cmp_(bsm1, b1, t) < 0) {
145 lmmp_zero(bsm2 + t, n - t);
146 flags = (enum toom6_flags)(flags ^ toom6_vm2_neg);
147 } else {
148 lmmp_sub_(bsm2, bsm1, n, b1, t);
149 }
150 }
151 }
152
153 /* Compute as1 and asm1. */
154 flags = (enum toom6_flags)(flags ^ (toom6_vm1_neg & lmmp_toom_eval_pm1_(as1, asm1, 4, numa, n, s, a0a2)));
155
156 lmmp_debug_assert(as1[n] <= 4);
157 lmmp_debug_assert(bs1[n] <= 1);
158 lmmp_debug_assert(asm1[n] <= 2);
159 /* lmmp_debug_assert (bsm1[n] <= 1); */
160 lmmp_debug_assert(as2[n] <= 30);
161 lmmp_debug_assert(bs2[n] <= 2);
162 lmmp_debug_assert(asm2[n] <= 20);
163 lmmp_debug_assert(bsm2[n] <= 1);
164
165 /* vm1, 2n+1 limbs */
166 lmmp_mul_(vm1, asm1, n + 1, bsm1, n); /* W4 */
167
168 /* vm2, 2n+1 limbs */
169 lmmp_mul_n_(vm2, asm2, bsm2, n + 1); /* W2 */
170
171 /* v2, 2n+1 limbs */
172 lmmp_mul_n_(v2, as2, bs2, n + 1); /* W1 */
173
174 /* v1, 2n+1 limbs */
175 lmmp_mul_n_(v1, as1, bs1, n + 1); /* W3 */
176
177 /* vinf, s+t limbs */ /* W0 */
178 if (s > t)
179 lmmp_mul_(vinf, a4, s, b1, t);
180 else
181 lmmp_mul_(vinf, b1, t, a4, s);
182
183 /* v0, 2n limbs */
184 lmmp_mul_n_(v0, numa, numb, n); /* W5 */
185
186 lmmp_toom_interp6_(dst, n, flags, vm1, vm2, v2, t + s);
188#undef v0
189#undef vm1
190#undef v1
191#undef vm2
192#undef v2
193#undef vinf
194#undef bs1
195#undef bs2
196#undef bsm1
197#undef bsm2
198#undef asm1
199#undef asm2
200#undef as1
201#undef as2
202#undef a0a2
203#undef b0b2
204#undef a1a3
205#undef a0
206#undef a1
207#undef a2
208#undef a3
209#undef b0
210#undef b1
211#undef b2
212}
#define lmmp_mul_n_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#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
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_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]
void lmmp_mul_toom52_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-52乘法运算 [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
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_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
#define b0
#define b1
#define v0
#define bsm1
#define asm1
#define vinf
#define vm1
#define v1
#define v2
#define t
#define numb
#define s
#define n
#define bs1
#define bs2
#define as2
#define asm2
#define bsm2
#define a0a2
#define as1
#define a1a3
#define vm2
#define a4
#define scratch
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_interp6_(mp_ptr dst, mp_size_t n, enum toom6_flags flags, mp_ptr w4, mp_ptr w2, mp_ptr w1, mp_size_t w0n)
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
toom6_flags
Copyright (C) 2026 HJimmyK (Jericho Knox)
@ toom6_vm2_neg
@ toom6_vm1_neg