LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
binvert_1.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 "lmmp/numth.h"
24#include "lmmp/lmmpn.h"
25#include "impl/longlong.h"
26
27/* from https://arxiv.org/abs/2204.04342 */
28
29static const uchar binv_tab[128] = {
30 1, 171, 205, 183, 57, 163, 197, 239, 241, 27, 61, 167, 41, 19, 53, 223, 225, 139, 173, 151, 25, 131,
31 165, 207, 209, 251, 29, 135, 9, 243, 21, 191, 193, 107, 141, 119, 249, 99, 133, 175, 177, 219, 253, 103,
32 233, 211, 245, 159, 161, 75, 109, 87, 217, 67, 101, 143, 145, 187, 221, 71, 201, 179, 213, 127, 129, 43,
33 77, 55, 185, 35, 69, 111, 113, 155, 189, 39, 169, 147, 181, 95, 97, 11, 45, 23, 153, 3, 37, 79,
34 81, 123, 157, 7, 137, 115, 149, 63, 65, 235, 13, 247, 121, 227, 5, 47, 49, 91, 125, 231, 105, 83,
35 117, 31, 33, 203, 237, 215, 89, 195, 229, 15, 17, 59, 93, 199, 73, 51, 85, 255};
36
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}
48
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}
62
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}
85
86static inline void _umul128to192_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[3]) {
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}
122
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}
149
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}
182
183/*
184unbalanced:
185 a := [numa,na]
186 a^-1 = a^-1 mod B^na
187
188 p = -k * a^-1 mod B^na
189 k = (k + a*p) / B^na
190*/
191
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}
212
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 k
#define a_binvert
static const uchar binv_tab[128]
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define xn
static void _umul128to192_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[3])
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
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)
#define a0
#define a1
#define a2
#define t
#define s
#define n
#define lo
void lmmp_binvert_unbalance_1_(mp_ptr dst, mp_limb_t a, mp_size_t n)
计算 a 在 B^n 下的逆元
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
uint32_t uint
定义 numth.h:38
uint lmmp_binvert_uint_(uint a)
计算 a 在2^32下的逆元
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
void lmmp_binvert_3_(mp_ptr dst, mp_srcptr numa)
计算 [numa,3] 在 B^3 下的逆元
void lmmp_binvert_4_(mp_ptr dst, mp_srcptr numa)
计算 [numa,4] 在 B^4 下的逆元
uint64_t ulong
定义 numth.h:39
void lmmp_binvert_unbalance_2_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
计算 [numa,2] 在 B^n 下的逆元
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)