LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
inv.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 "
lmmp/lmmpn.h
"
25
26
27
mp_limb_t
lmmp_inv_2_1_
(
mp_limb_t
xh,
mp_limb_t
xl) {
28
mp_limb_t
r, m;
29
{
30
mp_limb_t
p, ql;
31
unsigned
ul, uh, qh;
32
33
/* For notation, let b denote the half-limb base, so that B = b^2.
34
Split u1 = b uh + ul. */
35
ul = xh &
LLIMB_MASK
;
36
uh = xh >> (
LIMB_BITS
/ 2);
37
38
/* Approximation of the high half of quotient. Differs from the 2/1
39
inverse of the half limb uh, since we have already subtracted
40
u0. */
41
qh = (xh ^
LIMB_MAX
) / uh;
42
43
/* Adjust to get a half-limb 3/2 inverse, i.e., we want
44
45
qh' = floor( (b^3 - 1) / u) - b = floor ((b^3 - b u - 1) / u
46
= floor( (b (~u) + b-1) / u),
47
48
and the remainder
49
50
r = b (~u) + b-1 - qh (b uh + ul)
51
= b (~u - qh uh) + b-1 - qh ul
52
53
Subtraction of qh ul may underflow, which implies adjustments.
54
But by normalization, 2 u >= B > qh ul, so we need to adjust by
55
at most 2.
56
*/
57
58
r = ((~xh - (
mp_limb_t
)qh * uh) << (
LIMB_BITS
/ 2)) |
LLIMB_MASK
;
59
60
p = (
mp_limb_t
)qh * ul;
61
/* Adjustment steps taken from udiv_qrnnd_c */
62
if
(r < p) {
63
qh--;
64
r += xh;
65
if
(r >= xh)
/* i.e. we didn't get carry when adding to r */
66
if
(r < p) {
67
qh--;
68
r += xh;
69
}
70
}
71
r -= p;
72
73
/* Low half of the quotient is
74
75
ql = floor ( (b r + b-1) / u1).
76
77
This is a 3/2 division (on half-limbs), for which qh is a
78
suitable inverse. */
79
80
p = (r >> (
LIMB_BITS
/ 2)) * qh + r;
81
/* Unlike full-limb 3/2, we can add 1 without overflow. For this to
82
work, it is essential that ql is a full mp_limb_t. */
83
ql = (p >> (
LIMB_BITS
/ 2)) + 1;
84
85
/* By the 3/2 trick, we don't need the high half limb. */
86
r = (r << (
LIMB_BITS
/ 2)) +
LLIMB_MASK
- ql * xh;
87
88
if
(r >= (
LIMB_MAX
& (p << (
LIMB_BITS
/ 2)))) {
89
ql--;
90
r += xh;
91
}
92
m = ((
mp_limb_t
)qh << (
LIMB_BITS
/ 2)) + ql;
93
if
(r >= xh) {
94
m++;
95
r -= xh;
96
}
97
}
98
99
/* Now m is the 2/1 inverse of u1. If u0 > 0, adjust it to become a
100
3/2 inverse. */
101
if
(xl > 0) {
102
mp_limb_t
th, tl;
103
r = ~r;
104
r += xl;
105
if
(r < xl) {
106
m--;
107
if
(r >= xh) {
108
m--;
109
r -= xh;
110
}
111
r -= xh;
112
}
113
_umul64to128_
(xl, m, &tl, &th);
114
r += th;
115
if
(r < th) {
116
m--;
117
m -= ((r > xh) | ((r == xh) & (tl > xl)));
118
}
119
}
120
121
return
m;
122
}
123
124
mp_limb_t
lmmp_inv_1_
(
mp_limb_t
x) {
125
mp_limb_t
r, m;
126
{
127
mp_limb_t
p, ql;
128
unsigned
ul, uh, qh;
129
130
ul = x &
LLIMB_MASK
;
131
uh = x >> (
LIMB_BITS
/ 2);
132
qh = (x ^
LIMB_MAX
) / uh;
133
134
r = ((~x - (
mp_limb_t
)qh * uh) << (
LIMB_BITS
/ 2)) |
LLIMB_MASK
;
135
p = (
mp_limb_t
)qh * ul;
136
if
(r < p) {
137
qh--;
138
r += x;
139
if
(r >= x)
140
if
(r < p) {
141
qh--;
142
r += x;
143
}
144
}
145
r -= p;
146
p = (r >> (
LIMB_BITS
/ 2)) * qh + r;
147
ql = (p >> (
LIMB_BITS
/ 2)) + 1;
148
r = (r << (
LIMB_BITS
/ 2)) +
LLIMB_MASK
- ql * x;
149
if
(r >= (
LIMB_MAX
& (p << (
LIMB_BITS
/ 2)))) {
150
ql--;
151
r += x;
152
}
153
m = ((
mp_limb_t
)qh << (
LIMB_BITS
/ 2)) + ql;
154
if
(r >= x) {
155
m++;
156
r -= x;
157
}
158
}
159
return
m;
160
}
LLIMB_MASK
#define LLIMB_MASK
定义
lmmp.h:108
LIMB_MAX
#define LIMB_MAX
定义
lmmp.h:105
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
LIMB_BITS
#define LIMB_BITS
定义
lmmp.h:102
lmmpn.h
lmmp_inv_1_
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义
inv.c:124
lmmp_inv_2_1_
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
定义
inv.c:27
longlong.h
_umul64to128_
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
定义
longlong.h:132
src
lmmp
lmmpn
arch
generic
inv.c
生成于
, 为 LMMP使用
1.18.0