LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
div_basecase.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/longlong.h
"
24
#include "mparam.h"
25
#include "
lmmp/lmmpn.h
"
26
27
28
mp_limb_t
lmmp_div_basecase_
(
29
mp_ptr
restrict
dstq,
30
mp_ptr
restrict
numa,
31
mp_size_t
na,
32
mp_srcptr
restrict
numb
,
33
mp_size_t
nb,
34
mp_limb_t
inv21
35
) {
36
lmmp_param_assert
(na >= nb);
37
lmmp_param_assert
(nb >= 3);
38
lmmp_param_assert
(dstq != NULL && numa != NULL &&
numb
!= NULL);
39
lmmp_param_assert
(
numb
[nb - 1] >=
LIMB_B_2
);
40
mp_size_t
nq = na - nb;
41
42
numa += na;
43
44
mp_limb_t
qh =
lmmp_cmp_
(numa - nb,
numb
, nb) >= 0;
45
if
(qh) {
46
lmmp_sub_n_
(numa - nb, numa - nb,
numb
, nb);
47
}
48
49
nb -= 2;
50
numa -= 2;
51
52
mp_limb_t
d1 =
numb
[nb + 1], d0 =
numb
[nb + 0];
53
mp_limb_t
rh = numa[1], rl = numa[0];
54
55
while
(nq) {
56
mp_limb_t
q;
57
--numa;
58
if
(rh == d1 && rl == d0) {
59
q =
LIMB_MAX
;
60
numa[1] = rl;
61
lmmp_submul_1_
(numa - nb,
numb
, nb + 2, q);
62
rh = numa[1];
63
rl = numa[0];
64
}
else
{
65
mp_limb_t
cy, cy1,
r0
,
r1
, n0 = numa[0];
66
_udiv_qr_3by2
(q,
r1
,
r0
, rh, rl, n0, d1, d0, inv21);
67
cy =
lmmp_submul_1_
(numa - nb,
numb
, nb, q);
68
cy1 =
r0
< cy;
69
r0
-= cy;
70
cy =
r1
< cy1;
71
r1
-= cy1;
72
if
(cy) {
73
numa[0] =
r0
;
74
numa[1] =
r1
;
75
lmmp_add_n_
(numa - nb, numa - nb,
numb
, nb + 2);
76
rh = numa[1];
77
rl = numa[0];
78
--q;
79
}
else
{
80
rh =
r1
;
81
rl =
r0
;
82
}
83
}
84
dstq[--nq] = q;
85
}
86
numa[1] = rh;
87
numa[0] = rl;
88
return
qh;
89
}
LIMB_B_2
#define LIMB_B_2
定义
mparam.h:40
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
LIMB_MAX
#define LIMB_MAX
定义
lmmp.h:105
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_submul_1_
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
定义
mul_1.c:131
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_div_basecase_
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)
基础除法运算
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
longlong.h
_udiv_qr_3by2
#define _udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)
定义
longlong.h:634
r1
#define r1
r0
#define r0
numb
#define numb
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
src
lmmp
lmmpn
div_basecase.c
生成于
, 为 LMMP使用
1.18.0