LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
sqr_toom3.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#include "lmmp/lmmpn.h"
27
28#define MAYBE_sqr_toom3 (SQR_TOOM44_THRESHOLD >= 3 * SQR_TOOM33_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_toom3 || (n) < SQR_TOOM33_THRESHOLD) \
34 lmmp_sqr_toom2_((dst), (numa), (n)); \
35 else \
36 lmmp_sqr_toom3_((dst), (numa), (n))
37
38/*
39Evaluate in: -1, 0, +1, +2, +inf
40
41 <-s--><--n--><--n-->
42 |-a2-|--a1--|--a0--|
43
44v0 = a0 *^2 # A(0)^2
45v1 = (a0+ a1+ a2)*^2 # A(1)^2 ah <= 2
46vm1 = (a0- a1+ a2)*^2 # A(-1)^2 |ah| <= 1
47v2 = (a0+2a1+4a2)*^2 # A(2)^2 ah <= 6
48vinf= a2 *^2 # A(inf)^2
49*/
50
52 lmmp_param_assert(na > 4);
53 lmmp_param_assert(numa != NULL);
54 lmmp_param_assert(dst != NULL);
56 mp_size_t n = (na + 2) / 3, s = na - 2 * n;
57 mp_limb_t cy, cy2, vinf0, am1h;
59
60#define a0 numa
61#define a1 (numa + n)
62#define a2 (numa + 2 * n)
63
64#define v0 dst //[dst,2*n]
65#define v1 (dst + 2 * n) //[dst+2*n,2*n+1]
66#define vinf (dst + 4 * n) //[dst+4*n,s+t]
67#define vm1 tp //[tp,2*n+1]
68#define v2 (tp + 2 * n + 2) //[tp+2*n+2,2*n+1]
69
70#define am1 (dst) //[dst,n]
71#define ap1 tp //[tp,n+1]
72#define ap2 ap1 // same space
73
74 // ap1, am1
75 cy = lmmp_add_(ap1, a0, n, a2, s);
76 if (cy == 0 && lmmp_cmp_(ap1, a1, n) < 0) {
77 cy = lmmp_add_n_sub_n_(ap1, am1, a1, ap1, n);
78 ap1[n] = cy >> 1;
79 am1h = 0;
80 } else {
81 cy2 = lmmp_add_n_sub_n_(ap1, am1, ap1, a1, n);
82 ap1[n] = cy + (cy2 >> 1);
83 am1h = cy - (cy2 & 1);
84 }
85
86 // vinf
87 lmmp_sqr_(vinf, a2, s);
88 vinf0 = vinf[0]; // overlap with v1
89 cy = vinf[1]; // overlap with v1
90
91 // v1
92 lmmp_sqr_(v1, ap1, n + 1);
93 vinf[1] = cy; // restore, since v1[2*n+1]==0.
94
95 // ap2
96 cy = lmmp_addshl1_n_(ap2, a1, a2, s);
97 if (s != n)
98 cy = lmmp_add_1_(ap2 + s, a1 + s, n - s, cy);
99 cy = 2 * cy + lmmp_addshl1_n_(ap2, a0, ap2, n);
100 ap2[n] = cy;
101
102 // v2
103 lmmp_sqr_(v2, ap2, n + 1);
104
105 // vm1
106 lmmp_sqr_(vm1, am1, n);
107 if (am1h)
108 am1h += lmmp_addshl1_n_(vm1 + n, vm1 + n, am1, n);
109 vm1[2 * n] = am1h;
110
111 // v0
112 lmmp_sqr_(v0, a0, n);
113
114 lmmp_toom_interp5_(dst, v2, vm1, n, s + s, 0, vinf0);
116}
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
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]
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_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
void lmmp_sqr_toom3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-3平方运算 [dst,2*na] = [numa,na]^2
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
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 a0
#define a1
#define v0
#define vinf
#define am1
#define ap1
#define vm1
#define a2
#define v1
#define ap2
#define v2
#define tp
#define s
#define n
void lmmp_toom_interp5_(mp_ptr dst, mp_ptr v2, mp_ptr vm1, mp_size_t n, mp_size_t spt, int vm1_neg, mp_limb_t vinf0)
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