LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
remove.c 文件参考
#include "impl/inlines.h"
#include "impl/tmp_alloc.h"
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
remove.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define MAX_EXP   48
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

mp_size_t lmmp_remove_ (mp_ptr np, mp_size_t *restrict nn, mp_srcptr dp, mp_size_t 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 的长度

宏定义说明

◆ MAX_EXP

#define MAX_EXP   48

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 remove.c 第 38 行定义.

被这些函数引用 lmmp_remove_().

函数说明

◆ lmmp_remove_()

mp_size_t lmmp_remove_ ( mp_ptr np,
mp_size_t *restrict nn,
mp_srcptr dp,
mp_size_t dn )

在文件 remove.c 第 74 行定义.

74 {
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
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 TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 lmmp_copy, lmmp_param_assert, lmmp_remove_(), lmmp_sqr_, LMMP_SWAP, MAX_EXP, prod, restrict, rp, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 try_div_().

函数调用图:

◆ try_div_()

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 )
inlinestatic

qp 为商,rp 为余数,divp 为被除数,divn 为被除数长度,numb 为除数,nb 为除数长度 如果无法整除,则返回0,否则返回除数 qp 的长度

在文件 remove.c 第 44 行定义.

44 {
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}
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

引用了 lmmp_cmp_(), lmmp_div_(), lmmp_zero_q_(), numb, rp , 以及 try_div_().

被这些函数引用 lmmp_remove_() , 以及 try_div_().

函数调用图:
这是这个函数的调用关系图: