LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
sqr_toom4.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 MAYBE_sqr_toom2 (SQR_TOOM44_THRESHOLD < 4 * SQR_TOOM33_THRESHOLD)
28#define MAYBE_sqr_toom4 (SQR_TOOM6_THRESHOLD >= 4 * SQR_TOOM44_THRESHOLD)
29
30#define lmmp_sqr_(dst, numa, n) \
31 if ((n) < LMMP_MAX(4, SQR_TOOM22_THRESHOLD)) \
32 lmmp_sqr_hard_n_((dst), (numa), (n)); \
33 else if (MAYBE_sqr_toom2 && (n) < SQR_TOOM33_THRESHOLD) \
34 lmmp_sqr_toom2_((dst), (numa), (n)); \
35 else if (!MAYBE_sqr_toom4 || (n) < SQR_TOOM44_THRESHOLD) \
36 lmmp_sqr_toom3_((dst), (numa), (n)); \
37 else \
38 lmmp_sqr_toom4_((dst), (numa), (n))
39
40/*
41Evaluate in: -1, -1/2, 0, +1/2, +1, +2, +inf
42
43 <-s--><--n--><--n--><--n-->
44 |-a3-|--a2--|--a1--|--a0--|
45
46 v0 = a0 ^2 # A(0)^2
47 v1 = ( a0+ a1+ a2+ a3)^2 # A(1)^2 ah <= 3
48 vm1 = ( a0- a1+ a2- a3)^2 # A(-1)^2 |ah| <= 1
49 v2 = ( a0+2a1+4a2+8a3)^2 # A(2)^2 ah <= 14
50 vh = (8a0+4a1+2a2+ a3)^2 # A(1/2)^2 ah <= 14
51 vmh = (8a0-4a1+2a2- a3)^2 # A(-1/2)^2 -4<=ah<=9
52 vinf= a3 ^2 # A(inf)^2
53*/
54
56 lmmp_param_assert(na > 9);
57 lmmp_param_assert(dst != NULL);
58 lmmp_param_assert(numa != NULL);
59 mp_size_t n, s;
60 mp_limb_t cy;
61
62#define a0 numa
63#define a1 (numa + n)
64#define a2 (numa + 2 * n)
65#define a3 (numa + 3 * n)
66
67 n = (na + 3) >> 2;
70
71 s = na - 3 * n;
72
73 lmmp_debug_assert(0 < s && s <= n);
74
75 /* NOTE: The multiplications to v2, vm2, vh and vm1 overwrites the
76 * following limb, so these must be computed in order, and we need a
77 * one limb gap to tp. */
78#define v0 dst /* 2n */
79#define v1 (dst + 2 * n) /* 2n+1 */
80#define vinf (dst + 6 * n) /* s+t */
81#define v2 scratch /* 2n+1 */
82#define vm2 (scratch + 2 * n + 1) /* 2n+1 */
83#define vh (scratch + 4 * n + 2) /* 2n+1 */
84#define vm1 (scratch + 6 * n + 3) /* 2n+1 */
85#define tp (scratch + 8 * n + 5)
86
87 /* No overlap with v1 */
88#define apx dst /* n+1 */
89#define amx (dst + 4 * n + 2) /* n+1 */
90
91 /* Compute apx = a0 + 2 a1 + 4 a2 + 8 a3 and amx = a0 - 2 a1 + 4 a2 - 8 a3. */
93
94 lmmp_sqr_(v2, apx, n + 1); /* v2, 2n+1 limbs */
95 lmmp_sqr_(vm2, amx, n + 1); /* vm2, 2n+1 limbs */
96
97 /* Compute apx = 8 a0 + 4 a1 + 2 a2 + a3 = (((2*a0 + a1) * 2 + a2) * 2 + a3 */
98 cy = lmmp_addshl1_n_(apx, a1, a0, n);
99 cy = 2 * cy + lmmp_addshl1_n_(apx, a2, apx, n);
100 if (s < n) {
101 mp_limb_t cy2;
102 cy2 = lmmp_addshl1_n_(apx, a3, apx, s);
103 apx[n] = 2 * cy + lmmp_shl_(apx + s, apx + s, n - s, 1);
104 lmmp_inc_1(apx + s, cy2);
105 } else
106 apx[n] = 2 * cy + lmmp_addshl1_n_(apx, a3, apx, n);
107
108 lmmp_debug_assert(apx[n] < 15);
109
110 lmmp_sqr_(vh, apx, n + 1); /* vh, 2n+1 limbs */
111
112 /* Compute apx = a0 + a1 + a2 + a3 and amx = a0 - a1 + a2 - a3. */
114
115 lmmp_sqr_(v1, apx, n + 1); /* v1, 2n+1 limbs */
116 lmmp_sqr_(vm1, amx, n + 1); /* vm1, 2n+1 limbs */
117
118 lmmp_sqr_(v0, a0, n);
119 lmmp_sqr_(vinf, a3, s); /* vinf, 2s limbs */
120
121 lmmp_toom_interp7_(dst, n, (enum toom7_flags)0, vm2, vm1, v2, vh, 2 * s, tp);
123}
#define lmmp_sqr_
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
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
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_inc_1(p, inc)
加指定值宏(预期无进位)
void lmmp_sqr_toom4_(mp_ptr dst, mp_srcptr numa, mp_size_t an)
Toom-4平方运算 [dst,2*na] = [numa,na]^2
#define a0
#define a1
#define v0
#define vinf
#define vm1
#define a2
#define v1
#define v2
#define a3
#define tp
#define s
#define n
#define vm2
#define apx
#define vh
#define amx
#define scratch
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_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_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