LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom6h.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
28/* MAYBE_*:编译期常量折叠裁剪递归阶梯 */
29#define MAYBE_mul_basecase (MUL_TOOM6H_THRESHOLD < 6 * MUL_TOOM22_THRESHOLD)
30#define MAYBE_mul_toom22 (MUL_TOOM6H_THRESHOLD < 6 * MUL_TOOM33_THRESHOLD)
31#define MAYBE_mul_toom33 (MUL_TOOM6H_THRESHOLD < 6 * MUL_TOOM44_THRESHOLD)
32#define MAYBE_mul_toom6h (MUL_FFT_THRESHOLD >= 6 * MUL_TOOM6H_THRESHOLD)
33
34#define lmmp_mul_n_(dst, numa, numb, n) \
35 if (MAYBE_mul_basecase && (n) < MUL_TOOM22_THRESHOLD) \
36 lmmp_mul_hard_n_((dst), (numa), (numb), (n)); \
37 else if (MAYBE_mul_toom22 && (n) < MUL_TOOM33_THRESHOLD) \
38 lmmp_mul_toom22_((dst), (numa), (n), (numb), (n)); \
39 else if (MAYBE_mul_toom33 && (n) < MUL_TOOM44_THRESHOLD) \
40 lmmp_mul_toom33_((dst), (numa), (n), (numb), (n)); \
41 else if (!MAYBE_mul_toom6h || (n) < MUL_TOOM6H_THRESHOLD) \
42 lmmp_mul_toom44_((dst), (numa), (n), (numb), (n)); \
43 else \
44 lmmp_mul_toom6h_((dst), (numa), (n), (numb), (n))
45
46/*
47Evaluate in: infinity, +4, -4, +2, -2, +1, -1, +1/2, -1/2, +1/4, -1/4, 0
48
49 <-s-><---n---><---n---><---n---><--n-1--> ... (p 段)
50 |a_p|---a_p-1-|---...---|---a1---|---a0---|
51 |b_q|--...----|---b1---|---b0---| (q 段, q <= p)
52
53 v(0) = a0*b0
54 v(±1) = A(±1)*B(±1) |A(±1)| <= p
55 v(±2) = A(±2)*B(±2) 2^k 求值约束: 2*k_max < LIMB_BITS
56 v(±4) = A(±4)*B(±4)
57 v(±1/2)= A(±1/2)*B(±1/2)*2^k
58 v(±1/4)= A(±1/4)*B(±1/4)*4^k
59 v(inf) = a_top*b_top(仅 half,走 lmmp_mul_ 完整分派)
60*/
61
63 lmmp_param_assert(na >= nb);
64 lmmp_param_assert(nb >= 46);
65 lmmp_param_assert(6 * na < 17 * nb);
66 mp_size_t n, s, t;
67 int p, q, half;
68 int sign;
69
70 /* LIMIT = 18/17:介于 (12/11)^(log4/log7) 与 (12/11)^(log6/log11)
71 之间的有理逼近,控制近似平衡切分的判定边界(比例 < 18/17) */
72#define LIMIT_num (18)
73#define LIMIT_den (17)
74
75 if (na * LIMIT_den < LIMIT_num * nb) {
76 /* 近似平衡:双侧各切 5 段 */
77 n = 1 + (na - 1) / 6;
78 p = q = 5;
79 half = 0;
80 s = na - 5 * n;
81 t = nb - 5 * n;
82 } else {
83 /* 不平衡阶梯:(p,q) 随比例增大,短侧段数下降 */
84 if (na * 5 * LIMIT_num < LIMIT_den * 7 * nb) {
85 p = 7;
86 q = 6;
87 } else if (na * 5 * LIMIT_den < LIMIT_num * 7 * nb) {
88 p = 7;
89 q = 5;
90 } else if (na * LIMIT_num < LIMIT_den * 2 * nb) {
91 p = 8;
92 q = 5;
93 } else if (na * LIMIT_den < LIMIT_num * 2 * nb) {
94 p = 8;
95 q = 4;
96 } else {
97 p = 9;
98 q = 4;
99 }
100
101 half = (p ^ q) & 1;
102 n = 1 + (q * na >= p * nb ? (na - 1) / p : (nb - 1) / q);
103 p--;
104 q--;
105
106 s = na - p * n;
107 t = nb - q * n;
108
109 /* 恢复不良切分:段长必须保证 s,t > 0(LIMIT=18/17 时仅 nb<=73 触发)。
110 mp_size_t 无符号,s/t 为负时回绕,须按 na<=p*n / nb<=q*n 判定 */
111 if (half) {
112 if (na <= (mp_size_t)p * n) {
113 p--;
114 s += n;
115 half = 0;
116 } else if (nb <= (mp_size_t)q * n) {
117 q--;
118 t += n;
119 half = 0;
120 }
121 }
122 }
123#undef LIMIT_num
124#undef LIMIT_den
125
126 lmmp_debug_assert(0 < s && s <= n);
127 lmmp_debug_assert(0 < t && t <= n);
128 lmmp_debug_assert(s + t + 3 * (mp_size_t)half > 3);
129 lmmp_debug_assert(n > 2);
130
131#define r4 (dst + 3 * n) /* 3n+1 */
132#define r2 (dst + 7 * n) /* 3n+1 */
133#define r0 (dst + 11 * n) /* s+t <= 2n */
134#define r5 (scratch) /* 3n+1 */
135#define r3 (scratch + 3 * n + 1) /* 3n+1 */
136#define r1 (scratch + 6 * n + 2) /* 3n+1 */
137#define v0 (dst + 7 * n) /* n+1 */
138#define v1 (dst + 8 * n + 1) /* n+1 */
139#define v2 (dst + 9 * n + 2) /* n+1 */
140#define v3 (scratch + 9 * n + 3) /* n+1 */
141#define wsi (scratch + 9 * n + 3) /* 3n+1,与 v3 复用(生命周期不交) */
142#define wse (scratch + 10 * n + 4) /* 2n+1 */
143
144 /* scratch 总需求 12n+6 limbs;超过 32KiB 自动落池/堆(TALLOC 双轨),
145 最坏递归栈按比例收敛(子层 n' <= (n+5)/6,toom44 子层 SALLOC 10n') */
146 TEMP_DECL;
148
149 /* ±1/2 */
150 sign = lmmp_toom_eval_pm2rexp_(v2, v0, p, numa, n, s, 1, dst) ^ lmmp_toom_eval_pm2rexp_(v3, v1, q, numb, n, t, 1, dst);
151 lmmp_mul_n_(dst, v0, v1, n + 1);
152 lmmp_mul_n_(r5, v2, v3, n + 1);
153 lmmp_toom_couple_handling_(r5, 2 * n + 1, dst, sign, n, 1 + half, half);
154
155 /* ±1 */
156 sign = lmmp_toom_eval_pm1_(v2, v0, p, numa, n, s, dst);
157 if (q == 3)
158 sign ^= lmmp_toom_eval_dgr3_pm1_(v3, v1, numb, n, t, dst);
159 else
160 sign ^= lmmp_toom_eval_pm1_(v3, v1, q, numb, n, t, dst);
161 lmmp_mul_n_(dst, v0, v1, n + 1);
162 lmmp_mul_n_(r3, v2, v3, n + 1);
163 lmmp_toom_couple_handling_(r3, 2 * n + 1, dst, sign, n, 0, 0);
164
165 /* ±4 */
166 sign = lmmp_toom_eval_pm2exp_(v2, v0, p, numa, n, s, 2, dst) ^ lmmp_toom_eval_pm2exp_(v3, v1, q, numb, n, t, 2, dst);
167 lmmp_mul_n_(dst, v0, v1, n + 1);
168 lmmp_mul_n_(r1, v2, v3, n + 1);
169 lmmp_toom_couple_handling_(r1, 2 * n + 1, dst, sign, n, 2, 4);
170
171 /* ±1/4 */
172 sign = lmmp_toom_eval_pm2rexp_(v2, v0, p, numa, n, s, 2, dst) ^ lmmp_toom_eval_pm2rexp_(v3, v1, q, numb, n, t, 2, dst);
173 lmmp_mul_n_(dst, v0, v1, n + 1);
174 lmmp_mul_n_(r4, v2, v3, n + 1);
175 lmmp_toom_couple_handling_(r4, 2 * n + 1, dst, sign, n, 2 * (1 + half), 2 * half);
176
177 /* ±2 */
178 sign = lmmp_toom_eval_pm2_(v2, v0, p, numa, n, s, dst) ^ lmmp_toom_eval_pm2_(v3, v1, q, numb, n, t, dst);
179 lmmp_mul_n_(dst, v0, v1, n + 1);
180 lmmp_mul_n_(r2, v2, v3, n + 1);
181 lmmp_toom_couple_handling_(r2, 2 * n + 1, dst, sign, n, 1, 2);
182
183#undef v0
184#undef v1
185#undef v2
186#undef v3
187#undef wse
188
189 /* A(0)*B(0) */
190 lmmp_mul_n_(dst, numa, numb, n);
191
192 /* 无穷远点:顶部 s*t 尾巴之积,较大者在前 */
193 if (half != 0) {
194 if (s > t)
195 lmmp_mul_(r0, numa + p * n, s, numb + q * n, t);
196 else
197 lmmp_mul_(r0, numb + q * n, t, numa + p * n, s);
198 }
199
200 lmmp_toom_interp12_(dst, r1, r3, r5, n, s + t, half, wsi);
201
202#undef r0
203#undef r1
204#undef r2
205#undef r3
206#undef r4
207#undef r5
208#undef wsi
209
210 TEMP_FREE;
211}
212
213#undef lmmp_mul_n_
214#undef MAYBE_mul_basecase
215#undef MAYBE_mul_toom22
216#undef MAYBE_mul_toom33
217#undef MAYBE_mul_toom6h
#define lmmp_mul_n_
mp_limb_t * mp_ptr
定义 lmmp.h:96
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
void lmmp_mul_toom6h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-6.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±4,...
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]
#define v0
#define r2
#define r1
#define v1
#define r3
#define r0
#define v2
#define t
#define numb
#define s
#define n
#define scratch
#define LIMIT_den
#define wsi
#define v3
#define r4
#define LIMIT_num
#define r5
void lmmp_toom_couple_handling_(mp_ptr pp, mp_size_t n, mp_ptr np, int nsign, mp_size_t off, int ps, int ns)
Copyright (C) 2026 HJimmyK (Jericho Knox)
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 处求值
void lmmp_toom_interp12_(mp_ptr dst, mp_ptr r1, mp_ptr r3, mp_ptr r5, mp_size_t n, mp_size_t spt, int half, mp_ptr tp)
Toom插值计算(12点插值):用于 Toom-6.5(toom6h/toom6 平方)乘法 评估点:inf(仅 half), ±4, ±2, ±1, ±1/2, ±1/4,...
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)