LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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次方
312^64 - 1 - 2 - 4 - 8 - ... - 2^63 最为接近2^64
32故,理论上MAX_EXP = 63
33
34但是,实际上,[np,nn]几乎不可能超过[dp,dn]的2^48次方
352^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 */
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
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;
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
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}
#define prod
#define rp
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
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
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
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
#define numb
mp_size_t lmmp_remove_(mp_ptr np, mp_size_t *nn, mp_srcptr dp, mp_size_t dn)
除去 [np,nn] 中的 [dp,dn] 的因子
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 的长度
#define MAX_EXP
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)