LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
div.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 "mparam.h"
25#include "impl/tmp_alloc.h"
26#include "lmmp/lmmpn.h"
27
28
30 mp_ptr restrict dstq,
31 mp_ptr restrict numa,
32 mp_size_t na,
34 mp_size_t nb
35) {
36 lmmp_param_assert(na >= nb && nb > 0);
37 lmmp_param_assert(numa != NULL && numb != NULL && dstq != NULL);
39
41 mp_limb_t nq = na - nb;
42 mp_limb_t qh;
43 if (nq == 0) {
44 qh = lmmp_cmp_(numa, numb, nb) >= 0;
45 if (qh)
46 lmmp_sub_n_(numa, numa, numb, nb);
47 } else if (nb == 1) {
48 qh = lmmp_div_1_s_(dstq, numa, na, *numb);
49 } else if (nb == 2) {
50 qh = lmmp_div_2_s_(dstq, numa, na, numb);
51 } else if (nq < nb) {
52 qh = lmmp_div_s_(dstq, numa + na - 2 * nq, 2 * nq, numb + nb - nq, nq);
53
55 if (nq > nb - nq)
56 lmmp_mul_(tp, dstq, nq, numb, nb - nq);
57 else
58 lmmp_mul_(tp, numb, nb - nq, dstq, nq);
59
60 mp_limb_t cy = lmmp_sub_n_(numa, numa, tp, nb);
61 if (qh)
62 cy += lmmp_sub_n_(numa + nq, numa + nq, numb, nb - nq);
63
64 while (cy) {
65 qh -= lmmp_sub_1_(dstq, dstq, nq, 1);
66 cy -= lmmp_add_n_(numa, numa, numb, nb);
67 }
68 } else {
69 mp_limb_t inv21 = lmmp_inv_2_1_(numb[nb - 1], numb[nb - 2]);
70 if (nb < DIV_DIVIDE_THRESHOLD)
71 qh = lmmp_div_basecase_(dstq, numa, na, numb, nb, inv21);
72 else if (nb < DIV_MULINV_L_THRESHOLD || na < 2 * DIV_MULINV_N_THRESHOLD)
73 qh = lmmp_div_divide_(dstq, numa, na, numb, nb, inv21);
74 else {
75 mp_limb_t ni = lmmp_div_inv_size_(nq, nb);
76 mp_ptr restrict invappr = TALLOC_TYPE(ni, mp_limb_t);
77 lmmp_inv_prediv_(invappr, numb, nb, ni);
78 qh = lmmp_div_mulinv_(dstq, numa, na, numb, nb, invappr, ni);
79 }
80 }
82 return qh;
83}
84
86 lmmp_param_assert(na >= nb);
87 lmmp_param_assert(numa != NULL && numb != NULL && nb > 0);
88 lmmp_param_assert(numb[nb - 1] > 0);
89 if (nb == 1) {
90 mp_limb_t rem = lmmp_div_1_(dstq, numa, na, *numb);
91 if (dstr)
92 *dstr = rem;
93 } else if (nb == 2) {
94 mp_limb_t brem[2];
95 brem[0] = numb[0];
96 brem[1] = numb[1];
97 lmmp_div_2_(dstq, numa, na, brem);
98 if (dstr) {
99 dstr[0] = brem[0];
100 dstr[1] = brem[1];
101 }
102 } else {
103 int adjust = numa[na - 1] >= numb[nb - 1];
104 int cnt = lmmp_leading_zeros_(numb[nb - 1]);
105 mp_size_t nq = na + adjust - nb;
106 if (nq == 0) {
107 if (dstr && dstr != numa)
108 lmmp_copy(dstr, numa, nb);
109 if (dstq)
110 dstq[0] = 0;
111 return;
112 }
113 TEMP_DECL;
114
115 if (!dstq)
116 dstq = TALLOC_TYPE(na - nb + 1, mp_limb_t);
117 dstq[na - nb] = 0;
118
119 if (nq >= nb) {
120 mp_ptr restrict numa2 = TALLOC_TYPE(na + 1, mp_limb_t);
121 mp_ptr numb2;
122 if (cnt) {
123 numa2[na] = lmmp_shl_(numa2, numa, na, cnt);
124 numb2 = TALLOC_TYPE(nb, mp_limb_t);
125 lmmp_shl_(numb2, numb, nb, cnt);
126 } else {
127 numa2[na] = 0;
128 lmmp_copy(numa2, numa, na);
129 numb2 = (mp_ptr)numb;
130 }
131
132 mp_limb_t inv21 = lmmp_inv_2_1_(numb2[nb - 1], numb2[nb - 2]);
133 na += adjust;
134
135 if (nb < DIV_DIVIDE_THRESHOLD)
136 lmmp_div_basecase_(dstq, numa2, na, numb2, nb, inv21);
137 else if (nb < DIV_MULINV_L_THRESHOLD || na < 2 * DIV_MULINV_N_THRESHOLD)
138 lmmp_div_divide_(dstq, numa2, na, numb2, nb, inv21);
139 else {
140 mp_limb_t ni = lmmp_div_inv_size_(nq, nb);
141 mp_ptr invappr = TALLOC_TYPE(ni, mp_limb_t);
142 lmmp_inv_prediv_(invappr, numb2, nb, ni);
143 lmmp_div_mulinv_(dstq, numa2, na, numb2, nb, invappr, ni);
144 }
145
146 if (dstr) {
147 lmmp_shr_(dstr, numa2, nb, cnt); // cnt=0 时函数内即整段拷贝
148 }
149 } else {
150 // nq=na-nb+adj<nb
151 //-> na+adj>=2nq+1
152 mp_size_t ni = nb - nq;
153 mp_ptr numa2, numb2;
155 mp_limb_t cy;
156
157 numa2 = TALLOC_TYPE(nq * 2 + 1, mp_limb_t);
158 if (cnt) {
159 numb2 = TALLOC_TYPE(nq, mp_limb_t);
160 lmmp_shl_(numb2, numb + ni, nq, cnt);
161 numb2[0] |= numb[ni - 1] >> (LIMB_BITS - cnt);
162 cy = lmmp_shl_(numa2, numa + na - 2 * nq, 2 * nq, cnt);
163 if (adjust) {
164 numa2[2 * nq] = cy;
165 ++numa2; // numa2[0] is as significant as numa[ni=na-2nq+adjust]
166 } else
167 numa2[0] |= numa[na - 2 * nq - 1] >> (LIMB_BITS - cnt);
168 } else {
169 numb2 = (mp_ptr)numb + ni;
170 lmmp_copy(numa2, numa + na - 2 * nq, 2 * nq);
171 if (adjust) {
172 numa2[2 * nq] = 0;
173 ++numa2;
174 }
175 }
176
177 // now: 0<=numa2<B^2nq, B^nq/2<=numb2<B^nq, and 0<=numa2/numb2<B^nq
178 // ignored bits could be seen as fraction part of numa and numb
179 // we can prove: Q<=Qh<=Q+2
180 // where Q=floor(numa/numb) is the real quotient
181 // Qh=floor(floor(numa)/floor(numb)) as below
182
183 if (nq == 1) {
184 lmmp_div_1_s_(dstq, numa2, 2, *numb2);
185 } else if (nq == 2) {
186 lmmp_div_2_s_(dstq, numa2, 4, numb2);
187 } else {
188 mp_limb_t inv21 = lmmp_inv_2_1_(numb2[nq - 1], numb2[nq - 2]);
189
190 if (nq < DIV_DIVIDE_THRESHOLD)
191 lmmp_div_basecase_(dstq, numa2, 2 * nq, numb2, nq, inv21);
192 else if (nq < DIV_MULINV_N_THRESHOLD)
193 lmmp_div_divide_(dstq, numa2, 2 * nq, numb2, nq, inv21);
194 else {
195 mp_size_t inv_ni = lmmp_div_inv_size_(nq, nq);
196 mp_ptr invappr = tp;
197 lmmp_inv_prediv_(invappr, numb2, nq, inv_ni);
198 lmmp_div_mulinv_(dstq, numa2, 2 * nq, numb2, nq, invappr, inv_ni);
199 }
200 }
201 /*
202 true remainder = partial remainder - quotient * ignored divisor limbs
203
204 Multiply the first ignored divisor limb by the most significant
205 quotient limb. If that product is > the partial remainder's
206 most significant limb, we know the quotient is too large. This
207 test quickly catches most cases where the quotient is too large;
208 it catches all cases where the quotient is 2 too large.*/
209
210 mp_limb_t x;
211 if (cnt) {
212 mp_limb_t dl;
213 if (ni < 2)
214 dl = 0;
215 else
216 dl = numb[ni - 2];
217 x = (numb[ni - 1] << cnt) | (dl >> (LIMB_BITS - cnt));
218 } else
219 x = numb[ni - 1];
220 mp_limb_t h = (x >> LIMB_BITS / 2) * (dstq[nq - 1] >> LIMB_BITS / 2);
221 mp_limb_t rnb = 0; // remainder[nb]
222 mp_size_t nr = nq; // remainder=rnb:[numa2,nr]:[...,ni]
223
224 if (h > numa2[nq - 1]) {
225 lmmp_dec(dstq);
226 rnb = lmmp_add_n_(numa2, numa2, numb2, nq);
227 }
228
229 // if cnt, recover the shift of partial remainder
230 // and remove the effect of the partial-ignored numa[ni-1] and numb[ni-1]
231 if (cnt) {
232 numa2[nq] = rnb;
233 ++nr;
234 --ni;
235 lmmp_shl_(numa2, numa2, nr, LIMB_BITS - cnt);
236 numa2[0] |= numa[ni] & (LIMB_MAX >> cnt);
237 cy = lmmp_submul_1_(numa2, dstq, nq, numb[ni] & (LIMB_MAX >> cnt));
238 rnb = -(numa2[nq] < cy);
239 numa2[nq] -= cy;
240 }
241
242 if (ni == 0) {
243 if (dstr) {
244 if (rnb)
245 lmmp_add_n_(dstr, numa2, numb, nr);
246 else
247 lmmp_copy(dstr, numa2, nr);
248 }
249 } else {
250 tp[nb - 1] = 0;
251 if (ni < nq)
252 lmmp_mul_(tp, dstq, nq, numb, ni);
253 else
254 lmmp_mul_(tp, numb, ni, dstq, nq);
255
256 if (dstr) {
257 mp_ptr remptr = dstr == numb ? tp : dstr;
258 cy = lmmp_sub_n_(remptr, numa, tp, ni);
259 rnb -= lmmp_sub_nc_(remptr + ni, numa2, tp + ni, nr, cy);
260 if (rnb)
261 lmmp_add_n_(dstr, remptr, numb, nb);
262 else if (dstr != remptr)
263 lmmp_copy(dstr, remptr, nb);
264 } else {
265 int hcmp = lmmp_cmp_(numa2, tp + ni, nr);
266 if (hcmp < 0)
267 --rnb;
268 else if (hcmp == 0)
269 rnb -= (lmmp_cmp_(numa, tp, ni) < 0);
270 }
271 }
272
273 if (rnb)
274 lmmp_dec(dstq);
275 }
276
277 TEMP_FREE;
278 }
279}
#define lmmp_leading_zeros_
#define LIMB_B_2
mp_limb_t * mp_ptr
定义 lmmp.h:96
#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
#define LIMB_MAX
定义 lmmp.h:105
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define DIV_DIVIDE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define DIV_MULINV_N_THRESHOLD
#define DIV_MULINV_L_THRESHOLD
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
static mp_size_t lmmp_div_inv_size_(mp_size_t nq, mp_size_t nb)
计算预计算逆元的尺寸
mp_limb_t lmmp_div_1_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_limb_t x)
单精度数除法(除数为1个limb)
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
#define lmmp_dec(p)
减1宏(预期无借位)
void lmmp_inv_prediv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t ni)
除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B
void lmmp_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
定义 div.c:294
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
mp_limb_t lmmp_div_mulinv_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_srcptr invappr, mp_size_t ni)
乘法逆元除法
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
mp_limb_t lmmp_div_2_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb)
双精度数除法(除数为2个limb)
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
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
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
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
定义 inv.c:27
mp_limb_t lmmp_div_basecase_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
基础除法运算
mp_limb_t lmmp_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
定义 sub_n.c:67
mp_limb_t lmmp_div_divide_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
分治除法运算
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 numb
#define tp
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)