LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
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
/*
37
Evaluate in: -1, 0, +inf
38
39
<-s--><--n-->
40
|-a1-|--a0--|
41
42
v0 = a0 ^2 # A(0)^2
43
vm1 = (a0-a1)^2 # A(-1)^2
44
vinf= a1 ^2 # A(inf)^2
45
*/
46
47
void
lmmp_sqr_toom2_
(
mp_ptr
restrict
dst,
mp_srcptr
restrict
numa,
mp_size_t
na) {
48
lmmp_param_assert
(na > 3);
49
lmmp_param_assert
(dst != NULL);
50
lmmp_param_assert
(numa!= NULL);
51
TEMP_S_DECL
;
52
mp_size_t
s
= na >> 1,
n
= na -
s
;
53
mp_limb_t
*
vm1
=
SALLOC_TYPE
(2 *
n
,
mp_limb_t
);
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)
62
lmmp_sub_n_
(
asm1
,
a1
,
a0
,
n
);
63
else
64
lmmp_sub_n_
(
asm1
,
a0
,
a1
,
n
);
65
}
else
{
// s==n-1
66
if
(
a0
[
s
] == 0 &&
lmmp_cmp_
(
a0
,
a1
,
s
) < 0) {
67
lmmp_sub_n_
(
asm1
,
a1
,
a0
,
s
);
68
asm1
[
s
] = 0;
69
}
else
70
asm1
[
s
] =
a0
[
s
] -
lmmp_sub_n_
(
asm1
,
a0
,
a1
,
s
);
71
}
72
73
lmmp_sqr_
(
vm1
,
asm1
,
n
);
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);
96
TEMP_S_FREE
;
97
}
lmmp_sqr_
#define lmmp_sqr_
定义
inlines.h:168
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_slimb_t
int64_t mp_slimb_t
定义
lmmp.h:94
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
lmmp_add_
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]
定义
lmmpn.h:1206
lmmp_dec
#define lmmp_dec(p)
减1宏(预期无借位)
定义
lmmpn.h:1133
lmmp_sqr_toom2_
void lmmp_sqr_toom2_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-2平方运算 [dst,2*na] = [numa,na]^2
lmmp_cmp_
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义
cmp.c:26
lmmp_sub_n_
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
lmmp_inc_1
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
定义
lmmpn.h:1118
lmmp_add_n_
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
mul_hard.h
a0
#define a0
a1
#define a1
v0
#define v0
asm1
#define asm1
vinf
#define vinf
vm1
#define vm1
s
#define s
n
#define n
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
tmp_alloc.h
SALLOC_TYPE
#define SALLOC_TYPE(n, type)
定义
tmp_alloc.h:169
TEMP_S_DECL
#define TEMP_S_DECL
定义
tmp_alloc.h:153
TEMP_S_FREE
#define TEMP_S_FREE
定义
tmp_alloc.h:191
src
lmmp
lmmpn
sqr_toom2.c
生成于
, 为 LMMP使用
1.18.0