LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom_interp7.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/*
28 syms x integer
29 a = 12*x^3 + 22*x^2 + 32*x + 42;
30 b = 56*x^3 + 62*x^2 + 7*x + 82;
31 c_true = a*b;
32
33 w0 = subs(a,0)*subs(b,0);
34 w1 = subs(a,-2)*subs(b,-2);
35 w2 = subs(a,1)*subs(b,1);
36 w3 = subs(a,-1)*subs(b,-1);
37 w4 = subs(a,2)*subs(b,2);
38 w5 = 64*subs(a,1/2)*subs(b,1/2);
39 w6 = 12*56;
40
41 w5 = w5 + w4;
42 w1 = (w4 - w1)/2;
43 w4 = w4 - w0;
44 w4 = (w4 - w1)/4 - w6*16;
45 w3 = (w2 - w3)/2;
46 w2 = w2 - w3;
47 w5 = w5 - 65*w2;
48 w2 = w2 - w6 - w0;
49 w5 = (w5 + 45*w2)/2;
50 w4 = (w4 - w2)/3;
51 w2 = w2 - w4;
52 w1 = w5 - w1;
53 w5 = (w5 - 8*w3)/9;
54 w3 = w3 - w5;
55 w1 = (w1/15 + w5)/2;
56 w5 = w5 - w1;
57
58 c0 = w0; c1 = w1; c2 = w2; c3 = w3; c4 = w4; c5 = w5; c6 = w6;
59 c_calc = c6*x^6 + c5*x^5 + c4*x^4 + c3*x^3 + c2*x^2 + c1*x + c0;
60*/
61
63 mp_ptr dst,
65 enum toom7_flags flags,
66 mp_ptr w1,
67 mp_ptr w3,
68 mp_ptr w4,
69 mp_ptr w5,
70 mp_size_t w6n,
72) {
73 lmmp_param_assert(w6n > 0);
74 lmmp_param_assert(w6n <= 2 * n);
75 mp_size_t m;
76 mp_limb_t cy;
77
78 m = 2 * n + 1;
79#define w0 dst
80#define w2 (dst + 2 * n)
81#define w6 (dst + 6 * n)
82
83 lmmp_add_n_(w5, w5, w4, m);
84 if (flags & toom7_w1_neg) {
85 lmmp_shr1add_n_(w1, w1, w4, m);
86 } else {
87 lmmp_shr1sub_n_(w1, w4, w1, m);
88 }
89 lmmp_sub_(w4, w4, m, w0, 2 * n);
90 lmmp_sub_n_(w4, w4, w1, m);
91
92 lmmp_debug_assert(!(w4[0] & 3));
93
94 lmmp_shr_(w4, w4, m, 2); /* w4>=0 */
95
96 tp[w6n] = lmmp_shl_(tp, w6, w6n, 4);
97 lmmp_sub_(w4, w4, m, tp, w6n + 1);
98
99 if (flags & toom7_w3_neg) {
100 lmmp_shr1add_n_(w3, w3, w2, m);
101 } else {
102 lmmp_shr1sub_n_(w3, w2, w3, m);
103 }
104
105 lmmp_sub_n_(w2, w2, w3, m);
106
107 lmmp_submul_1_(w5, w2, m, 65);
108 lmmp_sub_(w2, w2, m, w6, w6n);
109 lmmp_sub_(w2, w2, m, w0, 2 * n);
110
111 lmmp_addmul_1_(w5, w2, m, 45);
112 lmmp_debug_assert(!(w5[0] & 1));
113 lmmp_shr_(w5, w5, m, 1);
114 lmmp_sub_n_(w4, w4, w2, m);
115
116 lmmp_divexact_by3_(w4, w4, m);
117 lmmp_sub_n_(w2, w2, w4, m);
118
119 lmmp_sub_n_(w1, w5, w1, m);
120 lmmp_shl_(tp, w3, m, 3);
121 lmmp_sub_n_(w5, w5, tp, m);
123 lmmp_sub_n_(w3, w3, w5, m);
124
125 lmmp_divexact_by15_(w1, w1, m);
126 lmmp_shr1add_n_(w1, w1, w5, m);
127 w1[m - 1] &= LIMB_MAX >> 1;
128
129 lmmp_sub_n_(w5, w5, w1, m);
130
131 /* These bounds are valid for the 4x4 polynomial product of toom44,
132 * and they are conservative for toom53 and toom62. */
133 lmmp_debug_assert(w1[2 * n] < 2);
134 lmmp_debug_assert(w2[2 * n] < 3);
135 lmmp_debug_assert(w3[2 * n] < 4);
136 lmmp_debug_assert(w4[2 * n] < 3);
137 lmmp_debug_assert(w5[2 * n] < 2);
138
139 cy = lmmp_add_n_(dst + n, dst + n, w1, m);
140 lmmp_inc_1(w2 + n + 1, cy);
141 cy = lmmp_add_n_(dst + 3 * n, dst + 3 * n, w3, n);
142 lmmp_inc_1(w3 + n, w2[2 * n] + cy);
143 cy = lmmp_add_n_(dst + 4 * n, w3 + n, w4, n);
144 lmmp_inc_1(w4 + n, w3[2 * n] + cy);
145 cy = lmmp_add_n_(dst + 5 * n, w4 + n, w5, n);
146 lmmp_inc_1(w5 + n, w4[2 * n] + cy);
147 if (w6n > n + 1) {
148 cy = lmmp_add_n_(dst + 6 * n, dst + 6 * n, w5 + n, n + 1);
149 lmmp_inc_1(dst + 7 * n + 1, cy);
150 } else {
151 cy = lmmp_add_n_(dst + 6 * n, dst + 6 * n, w5 + n, w6n);
152 lmmp_debug_assert(cy == 0);
153 }
154}
void lmmp_divexact_by9_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
精确除以9([dst,na] = [numa,na] / 9)
void lmmp_divexact_by3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_divexact_by15_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
精确除以15([dst,na] = [numa,na] / 15)
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 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
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.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
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
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_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 tp
#define n
#define w3
#define w0
#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)
#define w6
toom7_flags
@ toom7_w1_neg
@ toom7_w3_neg