LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
toom_interp.h
浏览该文件的文档.
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#ifndef __LMMP_TOOM_INTERP_H__
24#define __LMMP_TOOM_INTERP_H__
25
26#include "impl/tmp_alloc.h"
27#include "lmmp/lmmpn.h"
28
30
32
33/**
34 * @brief Toom插值计算(5点插值),用于Toom-33和Toom-42乘法算法
35 * @param dst 输出结果缓冲区,存储插值计算结果
36 * v(0)储存在[dst,2n],v(1)储存在[dst+2n,2n]
37 * @param v2 v(2)插值点值,长度为 2n+1 个limb
38 * @param vm1 v(-1)插值点值,长度为 2n+1 个limb
39 * @param n 操作数的 limb 长度
40 * @param spt 系数r4的长度
41 * @param vm1_neg 符号标记:v(-1)是否为负数(1表示负,0表示正)
42 * @param vinf0 无穷远点插值的低64位值
43 * @warning dst!=NULL, v2!=NULL, vm1!=NULL, n>0
44 */
45void 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);
46
47/**
48 * @brief Toom插值计算(6点插值):用于Toom-43和Toom-52 乘法算法
49 * @param dst 最终乘积结果缓冲区(5n + w0n limbs)
50 * w5 储存在[dst,2n], w3 储存在[dst+2n,2n+1], w0 储存在[dst+5n,w0n].
51 * @param n Toom-6 拆分后每段标准 limb 长度
52 * @param flags 插值符号标志位
53 * @param w4 输入/临时:点值 W4 缓冲区(2n+1 limbs)
54 * @param w2 输入/临时:点值 W2 缓冲区(2n+1 limbs)
55 * @param w1 输入/临时:点值 W1 缓冲区(2n+1 limbs)
56 * @param w0n 输入:最低位段 W0 的实际 limb 长度(0 < w0n <= 2n)
57 * @note w5=f(0), w4=f(-1), w3=f(1), w2=f(-2), w1=f(2), w0=f(inf)
58 * @warning n>0, 0<w0n<=2n, dst!=NULL, w4!=NULL, w2!=NULL, w1!=NULL
59 */
60void 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);
61
62/**
63 * @brief Toom插值计算(7点插值):用于Toom-44、Toom-53、Toom-62 乘法算法
64 * @param dst 输出结果缓冲区,存储插值计算结果(6*n + w6n limbs)
65 * w0 储存在[dst,2n], w2 储存在[dst+2n,2n+1], w6 储存在[dst+6n,w6n].
66 * @param n Toom-7 拆分后每段标准 limb 长度
67 * @param flags Toom-7 符号标志位,控制插值中的正负号运算
68 * @param w1 输入/临时:点值 W1 缓冲区(2n+1 limbs)
69 * @param w3 输入/临时:点值 W3 缓冲区(2n+1 limbs)
70 * @param w4 输入/临时:点值 W4 缓冲区(2n+1 limbs)
71 * @param w5 输入/临时:点值 W5 缓冲区(2n+1 limbs)
72 * @param w6n 输入:最低位段 W6 的实际 limb 长度 (0 < w6n <= 2n)
73 * @param tp 临时缓存空间(2*n+1 limbs)
74 * @note w0=f(0), w1=f(-2), w2=f(1), w3=f(-1), w4=f(2), w5=64*f(1/2), w6=f(inf),
75 * @warning n>0, 0<w6n<=2n, dst!=NULL, w1!=NULL, w3!=NULL, w4!=NULL, w5!=NULL, tp!=NULL
76 */
78 mp_size_t w6n, mp_ptr tp);
79
80/**
81 * @brief Toom-3 专用:3次多项式在 x = +1 和 x = -1 处求值
82 * 计算 P(+1) 和 P(-1),其中 P(x) 是一个3次多项式(4段系数)。
83 * @param xp1 输出:P(+1) 的结果(n+1 个 limb)
84 * @param xm1 输出:P(-1) 的结果(n+1 个 limb)
85 * @param xp 输入:多项式系数数组(共4段,每段 n limbs)
86 * @param n 每段完整系数的 limb 长度
87 * @param x3n 最后一段系数的实际长度(通常等于 n)
88 * @param tp 临时缓存空间(至少 n+1 limbs)
89 * @warning 0<x3n<=n, xp1!=NULL, xm1!=NULL, xp!=NULL, tp!=NULL
90 * @return 符号位:0=正,~0=负(对应 P(-1))
91 */
93
94/**
95 * @brief Toom-3 专用:3次多项式在 x = +2 和 x = -2 处求值
96 * 计算 P(+2) 和 P(-2),其中 P(x) 是一个3次多项式(4段系数)。
97 * @param xp2 输出:P(+2) 的结果(n+1 个 limb)
98 * @param xm2 输出:P(-2) 的结果(n+1 个 limb)
99 * @param xp 输入:多项式系数数组(共4段,每段 n limbs)
100 * @param n 每段完整系数的 limb 长度
101 * @param x3n 最后一段系数的实际长度
102 * @param tp 临时缓存空间(至少 n+1 limbs)
103 * @warning 0<x3n<=n, xp2!=NULL, xm2!=NULL, xp!=NULL, tp!=NULL
104 * @return 符号位:0=正,~0=负(对应 P(-2))
105 */
107
108/**
109 * @brief 通用高阶 Toom 求值:k次多项式在 x = +1 和 x = -1 处求值
110 * @param xp1 输出:P(+1) 的结果(n+1 limbs)
111 * @param xm1 输出:P(-1) 的结果(n+1 limbs)
112 * @param k 输入:多项式次数(也是完整段的数量)
113 * @param xp 输入:多项式系数数组
114 * @param n 输入:每段完整系数的 limb 长度
115 * @param hn 输入:最后一段系数的实际长度
116 * @param tp 临时缓存空间(n+1 limbs)
117 * @warning 0<hn<=n, 3<k, xp1!=NULL, xm1!=NULL, xp!=NULL, tp!=NULL
118 * @return 符号位:0=正,~0=负
119 */
121
122/**
123 * @brief 通用高阶 Toom 求值:k次多项式在 x = +2 和 x = -2 处求值
124 * @param xp2 输出:P(+2) 的结果(n+1 limbs)
125 * @param xm2 输出:P(-2) 的结果(n+1 limbs)
126 * @param k 输入:多项式次数
127 * @param xp 输入:多项式系数数组
128 * @param n 输入:每段完整系数的 limb 长度
129 * @param hn 输入:最后一段系数的实际长度
130 * @param tp 临时缓存空间(n+1 limbs)
131 * @warning 0<hn<=n, 3 < k < LIMB_BITS, xp2!=NULL, xm2!=NULL, xp!=NULL, tp!=NULL
132 * @return 符号位:0=正,~0=负
133 */
135
136/**
137 * @brief 通用高阶 Toom 求值:k次多项式在 x = +2^shift 和 x = -2^shift 处求值
138 * (toom6h 的 ±4 / toom8h 的 ±4、±8 点)
139 * @param xp2 输出:P(+2^shift) 的结果(n+1 limbs)
140 * @param xm2 输出:P(-2^shift) 的结果(n+1 limbs);求值过程中亦作暂存
141 * @param k 输入:多项式次数(完整段数)
142 * @param xp 输入:多项式系数数组(k 个 n 长段 + 1 个 hn 长尾段)
143 * @param n 输入:每段完整系数的 limb 长度
144 * @param hn 输入:最后一段系数的实际长度
145 * @param shift 输入:2 的幂指数(1<=shift,且 k*shift < LIMB_BITS)
146 * @param tp 临时缓存空间(n+1 limbs)
147 * @warning 0<hn<=n, 3<=k, k*shift<LIMB_BITS, sep(xp2,[xp|tp]), sep(xm2,[xp|tp])
148 * @return 符号位:0=正,~0=负(对应 P(-2^shift))
149 */
150int 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);
151
152/**
153 * @brief 通用高阶 Toom 求值:q次多项式在 x = +1/2^s 和 x = -1/2^s 处求值,
154 * 结果放大 2^(s*q)(toom6h 的 ±1/2、±1/4 / toom8h 的 ±1/2、±1/4、±1/8 点)
155 * @param rp 输出:2^(s*q)*P(+1/2^s) 的结果(n+1 limbs)
156 * @param rm 输出:2^(s*q)*P(-1/2^s) 的结果(n+1 limbs)
157 * @param q 输入:多项式次数(完整段数)
158 * @param ap 输入:多项式系数数组(q 个 n 长段 + 1 个 t 长尾段)
159 * @param n 输入:每段完整系数的 limb 长度
160 * @param t 输入:最后一段系数的实际长度
161 * @param s 输入:2 的幂指数(s!=0,且 q*s < LIMB_BITS)
162 * @param ws 临时缓存空间(n+1 limbs)
163 * @warning 0<t<=n, 1<q, sep(rp,[ap|ws]), sep(rm,[ap|ws])
164 * @return 符号位:0=正,~0=负(对应 P(-1/2^s))
165 */
166int 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);
167
168/**
169 * @brief Toom ± 点对配对混合:一次完成和/差半边的右移缩放与重叠拼回
170 * (toom6h/8h 各评估点对的两个 (n+1) 位乘积的后处理)
171 * 输入 [pp,n] 与 (nsign ? -[np,n] : [np,n]),计算:
172 * [np,n] <- ([pp,n]+[np,n])/2^(ns+1)(和半边,供奇系数插值)
173 * [pp,n] <- ([pp,n]-[np,n])/2^(ps+1)(差半边,供偶系数)
174 * 最后 {pp,n+off} <- {pp,n} + {np,n}*B^off
175 * @param pp 输入/输出:正点值乘积(容量 n+off+1 limbs)
176 * @param n 有效数据长度
177 * @param np 输入/输出:负点值乘积(容量 n limbs)
178 * @param nsign np 的符号(非 0 表示 np 存的是负值)
179 * @param off 拼回偏移(limb 数,0<=off<n)
180 * @param ps 和半边附加右移位数
181 * @param ns 差半边附加右移位数
182 * @warning 0<=off<n, ps>=0, ns>=0, pp/np 数据低 ps+1/ns+1 位保证为 0
183 */
184void lmmp_toom_couple_handling_(mp_ptr pp, mp_size_t n, mp_ptr np, int nsign, mp_size_t off, int ps, int ns);
185
186/**
187 * @brief Toom插值计算(12点插值):用于 Toom-6.5(toom6h/toom6 平方)乘法
188 * 评估点:inf(仅 half), ±4, ±2, ±1, ±1/2, ±1/4, 0
189 * @param dst 结果缓冲区(half ? 11n+spt : 10n+spt limbs)
190 * r8=f(0) 在 [dst,2n],r6 在 [dst+3n,3n+1],
191 * r4 在 [dst+7n,3n+1],r0 在 [dst+11n,spt]
192 * @param r1 输入/临时:±8...±4 点对混合后的奇系数(3n+1 limbs)
193 * @param r3 输入/临时:±1 点对(3n+1 limbs)
194 * @param r5 输入/临时:±1/2 点对(3n+1 limbs)
195 * @param n 每段标准 limb 长度
196 * @param spt 顶部系数 r0 的长度(0<spt<=2n)
197 * @param half 非零表示乘积多项式次数为奇(需要 inf 点,r0 有效)
198 * @param tp 临时缓存(3n+1 limbs)
199 * @note r1=f(±4), r2=f(±2), r3=f(±1), r4=f(±1/4), r5=f(±1/2);
200 * 各 ± 点对须先经 lmmp_toom_couple_handling_ 混合;负中间值以
201 * 补码存放,输入被破坏
202 * @warning n>0, 0<spt<=2n, sep(tp,[dst|r1|r3|r5])
203 */
205
206/**
207 * @brief Toom插值计算(16点插值):用于 Toom-8.5(toom8h/toom8 平方)乘法
208 * 评估点:inf(仅 half), ±8, ±4, ±2, ±1, ±1/2, ±1/4, ±1/8, 0
209 * @param dst 结果缓冲区(half ? 15n+spt : 14n+spt limbs)
210 * r8=f(0) 在 [dst,2n],r6 在 [dst+3n,3n+1],r4 在 [dst+7n,3n+1],
211 * r2 在 [dst+11n,3n+1],r0 在 [dst+15n,spt]
212 * @param r1 输入/临时:±8 点对混合后的奇系数(3n+1 limbs)
213 * @param r3 输入/临时:±2 点对(3n+1 limbs)
214 * @param r5 输入/临时:±1/4 点对(3n+1 limbs)
215 * @param r7 输入/临时:±1/8 点对(3n+1 limbs)
216 * @param n 每段标准 limb 长度
217 * @param spt 顶部系数 r0 的长度(0<spt<=2n)
218 * @param half 非零表示乘积多项式次数为奇(需要 inf 点,r0 有效)
219 * @param tp 临时缓存(3n+1 limbs)
220 * @note r1=f(±8), r2=f(±4), r3=f(±2), r4=f(±1), r5=f(±1/4), r6=f(±1/2),
221 * r7=f(±1/8);各 ± 点对须先经 lmmp_toom_couple_handling_ 混合;
222 * 负中间值以补码存放,输入被破坏
223 * @warning n>0, 0<spt<=2n, sep(tp,[dst|r1|r3|r5|r7])
224 */
226
227#endif // __LMMP_TOOM_INTERP_H__
#define k
#define rp
mp_limb_t * mp_ptr
定义 lmmp.h:96
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 xp
#define vm1
#define r1
#define r3
#define v2
#define t
#define tp
#define s
#define n
#define r5
#define r7
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 处求值
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段系数)。
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,...
void lmmp_toom_interp16_(mp_ptr dst, mp_ptr r1, mp_ptr r3, mp_ptr r5, mp_ptr r7, mp_size_t n, mp_size_t spt, int half, mp_ptr tp)
Toom插值计算(16点插值):用于 Toom-8.5(toom8h/toom8 平方)乘法 评估点:inf(仅 half), ±8, ±4, ±2, ±1, ±1/2,...
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)
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 w3
#define w5
#define w2
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)
toom6_flags
Copyright (C) 2026 HJimmyK (Jericho Knox)
@ toom6_vm2_neg
@ toom6_vm1_neg
@ toom6_all_pos
toom7_flags
@ toom7_w1_neg
@ toom7_w3_neg