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

浏览该文件的源代码.

宏定义

#define k   (k + 2)
#define k   (k[2])
#define xn   (dst)
#define xn   (dst[0])

函数

static void _umul128to192_ (uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[3])
void lmmp_binvert_2_ (mp_ptr dst, mp_srcptr numa)
 计算 [numa,2] 在 B^2 下的逆元
void lmmp_binvert_3_ (mp_ptr restrict dst, mp_srcptr restrict numa)
void lmmp_binvert_4_ (mp_ptr restrict dst, mp_srcptr restrict numa)
uint lmmp_binvert_uint_ (uint a)
 计算 a 在2^32下的逆元
ulong lmmp_binvert_ulong_ (ulong a)
 计算 a 在2^64下的逆元
void lmmp_binvert_unbalance_1_ (mp_ptr restrict dst, mp_limb_t a, mp_size_t n)
void lmmp_binvert_unbalance_2_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t n)

变量

static const uchar binv_tab [128]
 Copyright (C) 2026 HJimmyK (Jericho Knox)

宏定义说明

◆ k [1/2]

#define k   (k + 2)

◆ k [2/2]

#define k   (k[2])

◆ xn [1/2]

#define xn   (dst)

◆ xn [2/2]

函数说明

◆ _umul128to192_()

void _umul128to192_ ( uint64_t a_high,
uint64_t a_low,
uint64_t b_high,
uint64_t b_low,
uint64_t rr[3] )
inlinestatic

在文件 binvert_1.c 第 86 行定义.

86 {
87 /*
88 | res0 | res1 | res2 |
89 | p0l | p0h | |
90 | p1l | p1h |
91 | p2l | p2h |
92 | | p3l |
93 */
94#if defined(__SIZEOF_INT128__)
95 // 128 位累加让进位自然落在寄存器对高位,编译器生成 add/adc 链;
96 // rr[2] 为 192 位截断结果,hi 的进一步进位按定义舍弃
97 __uint128_t p0 = (__uint128_t)a_low * b_low;
98 __uint128_t p1 = (__uint128_t)a_low * b_high;
99 __uint128_t p2 = (__uint128_t)a_high * b_low;
100 __uint128_t mid = (p0 >> 64) + (uint64_t)p1 + (uint64_t)p2; // mid>>64 ∈ {0,1,2}
101 __uint128_t hi = (p1 >> 64) + (p2 >> 64) + a_high * b_high + (uint64_t)(mid >> 64);
102 rr[0] = (uint64_t)p0;
103 rr[1] = (uint64_t)mid;
104 rr[2] = (uint64_t)hi;
105#else
106 uint64_t p1_low, p1_high; // p1 = a_low × b_high
107 uint64_t p2_low, p2_high; // p2 = a_high × b_low
108 _umul64to128_(a_low, b_low, rr, rr + 1);
109 _umul64to128_(a_low, b_high, &p1_low, &p1_high);
110 _umul64to128_(a_high, b_low, &p2_low, &p2_high);
111 rr[1] += p1_low;
112 uint64_t carry = (rr[1] < p1_low) ? 1 : 0;
113 rr[1] += p2_low;
114 carry += (rr[1] < p2_low) ? 1 : 0;
115
116 rr[2] = a_high * b_high;
117 rr[2] += carry;
118 rr[2] += p1_high;
119 rr[2] += p2_high;
120#endif
121}
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)

引用了 _umul128to192_() , 以及 _umul64to128_().

被这些函数引用 _umul128to192_() , 以及 lmmp_binvert_3_().

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

◆ lmmp_binvert_2_()

void lmmp_binvert_2_ ( mp_ptr dst,
mp_srcptr numa )

计算 [numa,2] 在 B^2 下的逆元

参数
numa待求逆元指针(长度为 2 个limb)
dst结果指针(长度为 2 个limb)
警告
numa!=NULL, dst!=NULL, numa[0]%2==1, eqsep(dst,numa)

在文件 binvert_1.c 第 63 行定义.

63 {
64 lmmp_param_assert(dst != NULL && numa != NULL);
65 lmmp_param_assert(numa[0] % 2 == 1);
66 mp_limb_t k, t;
67 mp_limb_t a1 = numa[1];
68 mp_limb_t a0 = numa[0];
70 mp_limb_t z;
71 /*
72 xn * a0 == 1 + k * B
73 yn := xn * (2 - a * xn) mod B^2
74 := xn * (2 - a0 * xn - a1 * xn * B) mod B^2
75 := xn * (2 - 1 - k*B - a1 * xn * B) mod B^2
76 := xn * (1 - k*B - a1 * xn * B) mod B^2
77 := (xn - xn*k * B - a1 * xn^2 * B) mod B^2
78 */
79 _umul64to128_(a0, xn, &t, &k);
80 z = xn * k;
81 z += a1 * xn * xn;
82 dst[0] = xn;
83 dst[1] = -z;
84}
#define k
#define xn
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define a0
#define a1
#define t
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元

引用了 _umul64to128_(), a0, a1, k, lmmp_binvert_2_(), lmmp_binvert_ulong_(), lmmp_param_assert, t , 以及 xn.

被这些函数引用 lmmp_binvert_2_(), lmmp_binvert_3_(), lmmp_binvert_4_(), lmmp_binvert_n_dc_(), lmmp_binvert_unbalance_2_(), lmmp_divexact_(), lmmp_powmod_2_(), mont2_preinv(), TEST_CASE() , 以及 TEST_CASE().

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

◆ lmmp_binvert_3_()

void lmmp_binvert_3_ ( mp_ptr restrict dst,
mp_srcptr restrict numa )

在文件 binvert_1.c 第 123 行定义.

123 {
124 lmmp_param_assert(dst != NULL && numa != NULL);
125 lmmp_param_assert(numa[0] % 2 == 1);
126 /*
127 a == a0 + a1 * B^2
128 xn * a0 == 1 + k * B^2
129 yn := xn * (2 - a * xn) mod B^4
130 := xn * (2 - a0 * xn - a1 * xn * B^2) mod B^4
131 := xn * (2 - 1 - k*B^2 - a1 * xn * B^2) mod B^4
132 := xn * (1 - k*B^2 - a1 * xn * B^2) mod B^4
133 := (xn - xn*k * B^2 - a1 * xn^2 * B^2) mod B^4
134 */
135 lmmp_binvert_2_(dst, numa);
136 mp_limb_t k[3];
137 mp_limb_t z;
138 mp_limb_t a2 = numa[2];
139 _umul128to192_(dst[1], dst[0], numa[1], numa[0], k);
140 lmmp_debug_assert(k[1] == 0 && k[0] == 1);
141#define xn (dst[0])
142#define k (k[2])
143 z = xn * k;
144 z += a2 * xn * xn;
145 dst[2] = -z;
146#undef xn
147#undef k
148}
static void _umul128to192_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[3])
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define a2
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元

引用了 _umul128to192_(), a2, k, lmmp_binvert_2_(), lmmp_binvert_3_(), lmmp_debug_assert, lmmp_param_assert, restrict , 以及 xn.

函数调用图:

◆ lmmp_binvert_4_()

void lmmp_binvert_4_ ( mp_ptr restrict dst,
mp_srcptr restrict numa )

在文件 binvert_1.c 第 150 行定义.

150 {
151 lmmp_param_assert(dst != NULL && numa != NULL);
152 lmmp_param_assert(numa[0] % 2 == 1);
153 /*
154 a == a0 + a1 * B^2
155 xn * a0 == 1 + k * B^2
156 yn := xn * (2 - a * xn) mod B^4
157 := xn * (2 - a0 * xn - a1 * xn * B^2) mod B^4
158 := xn * (2 - 1 - k*B^2 - a1 * xn * B^2) mod B^4
159 := xn * (1 - k*B^2 - a1 * xn * B^2) mod B^4
160 := (xn - xn*k * B^2 - a1 * xn^2 * B^2) mod B^4
161 */
162 lmmp_binvert_2_(dst, numa);
163 mp_limb_t k[4];
164 _umul128to256_(dst[1], dst[0], numa[1], numa[0], k);
165 lmmp_debug_assert(k[1] == 0 && k[0] == 1);
166
167#define xn (dst)
168#define k (k + 2)
169 u128 z = _umul128to128_(k[1], k[0], xn[1], xn[0]);
170
171 mp_limb_t t0, t1;
172 _umul64to128_(xn[0], xn[0], &t0, &t1);
173 t1 += (xn[1] * xn[0]) << 1;
174 z += _umul128to128_(t1, t0, numa[3], numa[2]);
175
176 // dst[2..3] = -z (mod 2^128)
177 _u128store(dst + 2, (u128)0 - z);
178
179#undef xn
180#undef k
181}
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
static __uint128_t _umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)

引用了 _umul128to128_(), _umul128to256_(), _umul64to128_(), k, lmmp_binvert_2_(), lmmp_binvert_4_(), lmmp_debug_assert, lmmp_param_assert, restrict , 以及 xn.

函数调用图:

◆ lmmp_binvert_uint_()

uint lmmp_binvert_uint_ ( uint a)

计算 a 在2^32下的逆元

参数
a待求逆元
警告
a%2==1
返回
逆元

在文件 binvert_1.c 第 37 行定义.

37 {
38 lmmp_param_assert(a % 2 == 1);
39 uint r, y;
40
41 r = binv_tab[(a / 2) & 0x7F]; /* 8 bits */
42 y = 1 - a * r;
43 r = r * (1 + y); /* 16 bits */
44 y *= y;
45 r = r * (1 + y); /* 32 bits */
46 return r;
47}
static const uchar binv_tab[128]
Copyright (C) 2026 HJimmyK (Jericho Knox)
uint32_t uint
定义 numth.h:38

引用了 binv_tab, lmmp_binvert_uint_() , 以及 lmmp_param_assert.

被这些函数引用 lmmp_binvert_uint_() , 以及 TEST_CASE().

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

◆ lmmp_binvert_ulong_()

ulong lmmp_binvert_ulong_ ( ulong a)

计算 a 在2^64下的逆元

参数
a待求逆元
警告
a%2==1
返回
逆元

在文件 binvert_1.c 第 49 行定义.

49 {
50 lmmp_param_assert(a % 2 == 1);
51 ulong r, y;
52
53 r = binv_tab[(a / 2) & 0x7F]; /* 8 bits */
54 y = 1 - a * r;
55 r = r * (1 + y); /* 16 bits */
56 y *= y;
57 r = r * (1 + y); /* 32 bits */
58 y *= y;
59 r = r * (1 + y); /* 64 bits */
60 return r;
61}
uint64_t ulong
定义 numth.h:39

引用了 binv_tab, lmmp_binvert_ulong_() , 以及 lmmp_param_assert.

被这些函数引用 lmmp_binvert_2_(), lmmp_binvert_n_dc_(), lmmp_binvert_ulong_(), lmmp_binvert_unbalance_1_(), lmmp_divexact_(), lmmp_divexact_basecase_(), lmmp_is_prime_ulong_notrial_(), lmmp_mont_init_(), lmmp_powmod_1_(), lmmp_powmod_ulong_odd_(), TEST_CASE(), TEST_CASE() , 以及 trialdiv_init_chunk_().

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

◆ lmmp_binvert_unbalance_1_()

void lmmp_binvert_unbalance_1_ ( mp_ptr restrict dst,
mp_limb_t a,
mp_size_t n )

在文件 binvert_1.c 第 192 行定义.

192 {
193 lmmp_param_assert(dst != NULL);
194 lmmp_param_assert(a % 2 == 1);
195 lmmp_param_assert(n > 1);
197 dst[0] = a_binvert;
198 mp_size_t i = 0;
199 ulong k, p, lo, hi, carry;
200 _umul64to128_(a_binvert, a, &lo, &k);
202 for (; i < n - 2; i++) {
203 p = a_binvert * k;
204 dst[i + 1] = p;
205 _umul64to128_(p, a, &lo, &hi);
206 carry = (k + lo) < lo ? 1 : 0;
207 k = hi + carry;
208 }
209 p = a_binvert * k;
210 dst[n - 1] = p;
211}
#define a_binvert
uint64_t mp_size_t
定义 lmmp.h:93
#define n
#define lo

引用了 _umul64to128_(), a_binvert, k, lmmp_binvert_ulong_(), lmmp_binvert_unbalance_1_(), lmmp_param_assert, lo, n , 以及 restrict.

函数调用图:

◆ lmmp_binvert_unbalance_2_()

void lmmp_binvert_unbalance_2_ ( mp_ptr restrict dst,
mp_srcptr restrict numa,
mp_size_t n )

在文件 binvert_1.c 第 213 行定义.

213 {
214 lmmp_param_assert(dst != NULL && numa != NULL);
215 lmmp_param_assert(numa[0] % 2 == 1);
216 lmmp_param_assert(n > 2);
219 dst[0] = a_binvert[0];
220 dst[1] = a_binvert[1];
221
222 mp_limb_t k[4];
223 mp_limb_t t[4];
224 _umul128to256_(a_binvert[1], a_binvert[0], numa[1], numa[0], k);
225
226 // 此处本应按位取反再加一,得到相反数,但是a_binvert[0]不可能为0,所以进位必定为0
228 a_binvert[0] = ~a_binvert[0];
229 a_binvert[1] = ~a_binvert[1];
230 a_binvert[0]++;
231
232 mp_size_t i = 0;
233 if (n % 2 == 0) {
234 for (; i < n - 4; i += 2) {
235 u128 p = _umul128to128_(a_binvert[1], a_binvert[0], k[3], k[2]);
236 dst[i + 2] = _u128low(p);
237 dst[i + 3] = _u128high(p);
238 _umul128to256_(_u128high(p), _u128low(p), numa[1], numa[0], t);
239 // t = a*p;k = (k + t) >> 128,结果存回 k[2..3]
240 u128 klow = _u128load(k + 2);
241 u128 s = _u128load(t) + klow;
242 uint c = (uint)(s < klow);
243 _u128store(k + 2, _u128load(t + 2) + c);
244 }
245 u128 p = _umul128to128_(a_binvert[1], a_binvert[0], k[3], k[2]);
246 dst[i + 2] = _u128low(p);
247 dst[i + 3] = _u128high(p);
248 } else {
249 for (; i < n - 3; i += 2) {
250 u128 p = _umul128to128_(a_binvert[1], a_binvert[0], k[3], k[2]);
251 dst[i + 2] = _u128low(p);
252 dst[i + 3] = _u128high(p);
253 _umul128to256_(_u128high(p), _u128low(p), numa[1], numa[0], t);
254 // t = a*p;k = (k + t) >> 128,结果存回 k[2..3]
255 u128 klow = _u128load(k + 2);
256 u128 s = _u128load(t) + klow;
257 uint c = (uint)(s < klow);
258 _u128store(k + 2, _u128load(t + 2) + c);
259 }
260 u128 p = _umul128to128_(a_binvert[1], a_binvert[0], k[3], k[2]);
261 dst[i + 2] = _u128low(p);
262 }
263}
#define s

引用了 _umul128to128_(), _umul128to256_(), a_binvert, k, lmmp_binvert_2_(), lmmp_binvert_unbalance_2_(), lmmp_debug_assert, lmmp_param_assert, n, restrict, s , 以及 t.

函数调用图:

变量说明

◆ binv_tab

const uchar binv_tab[128]
static
初始值:
= {
1, 171, 205, 183, 57, 163, 197, 239, 241, 27, 61, 167, 41, 19, 53, 223, 225, 139, 173, 151, 25, 131,
165, 207, 209, 251, 29, 135, 9, 243, 21, 191, 193, 107, 141, 119, 249, 99, 133, 175, 177, 219, 253, 103,
233, 211, 245, 159, 161, 75, 109, 87, 217, 67, 101, 143, 145, 187, 221, 71, 201, 179, 213, 127, 129, 43,
77, 55, 185, 35, 69, 111, 113, 155, 189, 39, 169, 147, 181, 95, 97, 11, 45, 23, 153, 3, 37, 79,
81, 123, 157, 7, 137, 115, 149, 63, 65, 235, 13, 247, 121, 227, 5, 47, 49, 91, 125, 231, 105, 83,
117, 31, 33, 203, 237, 215, 89, 195, 229, 15, 17, 59, 93, 199, 73, 51, 85, 255}

Copyright (C) 2026 HJimmyK (Jericho Knox)

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

在文件 binvert_1.c 第 29 行定义.

被这些函数引用 lmmp_binvert_uint_() , 以及 lmmp_binvert_ulong_().