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

浏览该文件的源代码.

函数

mp_limb_t lmmp_inv_1_ (mp_limb_t x)
 1阶逆元计算 (inv1)
mp_limb_t lmmp_inv_2_1_ (mp_limb_t xh, mp_limb_t xl)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ lmmp_inv_1_()

mp_limb_t lmmp_inv_1_ ( mp_limb_t x)

1阶逆元计算 (inv1)

参数
x输入的64位无符号整数,最高位为1(MSB(x)=1)
返回
计算结果:(B^2-1)/x - B
警告
MSB(x)=1, 即x>=2^63

在文件 inv.c 第 124 行定义.

124 {
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

引用了 LIMB_BITS, LIMB_MAX, LLIMB_MASK , 以及 lmmp_inv_1_().

被这些函数引用 bench_inv_1(), lmmp_div_1_(), lmmp_div_1_s_(), lmmp_inv_1_(), lmmp_inv_basecase_(), lmmp_mod_1_(), lmmp_mulmod_ulong_(), lmmp_sqrlo_dc_(), mont_R2(), mont_R2(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), trialdiv_init_chunk_() , 以及 trialdiv_init_inv_().

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

◆ lmmp_inv_2_1_()

mp_limb_t lmmp_inv_2_1_ ( mp_limb_t xh,
mp_limb_t xl )

Copyright (C) 2026 HJimmyK (Jericho Knox)

2-1阶逆元计算 (inv21)

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

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
xh输入数的高64位部分
xl输入数的低64位部分
返回
计算结果:(B^3-1)/(xh*B+xl) - B
警告
MSB(xh)=1, 即xh>=2^63

在文件 inv.c 第 27 行定义.

27 {
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}
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)

引用了 _umul64to128_(), LIMB_BITS, LIMB_MAX, LLIMB_MASK , 以及 lmmp_inv_2_1_().

被这些函数引用 bench_div_3_2(), bench_inv_2_1(), ipn_sdiv_init_(), lmmp_bninv_appr_newton_(), lmmp_div_(), lmmp_div_2_(), lmmp_div_2_s_(), lmmp_div_s_(), lmmp_inv_2_1_(), lmmp_inv_basecase_(), lmmp_mod_2_(), lmmp_sqrlo_dc_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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