LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom_interp16.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/divexact.h"
24#include "lmmpn/toom_interp.h"
25
26
27#define DO_subrsh(dst, nd, src, ns, s) \
28 do { \
29 mp_limb_t __cy; \
30 lmmp_dec_1((dst), (src)[0] >> (s)); \
31 __cy = lmmp_submul_1_((dst), (src) + 1, (ns) - 1, (mp_limb_t)1 << (LIMB_BITS - (s))); \
32 lmmp_dec_1((dst) + (ns) - 1, __cy); \
33 } while (0)
34
35#define BINVERT_9_ ((mp_limb_t)0x8E38E38E38E38E39)
36#define BINVERT_255_ ((mp_limb_t)0xFEFEFEFEFEFEFEFF)
37#define BINVERT_2835_ ((mp_limb_t)0x938CC70553E3771B)
38#define BINVERT_42525_ ((mp_limb_t)0xE7B40D449F314C35)
39#define BINVERT_255x182712915_ ((mp_limb_t)0x1B649A076FC4CB25)
40#define BINVERT_255x188513325_ ((mp_limb_t)0x06DB993A6864275B)
41
44) {
45 mp_limb_t cy, cy2;
46 mp_size_t n3, n3p1;
47 n3 = 3 * n;
48 n3p1 = n3 + 1;
49
51 lmmp_param_assert(spt > 0);
52 lmmp_param_assert(spt <= 2 * n);
53
54#define r6 (dst + n3) /* 3n+1 */
55#define r4 (dst + 7 * n) /* 3n+1 */
56#define r2 (dst + 11 * n) /* 3n+1 */
57#define r0 (dst + 15 * n) /* spt <= 2n */
58
59 if (half != 0) {
60 cy = lmmp_sub_n_(r4, r4, r0, spt);
61 lmmp_dec_1(r4 + spt, cy);
62
63 cy = lmmp_submul_1_(r3, r0, spt, (mp_limb_t)1 << 14);
64 lmmp_dec_1(r3 + spt, cy);
65 DO_subrsh(r6, n3p1, r0, spt, 2);
66
67 cy = lmmp_submul_1_(r2, r0, spt, (mp_limb_t)1 << 28);
68 lmmp_dec_1(r2 + spt, cy);
69 DO_subrsh(r5, n3p1, r0, spt, 4);
70
71 cy = lmmp_submul_1_(r1, r0, spt, (mp_limb_t)1 << 42);
72 lmmp_dec_1(r1 + spt, cy);
73 DO_subrsh(r7, n3p1, r0, spt, 6);
74 }
75
76 r5[n3] -= lmmp_submul_1_(r5 + n, dst, 2 * n, (mp_limb_t)1 << 28);
77 DO_subrsh(r2 + n, 2 * n + 1, dst, 2 * n, 4);
78
79 lmmp_add_n_sub_n_(r2, r5, r5, r2, n3p1);
80
81 r6[n3] -= lmmp_submul_1_(r6 + n, dst, 2 * n, (mp_limb_t)1 << 14);
82 DO_subrsh(r3 + n, 2 * n + 1, dst, 2 * n, 2);
83
84 lmmp_add_n_sub_n_(r3, r6, r6, r3, n3p1);
85
86 r7[n3] -= lmmp_submul_1_(r7 + n, dst, 2 * n, (mp_limb_t)1 << 42);
87 DO_subrsh(r1 + n, 2 * n + 1, dst, 2 * n, 6);
88
89 lmmp_add_n_sub_n_(r1, r7, r7, r1, n3p1);
90
91 r4[n3] -= lmmp_sub_n_(r4 + n, r4 + n, dst, 2 * n);
92
93 lmmp_submul_1_(r5, r6, n3p1, 1028);
94 lmmp_submul_1_(r7, r5, n3p1, 1300);
95 lmmp_submul_1_(r7, r6, n3p1, 1052688);
96 lmmp_divexact_odd_pi_(r7, r7, n3p1, (mp_limb_t)255 * 188513325, BINVERT_255x188513325_, 0);
97
98 lmmp_submul_1_(r5, r7, n3p1, 12567555);
99 /* 随后除以 2835*64,操作数可能为负(补码) */
100 lmmp_divexact_odd_pi_(r5, r5, n3p1, 2835, BINVERT_2835_, 6);
101 if ((r5[n3] & (LIMB_MAX << (LIMB_BITS - 7))) != 0)
102 r5[n3] |= LIMB_MAX << (LIMB_BITS - 6);
103
104 lmmp_submul_1_(r6, r7, n3p1, 4095);
105 lmmp_addmul_1_(r6, r5, n3p1, 240);
106 /* 随后除以 255*4,操作数可能为负(补码) */
107 lmmp_divexact_odd_pi_(r6, r6, n3p1, 255, BINVERT_255_, 2);
108 if ((r6[n3] & (LIMB_MAX << (LIMB_BITS - 3))) != 0)
109 r6[n3] |= LIMB_MAX << (LIMB_BITS - 2);
110
111 cy = lmmp_submul_1_(r3, r4, n3p1, (mp_limb_t)1 << 7);
112 lmmp_debug_assert(cy == 0);
113
114 cy = lmmp_submul_1_(r2, r4, n3p1, (mp_limb_t)1 << 13);
115 lmmp_debug_assert(cy == 0);
116 cy = lmmp_submul_1_(r2, r3, n3p1, 400);
117 lmmp_debug_assert(cy == 0);
118
119 lmmp_submul_1_(r1, r4, n3p1, (mp_limb_t)1 << 19);
120 lmmp_submul_1_(r1, r2, n3p1, 1428);
121 lmmp_submul_1_(r1, r3, n3p1, 112896);
122 lmmp_divexact_odd_pi_(r1, r1, n3p1, (mp_limb_t)255 * 182712915, BINVERT_255x182712915_, 0);
123
124 cy = lmmp_submul_1_(r2, r1, n3p1, 15181425);
125 lmmp_debug_assert(cy == 0);
126 lmmp_divexact_odd_pi_(r2, r2, n3p1, 42525, BINVERT_42525_, 4);
127
128 cy = lmmp_submul_1_(r3, r1, n3p1, 3969);
129 lmmp_debug_assert(cy == 0);
130 cy = lmmp_submul_1_(r3, r2, n3p1, 900);
131 lmmp_debug_assert(cy == 0);
132 lmmp_divexact_odd_pi_(r3, r3, n3p1, 9, BINVERT_9_, 4);
133
134 cy = lmmp_sub_n_(r4, r4, r1, n3p1);
135 lmmp_debug_assert(cy == 0);
136 cy = lmmp_sub_n_(r4, r4, r3, n3p1);
137 lmmp_debug_assert(cy == 0);
138 cy = lmmp_sub_n_(r4, r4, r2, n3p1);
139 lmmp_debug_assert(cy == 0);
140
141 lmmp_shr1add_n_(r6, r2, r6, n3p1);
142 r6[n3p1 - 1] &= LIMB_MAX >> 1;
143 cy = lmmp_sub_n_(r2, r2, r6, n3p1);
144 lmmp_debug_assert(cy == 0);
145
146 lmmp_shr1sub_n_(r5, r3, r5, n3p1);
147 r5[n3p1 - 1] &= LIMB_MAX >> 1;
148 cy = lmmp_sub_n_(r3, r3, r5, n3p1);
149 lmmp_debug_assert(cy == 0);
150
151 lmmp_shr1add_n_(r7, r1, r7, n3p1);
152 r7[n3p1 - 1] &= LIMB_MAX >> 1;
153 cy = lmmp_sub_n_(r1, r1, r7, n3p1);
154 lmmp_debug_assert(cy == 0);
155
156 (void)tp; /* 现有原语集(submul/addmul/原生 add_n_sub_n)不消耗临时区 */
157
158 /***************************** 重组 *******************************/
159 /*
160 dst 操作前:
161 |M r0|L r0|___||H r2|M r2|L r2|___||H r4|M r4|L r4|___||H r6|M r6|L r6|____|H_r8|L_r8|dst
162 求和方案:
163 |__16|n_15|n_14|n_13|n_12|n_11|n_10|n__9|n__8|n__7|n__6|n__5|n__4|n__3|n__2|n___|n___|dst
164 |M r0|L r0|___||H r2|M r2|L r2|___||H r4|M r4|L r4|___||H r6|M r6|L r6|____|H_r8|L_r8|dst
165 ||H r1|M r1|L r1| ||H r3|M r3|L r3| ||H_r5|M_r5|L_r5| ||H_r7|M_r7|L_r7|
166 */
167
168 cy = lmmp_add_n_(dst + n, dst + n, r7, n);
169 cy = lmmp_add_1_(dst + 2 * n, r7 + n, n, cy);
170 cy = r7[n3] + lmmp_add_nc_(dst + n3, dst + n3, r7 + 2 * n, n, cy);
171 lmmp_inc_1(dst + 4 * n, cy);
172
173 dst[2 * n3] += lmmp_add_n_(dst + 5 * n, dst + 5 * n, r5, n);
174 cy = lmmp_add_1_(dst + 2 * n3, r5 + n, n, dst[2 * n3]);
175 cy = r5[n3] + lmmp_add_nc_(dst + 7 * n, dst + 7 * n, r5 + 2 * n, n, cy);
176 lmmp_inc_1(dst + 8 * n, cy);
177
178 dst[10 * n] += lmmp_add_n_(dst + 9 * n, dst + 9 * n, r3, n);
179 cy = lmmp_add_1_(dst + 10 * n, r3 + n, n, dst[10 * n]);
180 cy = r3[n3] + lmmp_add_nc_(dst + 11 * n, dst + 11 * n, r3 + 2 * n, n, cy);
181 lmmp_inc_1(dst + 12 * n, cy);
182
183 dst[14 * n] += lmmp_add_n_(dst + 13 * n, dst + 13 * n, r1, n);
184 if (half) {
185 cy = lmmp_add_1_(dst + 14 * n, r1 + n, n, dst[14 * n]);
186 if (spt > n) {
187 cy = r1[n3] + lmmp_add_nc_(dst + 15 * n, dst + 15 * n, r1 + 2 * n, n, cy);
188 lmmp_inc_1(dst + 16 * n, cy);
189 } else {
190 cy2 = lmmp_add_nc_(dst + 15 * n, dst + 15 * n, r1 + 2 * n, spt, cy);
191 lmmp_debug_assert(cy2 == 0);
192 }
193 } else {
194 cy = lmmp_add_1_(dst + 14 * n, r1 + n, spt, dst[14 * n]);
195 lmmp_debug_assert(cy == 0);
196 }
197
198#undef r6
199#undef r4
200#undef r2
201#undef r0
202}
mp_limb_t lmmp_divexact_odd_pi_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t di, unsigned shr)
通用奇除数精确除,可带 2^shr 因子: [dst,na] = [numa,na] / (d*2^shr),其中 d 为奇数、di = d^(-1) mod B
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LIMB_MAX
定义 lmmp.h:105
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_limb_t lmmp_shr1add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1
定义 shr.c:65
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
mp_limb_t lmmp_add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c
定义 add_n.c:58
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_dec_1(p, dec)
减指定值宏(预期无借位)
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
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
mp_limb_t lmmp_shr1sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1
定义 shr.c:87
#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 r2
#define r1
#define r3
#define r0
#define tp
#define n
#define r4
#define r5
#define r6
#define r7
#define BINVERT_42525_
#define DO_subrsh(dst, nd, src, ns, s)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define BINVERT_9_
#define BINVERT_255_
#define BINVERT_2835_
#define BINVERT_255x182712915_
#define BINVERT_255x188513325_
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,...