LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom_eval.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 "lmmpn/toom_interp.h"
24
26
27
29 int neg;
30 lmmp_param_assert(x3n > 0);
31 lmmp_param_assert(x3n <= n);
32
33 xp1[n] = lmmp_add_n_(xp1, xp, xp + 2 * n, n);
34 tp[n] = lmmp_add_(tp, xp + n, n, xp + 3 * n, x3n);
35
36 neg = (lmmp_cmp_(xp1, tp, n + 1) < 0) ? ~0 : 0;
37 if (neg)
38 lmmp_add_n_sub_n_(xp1, xm1, tp, xp1, n + 1);
39 else
40 lmmp_add_n_sub_n_(xp1, xm1, xp1, tp, n + 1);
41
42 lmmp_debug_assert(xp1[n] <= 3);
43 lmmp_debug_assert(xm1[n] <= 1);
44
45 return neg;
46}
47
49 mp_limb_t cy;
50 int neg;
51 lmmp_param_assert(x3n > 0);
52 lmmp_param_assert(x3n <= n);
53 /* (x0 + 4 * x2) +/- (2 x1 + 8 x_3) */
54
55 cy = lmmp_shl_(tp, xp + 2 * n, n, 2);
56 xp2[n] = cy + lmmp_add_n_(xp2, tp, xp, n);
57
58 tp[x3n] = lmmp_shl_(tp, xp + 3 * n, x3n, 2);
59 if (x3n < n)
60 tp[n] = lmmp_add_(tp, xp + n, n, tp, x3n + 1);
61 else
62 tp[n] += lmmp_add_n_(tp, xp + n, tp, n);
63
64 lmmp_shl_(tp, tp, n + 1, 1);
65
66 neg = (lmmp_cmp_(xp2, tp, n + 1) < 0) ? ~0 : 0;
67
68 if (neg)
69 lmmp_add_n_sub_n_(xp2, xm2, tp, xp2, n + 1);
70 else
71 lmmp_add_n_sub_n_(xp2, xm2, xp2, tp, n + 1);
72
73 lmmp_debug_assert(xp2[n] < 15);
74 lmmp_debug_assert(xm2[n] < 10);
75
76 return neg;
77}
78
80 unsigned i;
81 int neg;
82 lmmp_param_assert(k >= 4);
83
84 lmmp_param_assert(hn > 0);
85 lmmp_param_assert(hn <= n);
86
87 /* The degree k is also the number of full-size coefficients, so
88 * that last coefficient, of size hn, starts at xp + k*n. */
89
90 xp1[n] = lmmp_add_n_(xp1, xp, xp + 2 * n, n);
91 for (i = 4; i < k; i += 2) lmmp_add_(xp1, xp1, n + 1, xp + i * n, n);
92
93 tp[n] = lmmp_add_n_(tp, xp + n, xp + 3 * n, n);
94 for (i = 5; i < k; i += 2) lmmp_add_(tp, tp, n + 1, xp + i * n, n);
95
96 if (k & 1)
97 lmmp_add_(tp, tp, n + 1, xp + k * n, hn);
98 else
99 lmmp_add_(xp1, xp1, n + 1, xp + k * n, hn);
100
101 neg = (lmmp_cmp_(xp1, tp, n + 1) < 0) ? ~0 : 0;
102
103 if (neg)
104 lmmp_add_n_sub_n_(xp1, xm1, tp, xp1, n + 1);
105 else
106 lmmp_add_n_sub_n_(xp1, xm1, xp1, tp, n + 1);
107
108 lmmp_debug_assert(xp1[n] <= k);
109 lmmp_debug_assert(xm1[n] <= k / 2 + 1);
110
111 return neg;
112}
113
114/* DO_addlsh2(d,a,b,n,cy) computes cy,[d,n] <= [a,n] + 4*(cy,[b,n]), it
115 can be used as DO_addlsh2(d,a,d,n,d[n]), for accumulation on [d,n+1]. */
116
117/* The following is not a general substitute for addlsh2.
118 It is correct if d == b, but it is not if d == a. */
119#define DO_addlsh2(d, a, b, n, cy) \
120 do { \
121 (cy) <<= 2; \
122 (cy) += lmmp_shl_(d, b, n, 2); \
123 (cy) += lmmp_add_n_(d, d, a, n); \
124 } while (0)
125
127 int i;
128 int neg;
129 mp_limb_t cy;
130 lmmp_param_assert(k >= 3);
132
133 lmmp_param_assert(hn > 0);
134 lmmp_param_assert(hn <= n);
135
136 /* The degree k is also the number of full-size coefficients, so
137 * that last coefficient, of size hn, starts at xp + k*n. */
138
139 cy = 0;
140 DO_addlsh2(xp2, xp + (k - 2) * n, xp + k * n, hn, cy);
141 if (hn != n)
142 cy = lmmp_add_1_(xp2 + hn, xp + (k - 2) * n + hn, n - hn, cy);
143 for (i = k - 4; i >= 0; i -= 2) DO_addlsh2(xp2, xp + i * n, xp2, n, cy);
144 xp2[n] = cy;
145
146 k--;
147
148 cy = 0;
149 DO_addlsh2(tp, xp + (k - 2) * n, xp + k * n, n, cy);
150 for (i = k - 4; i >= 0; i -= 2) DO_addlsh2(tp, xp + i * n, tp, n, cy);
151 tp[n] = cy;
152
153 if (k & 1)
154 lmmp_shl_(tp, tp, n + 1, 1);
155 else
156 lmmp_shl_(xp2, xp2, n + 1, 1);
157
158 neg = (lmmp_cmp_(xp2, tp, n + 1) < 0) ? ~0 : 0;
159
160 if (neg)
161 lmmp_add_n_sub_n_(xp2, xm2, tp, xp2, n + 1);
162 else
163 lmmp_add_n_sub_n_(xp2, xm2, xp2, tp, n + 1);
164
165 lmmp_debug_assert(xp2[n] < (1ull << (k + 2)) - 1);
166 lmmp_debug_assert(xm2[n] < ((1 << (k + 3)) - 1 - (1 ^ (k & 1))) / 3);
167
168 neg ^= ((k & 1) - 1);
169
170 return neg;
171}
172
173#undef DO_addlsh2
174
175int lmmp_toom_eval_pm2exp_(mp_ptr xp2, mp_ptr xm2, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, unsigned shift, mp_ptr tp) {
176 unsigned i;
177 int neg;
178 mp_limb_t cy;
179
180 lmmp_param_assert(k >= 3);
181 lmmp_param_assert(k * shift < LIMB_BITS);
182 lmmp_param_assert(hn > 0);
183 lmmp_param_assert(hn <= n);
184
185 /* k 次多项式(k 个完整段 + hn 长尾段)在 x = ±2^shift 处求值:
186 * 偶下标系数和进 xp2(k 偶时含尾段),奇下标进 tp(k 奇时含尾段),
187 * 点值和/差经 add_n_sub_n 一次分离,返回差半边的符号。 */
188
189 lmmp_copy(xp2, xp, n);
190 xp2[n] = 0;
191 for (i = 2; i < k; i += 2)
192 xp2[n] += lmmp_addmul_1_(xp2, xp + i * n, n, (mp_limb_t)1 << (i * shift));
193 if ((k & 1) == 0) {
194 cy = lmmp_addmul_1_(xp2, xp + k * n, hn, (mp_limb_t)1 << (k * shift));
195 lmmp_inc_1(xp2 + hn, cy);
196 }
197
198 tp[n] = lmmp_shl_(tp, xp + n, n, shift);
199 for (i = 3; i < k; i += 2)
200 tp[n] += lmmp_addmul_1_(tp, xp + i * n, n, (mp_limb_t)1 << (i * shift));
201 if (k & 1) {
202 cy = lmmp_addmul_1_(tp, xp + k * n, hn, (mp_limb_t)1 << (k * shift));
203 lmmp_inc_1(tp + hn, cy);
204 }
205
206 neg = (lmmp_cmp_(xp2, tp, n + 1) < 0) ? ~0 : 0;
207
208 if (neg)
209 lmmp_add_n_sub_n_(xp2, xm2, tp, xp2, n + 1);
210 else
211 lmmp_add_n_sub_n_(xp2, xm2, xp2, tp, n + 1);
212
213 return neg;
214}
215
216int lmmp_toom_eval_pm2rexp_(mp_ptr rp, mp_ptr rm, unsigned q, mp_srcptr ap, mp_size_t n, mp_size_t t, unsigned s, mp_ptr ws) {
217 unsigned i;
218 int neg;
219 mp_limb_t cy;
220
222 lmmp_param_assert(t > 0);
223 lmmp_param_assert(s != 0); /* s==0 时应改用 eval_pm1 */
224 lmmp_param_assert(q > 1);
226
227 /* q 次多项式(q 个完整段 + t 长尾段)在 x = ±1/2^s 处求值,结果放大
228 * 2^(s*q):第 i 段权重 2^(s*(q-i)),即倒序多项式在 2^s 处的点值。
229 * 偶下标和进 rp(q 偶时含尾段),奇下标进 ws(q 奇时含尾段)。 */
230
231 rp[n] = lmmp_shl_(rp, ap, n, s * q);
232 ws[n] = lmmp_shl_(ws, ap + n, n, s * (q - 1));
233 if (q & 1) {
234 cy = lmmp_add_(ws, ws, n + 1, ap + n * q, t);
235 lmmp_debug_assert(cy == 0);
236 rp[n] += lmmp_addmul_1_(rp, ap + n * (q - 1), n, (mp_limb_t)1 << s);
237 } else {
238 cy = lmmp_add_(rp, rp, n + 1, ap + n * q, t);
239 lmmp_debug_assert(cy == 0);
240 }
241 for (i = 2; i + 1 < q; i += 2) {
242 rp[n] += lmmp_addmul_1_(rp, ap + n * i, n, (mp_limb_t)1 << (s * (q - i)));
243 ws[n] += lmmp_addmul_1_(ws, ap + n * (i + 1), n, (mp_limb_t)1 << (s * (q - i - 1)));
244 }
245
246 neg = (lmmp_cmp_(rp, ws, n + 1) < 0) ? ~0 : 0;
247
248 if (neg)
249 lmmp_add_n_sub_n_(rp, rm, ws, rp, n + 1);
250 else
251 lmmp_add_n_sub_n_(rp, rm, rp, ws, n + 1);
252
253 return neg;
254}
#define k
#define rp
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
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 LIMB_BITS
定义 lmmp.h:102
#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
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
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
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])
#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 xp
#define t
#define tp
#define s
#define n
int lmmp_toom_eval_pm2exp_(mp_ptr xp2, mp_ptr xm2, unsigned k, mp_srcptr xp, mp_size_t n, mp_size_t hn, unsigned shift, mp_ptr tp)
通用高阶 Toom 求值:k次多项式在 x = +2^shift 和 x = -2^shift 处求值 (toom6h 的 ±4 / toom8h 的 ±4、±8 点)
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 处求值
LMMP_VECT_CONSERVATIVE int lmmp_toom_eval_dgr3_pm1_(mp_ptr xp1, mp_ptr xm1, mp_srcptr xp, mp_size_t n, mp_size_t x3n, mp_ptr tp)
Copyright (C) 2026 HJimmyK (Jericho Knox)
int lmmp_toom_eval_pm2rexp_(mp_ptr rp, mp_ptr rm, unsigned q, mp_srcptr ap, mp_size_t n, mp_size_t t, unsigned s, mp_ptr ws)
通用高阶 Toom 求值:q次多项式在 x = +1/2^s 和 x = -1/2^s 处求值, 结果放大 2^(s*q)(toom6h 的 ±1/2、±1/4 / toom8h 的 ±1/2、±1/4...
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 处求值
int lmmp_toom_eval_dgr3_pm2_(mp_ptr xp2, mp_ptr xm2, mp_srcptr xp, mp_size_t n, mp_size_t x3n, mp_ptr tp)
Toom-3 专用:3次多项式在 x = +2 和 x = -2 处求值 计算 P(+2) 和 P(-2),其中 P(x) 是一个3次多项式(4段系数)。
#define DO_addlsh2(d, a, b, n, cy)