LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
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
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}
#define LLIMB_MASK
定义 lmmp.h:108
#define LIMB_MAX
定义 lmmp.h:105
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
定义 inv.c:27
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)