LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
remove.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/inlines.h
"
24
#include "
impl/tmp_alloc.h
"
25
#include "
lmmp/lmmpn.h
"
26
#include "
lmmp/numth.h
"
27
28
29
/*
30
事实上,我们可以知道,[np,nn]至多为[dp,dn]的2^64次方
31
2^64 - 1 - 2 - 4 - 8 - ... - 2^63 最为接近2^64
32
故,理论上MAX_EXP = 63
33
34
但是,实际上,[np,nn]几乎不可能超过[dp,dn]的2^48次方
35
2^48 - 1 - 2 - 4 - 8 - ... - 2^47 最为接近2^48
36
故,我们使用MAX_EXP = 48
37
*/
38
#define MAX_EXP 48
39
40
/**
41
* qp 为商,rp 为余数,divp 为被除数,divn 为被除数长度,numb 为除数,nb 为除数长度
42
* 如果无法整除,则返回0,否则返回除数 qp 的长度
43
*/
44
static
inline
mp_size_t
try_div_
(
mp_ptr
qp,
mp_ptr
rp
,
mp_srcptr
divp,
mp_size_t
divn,
mp_srcptr
numb
,
mp_size_t
nb) {
45
if
(divn < nb) {
46
return
0;
47
}
else
{
48
int
cmp;
49
if
(divn > nb)
50
cmp = 1;
51
else
52
cmp =
lmmp_cmp_
(divp,
numb
, nb);
53
if
(cmp == 0) {
54
qp[0] = 1;
55
return
1;
56
}
else
if
(cmp < 0) {
57
return
0;
58
}
else
{
59
// 拷贝原始数,当无法整除时,再进行恢复
60
lmmp_div_
(qp,
rp
, divp, divn,
numb
, nb);
61
if
(
lmmp_zero_q_
(
rp
, nb)) {
62
// 整除
63
divn = divn - nb + 1;
64
while
(divn > 0 && qp[divn - 1] == 0) --divn;
65
return
divn;
66
}
else
{
67
// 无法整除
68
return
0;
69
}
70
}
71
}
72
}
73
74
mp_size_t
lmmp_remove_
(
mp_ptr
np,
mp_size_t
*
restrict
nn,
mp_srcptr
dp,
mp_size_t
dn) {
75
lmmp_param_assert
(np != NULL && *nn > 0);
76
lmmp_param_assert
(dp != NULL && dn > 0);
77
lmmp_param_assert
(((dn - 1) | (dp[0] - 1)) != 0);
78
79
mp_srcptr
pd_pow[
MAX_EXP
];
80
mp_size_t
pn_pow[
MAX_EXP
];
81
// qp as quotient, rp as remainder, divp as divdend
82
mp_ptr
qp,
rp
, divp;
83
mp_ptr
prod
;
84
mp_size_t
divn = *nn, qn;
85
mp_size_t
ret = 0;
86
int
i, j;
87
pd_pow[0] = dp;
88
pn_pow[0] = dn;
89
90
TEMP_DECL
;
91
92
qp =
TALLOC_TYPE
(*nn,
mp_limb_t
);
93
rp
=
TALLOC_TYPE
(*nn,
mp_limb_t
);
94
95
divp = np;
96
97
for
(i = 1; i <
MAX_EXP
; i++) {
98
// if qn == 0, means cannot be divided by pd_pow[i - 1]
99
if
((qn =
try_div_
(qp,
rp
, divp, divn, pd_pow[i - 1], pn_pow[i - 1]))) {
100
divn = qn;
101
LMMP_SWAP
(qp, divp,
mp_ptr
);
102
103
ret += (
mp_size_t
)1 << (i - 1);
104
105
// 先计算下一次试除需要的 d^(2^i) 及其实际 limb 长度,
106
// 再判断是否继续。不能用 2*pn 代替实际长度。
107
prod
=
TALLOC_TYPE
(2 * pn_pow[i - 1],
mp_limb_t
);
108
lmmp_sqr_
(
prod
, pd_pow[i - 1], pn_pow[i - 1]);
109
pn_pow[i] = 2 * pn_pow[i - 1];
110
pn_pow[i] -= (
prod
[pn_pow[i] - 1] == 0) ? 1 : 0;
111
pd_pow[i] =
prod
;
112
113
if
(divn < pn_pow[i]) {
114
++i;
115
break
;
116
}
117
}
else
{
118
break
;
119
}
120
}
121
for
(j = i - 1; j > 0; --j) {
122
if
((qn =
try_div_
(qp,
rp
, divp, divn, pd_pow[j - 1], pn_pow[j - 1]))) {
123
divn = qn;
124
LMMP_SWAP
(qp, divp,
mp_ptr
);
125
126
ret += (
mp_size_t
)1 << (j - 1);
127
}
128
}
129
if
(qn == 0) {
130
// 无法整除:恢复为最后一次试除前的被除数
131
lmmp_copy
(np, divp, divn);
132
*nn = divn;
133
}
else
{
134
// 整除:商在最后一次 swap 后的 divp 中
135
lmmp_copy
(np, divp, qn);
136
*nn = qn;
137
}
138
139
TEMP_FREE
;
140
return
ret;
141
}
prod
#define prod
rp
#define rp
inlines.h
lmmp_sqr_
#define lmmp_sqr_
定义
inlines.h:168
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
LMMP_SWAP
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义
lmmp.h:458
lmmp_copy
#define lmmp_copy(dst, src, n)
定义
lmmp.h:474
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
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_cmp_
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义
cmp.c:26
lmmp_zero_q_
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义
cmp.c:55
lmmp_div_
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义
div.c:85
numb
#define numb
numth.h
lmmp_remove_
mp_size_t lmmp_remove_(mp_ptr np, mp_size_t *nn, mp_srcptr dp, mp_size_t dn)
除去 [np,nn] 中的 [dp,dn] 的因子
try_div_
static mp_size_t try_div_(mp_ptr qp, mp_ptr rp, mp_srcptr divp, mp_size_t divn, mp_srcptr numb, mp_size_t nb)
qp 为商,rp 为余数,divp 为被除数,divn 为被除数长度,numb 为除数,nb 为除数长度 如果无法整除,则返回0,否则返回除数 qp 的长度
定义
remove.c:44
MAX_EXP
#define MAX_EXP
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
remove.c:38
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
tmp_alloc.h
TEMP_DECL
#define TEMP_DECL
定义
tmp_alloc.h:145
TEMP_FREE
#define TEMP_FREE
定义
tmp_alloc.h:175
TALLOC_TYPE
#define TALLOC_TYPE(n, type)
定义
tmp_alloc.h:173
src
lmmp
numth
remove.c
生成于
, 为 LMMP使用
1.18.0