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/inlines.h"
24#include "mparam.h"
25#include "impl/tmp_alloc.h"
26#include "lmmp/lmmpn.h"
27
28
30 lmmp_param_assert(na > 0);
31 lmmp_param_assert(dst != NULL && numa != NULL);
32 lmmp_param_assert(numa[na - 1] >= LIMB_B_2);
33 if (na == 1)
34 *dst = lmmp_inv_1_(*numa);
35 else {
38 mp_size_t i = na;
39 do {
40 xp[--i] = LIMB_MAX;
41 } while (i);
42 lmmp_not_(xp + na, numa, na);
43 //[xp,2*na] = B^(2*na)-1 - [numa,na]*B^na
44
45 if (na == 2) {
46 lmmp_div_2_s_(dst, xp, 4, numa);
47 } else {
48 mp_limb_t inv21 = lmmp_inv_2_1_(numa[na - 1], numa[na - 2]);
49 if (na < DIV_DIVIDE_THRESHOLD) {
50 lmmp_div_basecase_(dst, xp, 2 * na, numa, na, inv21);
51 } else {
52 lmmp_div_divide_(dst, xp, 2 * na, numa, na, inv21);
53 }
54 }
56 }
57}
58
60 lmmp_param_assert(na > 4);
61 lmmp_param_assert(dst != NULL && numa != NULL);
62 lmmp_param_assert(numa[na - 1] >= LIMB_B_2);
63
64 mp_limb_t cy;
65 mp_size_t nr = na, mn;
66 mp_size_t sizes[LIMB_BITS], *sizp = sizes;
67
68 do {
69 *sizp = nr;
70 nr = (nr >> 1) + 1;
71 ++sizp;
72 } while (nr >= INV_NEWTON_THRESHOLD);
73
74 numa += na;
75 dst += na;
76
77 lmmp_inv_basecase_(dst - nr, numa - nr, nr);
78
80 mp_ptr restrict xp = TALLOC_TYPE(3 * (na >> 1) + 3, mp_limb_t);
81 do {
82 na = *--sizp;
83
84 // ar = 0:[numa-nr,nr]
85 // an = 0:[numa-na,na]
86 // ir = 1:[dst-nr,nr] = (B^(2*nr)-1)/ar - [0|1]
87 // rem = ir*an-B^(na+nr)
88 //-2*B^na < rem < 2*B^na
89
90 //[xp] = rem
91 if (na < INV_MODM_THRESHOLD || (mn = lmmp_mersenne_next_size_(na + 1)) >= na + nr) {
92 lmmp_mul_(xp, numa - na, na, dst - nr, nr);
93 lmmp_add_n_(xp + nr, xp + nr, numa - na, na + 1 - nr);
94 cy = 1; // for mod B^(na+1)
95 } else { // nr < na < mn < na+nr
96
97 //[xp,mn] = [dst,nr] * [numa,na] mod (B^mn-1)
98 lmmp_mul_mersenne_(xp, mn, numa - na, na, dst - nr, nr);
99
100 //[xp,mn] += [numa,na]*B^nr mod (B^mn-1)
101 cy = lmmp_add_n_(xp + nr, xp + nr, numa - na, mn - nr);
102 cy = lmmp_add_nc_(xp, xp, numa - (na - (mn - nr)), na - (mn - nr), cy);
103
104 //[xp,mn] -= B^(na+nr) mod (B^mn-1)
105 xp[mn] = 1;
106 lmmp_dec_1(xp + na + nr - mn, 1 - cy);
107 lmmp_dec_1(xp, 1 - xp[mn]);
108
109 cy = 0; // for mod (B^mn-1)
110 }
111
112 // adjust ir,rem s.t.
113 // -B^na < rem = ir*an - B^(na+nr) < 0
114 // use this we can prove B^nr <= ir < 2*B^nr
115 // so inc/dec ir won't overflow
116 if (xp[na] < 2) { // rem>=0
117
118 // rem-=cy*an s.t. rem[na]=0
119 if ((cy = xp[na])) {
120 if (!lmmp_sub_n_(xp, xp, numa - na, na)) {
121 ++cy;
122 lmmp_sub_n_(xp, xp, numa - na, na);
123 }
124 }
125
126 // rem-=cy*an s.t. 0<=rem<an
127 if (lmmp_cmp_(xp, numa - na, na) >= 0) {
128 lmmp_sub_n_(xp, xp, numa - na, na);
129 ++cy;
130 }
131
132 // 0 < an-rem <= an < B^na , trunc to nr limbs
133 lmmp_sub_nc_(xp + 2 * nr, numa - nr, xp + na - nr, nr, lmmp_cmp_(xp, numa - na, na - nr) > 0);
134 ++cy;
135
136 lmmp_dec_1(dst - nr, cy);
137 } else { // rem<0
138 if (cy)
139 lmmp_dec(xp); // for neg to not
140 // else (neg to not) compensate (mod transfer)
141
142 if (xp[na] != LIMB_MAX) {
143 mp_limb_t not_xp = lmmp_add_n_(xp, xp, numa - na, na);
144 lmmp_assert(xp[na] + not_xp == LIMB_MAX);
145 lmmp_inc(dst - nr);
146 }
147
148 //-rem
149 lmmp_not_(xp + 2 * nr, xp + na - nr, nr);
150 }
151
152 // in = 1:[dst-na,na]
153 // in = ir*B^(na-nr) + ir*(-rem/B^(na-nr))/B^(3*nr-na)
154 // use inequality an*ir!=B^(na+nr),
155 //(otherwise obviously contradictory),
156 // we can prove
157 // an*in <= an*ir * ( 2*B^(na+nr) - an*ir ) * B^(-2*nr) < B^(2*na)
158 // so in < B^(2*na)/an <= 2*B^(na),
159 // inc below won't overflow
160
161 // and via inequality -B^na < an*ir - B^(na+nr) < 0
162 // we can prove in = (B^(2*na)-1)/an - [0|1]
163 lmmp_mul_n_(xp, xp + 2 * nr, dst - nr, nr);
164 cy = lmmp_add_n_(xp + nr, xp + nr, xp + 2 * nr, 2 * nr - na);
165 if (lmmp_add_nc_(dst - na, xp + 3 * nr - na, xp + 4 * nr - na, na - nr, cy))
166 lmmp_inc(dst - nr);
167
168 nr = na;
169 } while (sizp != sizes);
170 TEMP_FREE;
171}
172
174 lmmp_param_assert(na > 0);
175 lmmp_param_assert(dst != NULL && numa != NULL);
176 lmmp_param_assert(numa[na - 1] != 0);
177 mp_limb_t high = numa[na - 1];
178 int nsh = lmmp_leading_zeros_(high);
179 TEMP_DECL;
180 if (dst == numa || nsh || nf) {
181 nf += nsh != 0;
182 mp_ptr restrict numa2 = TALLOC_TYPE(na + nf, mp_limb_t);
183 lmmp_zero(numa2, nf);
184 lmmp_shl_(numa2 + nf, numa, na, nsh); // nsh=0 时函数内即整段拷贝
185 numa = numa2;
186 }
187 lmmp_invappr_(dst, numa, na + nf);
188 if (nsh)
189 lmmp_shr_c_(dst, dst, na + nf, LIMB_BITS - nsh, (mp_limb_t)1 << nsh);
190 else
191 dst[na + nf] = 1;
192 TEMP_FREE;
193}
194
196 lmmp_param_assert(dst != NULL && numa != NULL);
197 lmmp_param_assert(na > 0);
198 if (na < INV_NEWTON_THRESHOLD)
199 lmmp_inv_basecase_(dst, numa, na);
200 else
201 lmmp_invappr_newton_(dst, numa, na);
202}
#define lmmp_leading_zeros_
#define lmmp_mul_n_
#define LIMB_B_2
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define LIMB_MAX
定义 lmmp.h:105
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_assert(x)
定义 lmmp.h:481
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define DIV_DIVIDE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define INV_NEWTON_THRESHOLD
#define INV_MODM_THRESHOLD
void lmmp_invappr_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算 (invappr)
void lmmp_mul_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
mp_limb_t lmmp_shr_c_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr, mp_limb_t c)
带进位的右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充c的高shr位
定义 shr.c:39
#define lmmp_dec(p)
减1宏(预期无借位)
#define lmmp_inc(p)
加1宏(预期无进位)
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_invappr_newton_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算(牛顿迭代法)
mp_limb_t lmmp_add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c
定义 add_n.c:58
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
void lmmp_inv_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
void lmmp_inv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t nf)
求逆操作 [dst,na+nf+1] = (B^(2*(na+nf)) - 1) / ([numa,na]*B^nf) + [0|-1]
定义 inv.c:173
mp_limb_t lmmp_div_2_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb)
双精度数除法(除数为2个limb)
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
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
mp_limb_t lmmp_div_basecase_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
基础除法运算
mp_limb_t lmmp_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
定义 sub_n.c:67
mp_limb_t lmmp_div_divide_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
分治除法运算
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
#define xp
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)