LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom53.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: 0, +1, -1, +2, -2, 1/2, +inf
39
40 <-s-><--n--><--n--><--n--><--n-->
41 |a4-|--a3--|--a2--|--a1--|--a0--|
42 |--b2|--b1--|--b0--|
43 <-t--><--n--><--n-->
44
45 v0 = a0 * b0 # A(0)*B(0)
46 v1 = ( a0+ a1+ a2+ a3+ a4)*( b0+ b1+ b2) # A(1)*B(1) ah <= 4 bh <= 2
47 vm1 = ( a0- a1+ a2- a3+ a4)*( b0- b1+ b2) # A(-1)*B(-1) |ah| <= 2 bh <= 1
48 v2 = ( a0+2a1+4a2+8a3+16a4)*( b0+2b1+4b2) # A(2)*B(2) ah <= 30 bh <= 6
49 vm2 = ( a0-2a1+4a2-8a3+16a4)*( b0-2b1+4b2) # A(2)*B(2) -9<=ah<=20 -1<=bh<=4
50 vh = (16a0+8a1+4a2+2a3+ a4)*(4b0+2b1+ b2) # A(1/2)*B(1/2) ah <= 30 bh <= 6
51 vinf= a4 * b2 # A(inf)*B(inf)
52*/
53
55 lmmp_param_assert(5 * nb > 2 * na);
56 lmmp_param_assert(3 * na > 4 * nb);
57 mp_size_t n, s, t;
58 mp_limb_t cy;
59 mp_ptr gp;
60 mp_ptr as1, asm1, as2, asm2, ash;
62 mp_ptr tmp;
63 enum toom7_flags flags;
65
66#define a0 numa
67#define a1 (numa + n)
68#define a2 (numa + 2 * n)
69#define a3 (numa + 3 * n)
70#define a4 (numa + 4 * n)
71#define b0 numb
72#define b1 (numb + n)
73#define b2 (numb + 2 * n)
74
75 n = 1 + (3 * na >= 5 * nb ? (na - 1) / (mp_size_t)5 : (nb - 1) / (mp_size_t)3);
76 lmmp_param_assert(na > 4 * n && nb > 2 * n);
77 s = na - 4 * n;
78 t = nb - 2 * n;
79
80 lmmp_param_assert(0 < s && s <= n);
81 lmmp_param_assert(0 < t && t <= n);
82
84 tmp = SALLOC_TYPE(10 * (n + 1), mp_limb_t);
85 as1 = tmp;
86 tmp += n + 1;
87 asm1 = tmp;
88 tmp += n + 1;
89 as2 = tmp;
90 tmp += n + 1;
91 asm2 = tmp;
92 tmp += n + 1;
93 ash = tmp;
94 tmp += n + 1;
95 bs1 = tmp;
96 tmp += n + 1;
97 bsm1 = tmp;
98 tmp += n + 1;
99 bs2 = tmp;
100 tmp += n + 1;
101 bsm2 = tmp;
102 tmp += n + 1;
103 bsh = tmp;
104 tmp += n + 1;
105
106 gp = dst;
107
108 /* Compute as1 and asm1. */
109 flags = (enum toom7_flags)(toom7_w3_neg & lmmp_toom_eval_pm1_(as1, asm1, 4, numa, n, s, gp));
110
111 /* Compute as2 and asm2. */
112 flags = (enum toom7_flags)(flags | (toom7_w1_neg & lmmp_toom_eval_pm2_(as2, asm2, 4, numa, n, s, gp)));
113
114 /* Compute ash = 16 a0 + 8 a1 + 4 a2 + 2 a3 + a4
115 = 2*(2*(2*(2*a0 + a1) + a2) + a3) + a4 */
116 cy = lmmp_addshl1_n_(ash, a1, a0, n);
117 cy = 2 * cy + lmmp_addshl1_n_(ash, a2, ash, n);
118 cy = 2 * cy + lmmp_addshl1_n_(ash, a3, ash, n);
119 if (s < n) {
120 mp_limb_t cy2;
121 cy2 = lmmp_addshl1_n_(ash, a4, ash, s);
122 ash[n] = 2 * cy + lmmp_shl_(ash + s, ash + s, n - s, 1);
123 lmmp_inc_1(ash + s, cy2);
124 } else
125 ash[n] = 2 * cy + lmmp_addshl1_n_(ash, a4, ash, n);
126
127 /* Compute bs1 and bsm1. */
128 bs1[n] = lmmp_add_(bs1, b0, n, b2, t); /* b0 + b2 */
129 if (bs1[n] == 0 && lmmp_cmp_(bs1, b1, n) < 0) {
130 bs1[n] = lmmp_add_n_sub_n_(bs1, bsm1, b1, bs1, n) >> 1;
131 bsm1[n] = 0;
132 flags = (enum toom7_flags)(flags ^ toom7_w3_neg);
133 } else {
134 cy = lmmp_add_n_sub_n_(bs1, bsm1, bs1, b1, n);
135 bsm1[n] = bs1[n] - (cy & 1);
136 bs1[n] += (cy >> 1);
137 }
138
139 /* Compute bs2 and bsm2. */
140
141 cy = lmmp_shl_(gp, b2, t, 2);
142 bs2[n] = lmmp_add_(bs2, b0, n, gp, t);
143 lmmp_inc_1(bs2 + t, cy);
144
145 gp[n] = lmmp_shl_(gp, b1, n, 1);
146
147 if (lmmp_cmp_(bs2, gp, n + 1) < 0) {
148 lmmp_add_n_sub_n_(bs2, bsm2, gp, bs2, n + 1);
149 flags = (enum toom7_flags)(flags ^ toom7_w1_neg);
150 } else {
151 lmmp_add_n_sub_n_(bs2, bsm2, bs2, gp, n + 1);
152 }
153
154 /* Compute bsh = 4 b0 + 2 b1 + b2 = 2*(2*b0 + b1)+b2. */
155
156 cy = lmmp_addshl1_n_(bsh, b1, b0, n);
157 if (t < n) {
158 mp_limb_t cy2;
159 cy2 = lmmp_addshl1_n_(bsh, b2, bsh, t);
160 bsh[n] = 2 * cy + lmmp_shl_(bsh + t, bsh + t, n - t, 1);
161 lmmp_inc_1(bsh + t, cy2);
162 } else
163 bsh[n] = 2 * cy + lmmp_addshl1_n_(bsh, b2, bsh, n);
164
165 lmmp_debug_assert(as1[n] <= 4);
166 lmmp_debug_assert(bs1[n] <= 2);
167 lmmp_debug_assert(asm1[n] <= 2);
168 lmmp_debug_assert(bsm1[n] <= 1);
169 lmmp_debug_assert(as2[n] <= 30);
170 lmmp_debug_assert(bs2[n] <= 6);
171 lmmp_debug_assert(asm2[n] <= 20);
172 lmmp_debug_assert(bsm2[n] <= 4);
173 lmmp_debug_assert(ash[n] <= 30);
174 lmmp_debug_assert(bsh[n] <= 6);
175
176#define v0 dst /* 2n */
177#define v1 (dst + 2 * n) /* 2n+1 */
178#define vinf (dst + 6 * n) /* s+t */
179#define v2 scratch /* 2n+1 */
180#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
181#define vh (scratch + 4 * n + 2) /* 2n+1 */
182#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
183#define scratch_out (scratch + 8 * n + 4) /* 2n+1 */
184 /* Total scratch need: 10*n+5 */
185
186 /* Must be in allocation order, as they overwrite one limb beyond
187 * 2n+1. */
188 lmmp_mul_n_(v2, as2, bs2, n + 1); /* v2, 2n+1 limbs */
189 lmmp_mul_n_(vm2, asm2, bsm2, n + 1); /* vm2, 2n+1 limbs */
190 lmmp_mul_n_(vh, ash, bsh, n + 1); /* vh, 2n+1 limbs */
191
192 /* vm1, 2n+1 limbs */
193 vm1[2 * n] = 0;
194 lmmp_mul_n_(vm1, asm1, bsm1, n + ((asm1[n] | bsm1[n]) != 0));
195
196 /* v1, 2n+1 limbs */
197 v1[2 * n] = 0;
198 lmmp_mul_n_(v1, as1, bs1, n + ((as1[n] | bs1[n]) != 0));
199
200 lmmp_mul_n_(v0, a0, b0, n); /* v0, 2n limbs */
201
202 /* vinf, s+t limbs */
203 if (s > t)
204 lmmp_mul_(vinf, a4, s, b2, t);
205 else
206 lmmp_mul_(vinf, b2, t, a4, s);
207
208 lmmp_toom_interp7_(dst, n, flags, vm2, vm1, v2, vh, s + t, scratch_out);
209
211}
#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
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]
mp_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
定义 shl.c:53
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
void lmmp_mul_toom53_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-53乘法运算 [dst,na+nb] = [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])
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
#define b0
#define b1
#define a0
#define a1
#define v0
#define bsm1
#define asm1
#define vinf
#define vm1
#define a2
#define v1
#define v2
#define b2
#define t
#define a3
#define numb
#define s
#define n
#define bs1
#define bs2
#define as2
#define asm2
#define bsm2
#define as1
#define vm2
#define vh
#define a4
#define scratch_out
#define scratch
#define tmp
#define bsh
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_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)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TEMP_S_FREE
toom7_flags
@ toom7_w1_neg
@ toom7_w3_neg