LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_toom_interp6.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 = 2*x^3 + 32*x^2 + 4*x + 5;
30 b = 6*x^2 + 712*x + 18;
31 c_true = a*b;
32
33 w0 = 2*6;
34 w1 = subs(a,2)*subs(b,2);
35 w2 = subs(a,-2)*subs(b,-2);
36 w3 = subs(a,1)*subs(b,1);
37 w4 = subs(a,-1)*subs(b,-1);
38 w5 = subs(a,0)*subs(b,0);
39
40 w2 = (w1 - w2)/4;
41 w1 = (w1 - w5)/2;
42 w1 = (w1 - w2)/2;
43 w4 = (w3 - w4)/2;
44 w2 = (w2 - w4)/3;
45 w3 = w3 - w4 - w5;
46 w1 = (w1 - w3)/3;
47 w2 = w2 - w0*4;
48 w4 = w4 - w2;
49 w3 = w3 - w1;
50 w2 = w2 - w0;
51
52 c0=w5; c1=w4; c2=w3; c3=w2; c4=w1; c5=w0;
53 c_calc = c5*x^5 + c4*x^4 + c3*x^3 + c2*x^2 + c1*x + c0;
54*/
55
57 mp_ptr dst,
59 enum toom6_flags flags,
60 mp_ptr w4,
61 mp_ptr w2,
62 mp_ptr w1,
63 mp_size_t w0n
64) {
65
67 lmmp_param_assert(2 * n >= w0n && w0n > 0);
68 mp_limb_t cy;
69 /* cy6 can be stored in w1[2*n], cy4 in w4[0], embankment in w2[0] */
70 mp_limb_t cy4, cy6, embankment;
71
72#define w5 dst /* 2n */
73#define w3 (dst + 2 * n) /* 2n+1 */
74#define w0 (dst + 5 * n) /* w0n */
75
76 /* W2 =(W1 - W2)>>2 */
77 if (flags & toom6_vm2_neg)
78 lmmp_add_n_(w2, w1, w2, 2 * n + 1);
79 else
80 lmmp_sub_n_(w2, w1, w2, 2 * n + 1);
81 lmmp_shr_(w2, w2, 2 * n + 1, 2);
82
83 /* W1 =(W1 - W5)>>1 */
84 w1[2 * n] -= lmmp_sub_n_(w1, w1, w5, 2 * n);
85 lmmp_shr_(w1, w1, 2 * n + 1, 1);
86
87 /* W1 =(W1 - W2)>>1 */
88 lmmp_shr1sub_n_(w1, w1, w2, 2 * n + 1);
89
90 /* W4 =(W3 - W4)>>1 */
91 if (flags & toom6_vm1_neg) {
92 lmmp_shr1add_n_(w4, w3, w4, 2 * n + 1);
93 } else {
94 lmmp_shr1sub_n_(w4, w3, w4, 2 * n + 1);
95 }
96
97 /* W2 =(W2 - W4)/3 */
98 lmmp_sub_n_(w2, w2, w4, 2 * n + 1);
99 lmmp_divexact_by3_(w2, w2, 2 * n + 1);
100
101 /* W3 = W3 - W4 - W5 */
102 lmmp_sub_n_(w3, w3, w4, 2 * n + 1);
103 w3[2 * n] -= lmmp_sub_n_(w3, w3, w5, 2 * n);
104
105 /* W1 =(W1 - W3)/3 */
106 lmmp_sub_n_(w1, w1, w3, 2 * n + 1);
107 lmmp_divexact_by3_(w1, w1, 2 * n + 1);
108
109 cy = lmmp_add_n_(dst + n, dst + n, w4, 2 * n + 1);
110 lmmp_inc_1(dst + 3 * n + 1, cy);
111
112 /* W2 -= W0<<2 */
113 /* {W4,2*n+1} is now free and can be overwritten. */
114 cy = lmmp_shl_(w4, w0, w0n, 2);
115 cy += lmmp_sub_n_(w2, w2, w4, w0n);
116
117 lmmp_dec_1(w2 + w0n, cy);
118
119 /* W4L = W4L - W2L */
120 cy = lmmp_sub_n_(dst + n, dst + n, w2, n);
121 lmmp_dec_1(w3, cy);
122
123 /* W3H = W3H + W2L */
124 cy4 = w3[2 * n] + lmmp_add_n_(dst + 3 * n, dst + 3 * n, w2, n);
125 /* W1L + W2H */
126 cy = w2[2 * n] + lmmp_add_n_(dst + 4 * n, w1, w2 + n, n);
127 lmmp_inc_1(w1 + n, cy);
128
129 /* W0 = W0 + W1H */
130 if (w0n > n)
131 cy6 = w1[2 * n] + lmmp_add_n_(w0, w0, w1 + n, n);
132 else
133 cy6 = lmmp_add_n_(w0, w0, w1 + n, w0n);
134
135 cy = lmmp_sub_n_(dst + 2 * n, dst + 2 * n, dst + 4 * n, n + w0n);
136
137 /* embankment is a "dirty trick" to avoid carry/borrow propagation
138 beyond allocated memory */
139 embankment = w0[w0n - 1] - 1;
140 w0[w0n - 1] = 1;
141 if (w0n > n) {
142 if (cy4 > cy6)
143 lmmp_inc_1(dst + 4 * n, cy4 - cy6);
144 else
145 lmmp_dec_1(dst + 4 * n, cy6 - cy4);
146 lmmp_dec_1(dst + 3 * n + w0n, cy);
147 lmmp_inc_1(w0 + n, cy6);
148 } else {
149 lmmp_inc_1(dst + 4 * n, cy4);
150 lmmp_dec_1(dst + 3 * n + w0n, cy + cy6);
151 }
152 w0[w0n - 1] += embankment;
153
154#undef w5
155#undef w3
156#undef w0
157}
void lmmp_divexact_by3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
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
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
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 n
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 w0
#define w5
#define w2
toom6_flags
Copyright (C) 2026 HJimmyK (Jericho Knox)
@ toom6_vm2_neg
@ toom6_vm1_neg