LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
sqr_toom2.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 "impl/tmp_alloc.h"
26#include "lmmp/lmmpn.h"
27
28#define MAYBE_sqr_toom2 (SQR_TOOM33_THRESHOLD >= 2 * SQR_TOOM22_THRESHOLD)
29
30#define lmmp_sqr_(dst, numa, n) \
31 if (!MAYBE_sqr_toom2 || (n) < SQR_TOOM22_THRESHOLD) \
32 lmmp_sqr_hard_n_((dst), (numa), (n)); \
33 else \
34 lmmp_sqr_toom2_((dst), (numa), (n))
35
36/*
37Evaluate in: -1, 0, +inf
38
39 <-s--><--n-->
40 |-a1-|--a0--|
41
42v0 = a0 ^2 # A(0)^2
43vm1 = (a0-a1)^2 # A(-1)^2
44vinf= a1 ^2 # A(inf)^2
45*/
46
48 lmmp_param_assert(na > 3);
49 lmmp_param_assert(dst != NULL);
50 lmmp_param_assert(numa!= NULL);
52 mp_size_t s = na >> 1, n = na - s;
54 mp_slimb_t cy, cy2;
55
56#define a0 numa
57#define a1 (numa + n)
58#define asm1 dst
59
60 if (s == n) {
61 if (lmmp_cmp_(a0, a1, n) < 0)
63 else
65 } else { // s==n-1
66 if (a0[s] == 0 && lmmp_cmp_(a0, a1, s) < 0) {
68 asm1[s] = 0;
69 } else
70 asm1[s] = a0[s] - lmmp_sub_n_(asm1, a0, a1, s);
71 }
72
74
75#undef asm1
76#define v0 dst
77#define vinf (dst + 2 * n)
78
79 lmmp_sqr_(v0, a0, n);
80
81 lmmp_sqr_(vinf, a1, s);
82
83 cy = lmmp_add_n_(dst + 2 * n, v0 + n, vinf, n);
84 cy2 = cy + lmmp_add_n_(dst + n, dst + 2 * n, v0, n);
85 cy += lmmp_add_(dst + 2 * n, dst + 2 * n, n, vinf + n, s + s - n);
86
87 cy -= lmmp_sub_n_(dst + n, dst + n, vm1, 2 * n);
88
89 // no overflow.
90 lmmp_inc_1(dst + 2 * n, cy2);
91
92 if (cy < 0)
93 lmmp_dec(dst + 3 * n);
94 else
95 lmmp_inc_1(dst + 3 * n, cy);
97}
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
int64_t mp_slimb_t
定义 lmmp.h:94
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]
#define lmmp_dec(p)
减1宏(预期无借位)
void lmmp_sqr_toom2_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-2平方运算 [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_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
#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 a0
#define a1
#define v0
#define asm1
#define vinf
#define vm1
#define s
#define n
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define SALLOC_TYPE(n, type)
#define TEMP_S_DECL
#define TEMP_S_FREE