LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
bninv.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
29/*
30funtion: bninv
31output:
32 dstq := B^(2*(na+ni)) / ([numa,na] * B^ni)
33
34 numa
35 |
36 |---ni---|------na-------|
37 +--------+---------------+
38 | 000000 | aaaaaaaaaaaaa |
39 +--------+---------------+
40 <---remn---->|<--a_hatn->|
41 |
42 a_hat
43
44 N = na + ni
45 a_hatn = N / 2 + 1
46 remn = N - a_hatn
47 a_hat = numa + na - a_hatn
48
49 if remn > ni:
50 ni_hat = 0
51 else
52 ni_hat = ni - remn
53 q_hat = bninv(a_hat, a_hatn, ni_hat)
54
55 q_hatn = a_hatn + ni_hat + 1
56 = N_half + 1
57
58 qrn = N + 1 - q_hatn
59 = N + 1 - (N_half + 1)
60 = N - N_half
61
62 q_hat
63 |
64 |---qrn----|--q_hatn--|
65 +----------+----------+
66 | 00000000 | qqqqqqqq |
67 +----------+----------+
68 <---------N+1--------->
69
70
71 2*q_hatn + 2*qrn + an + ni = 2*(N+1) + N = 3*N + 2
72
73 q_hat_sqr_a
74 |
75 |---qrn---|---qrn---|-----ni-----|------2 * q_hatn + an-------|
76 +---------+---------+------------+----------------------------+
77 | 0000000 | 0000000 | 0000000000 | ssssssssssssssssssss | 0 |
78 +---------+---------+----------+-+---------+------------+-----+
79 | delete | 000000000 | qqqqqqqqqq | ca |
80 +-------------- 2*N -----------+----qrn----+-- q_hatn --+-----+
81 | 2*N_half |<------- N+1 ---------->|<-1->|
82 |
83 dstq
84 and assert(ca == 0)
85*/
86
87/**
88 * @brief 牛顿法求精确逆元(至多产生1的误差)
89 * @note dstq := B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|1]
90 * @warning sep(dstq,numa), dstq!=NULL, numa!=NULL, na>=3, MSB(numa)=1
91 */
93 lmmp_param_assert(na >= 3);
94 lmmp_param_assert(dstq != NULL && numa != NULL);
95 lmmp_param_assert(numa[na - 1] >= LIMB_B_2);
97 if (na < BNINV_NEWTON_THRESHOLD) {
98 mp_ptr restrict bnp = TALLOC_TYPE(2 * na + ni + 1, mp_limb_t);
99 lmmp_zero(bnp, 2 * na + ni + 1);
100 bnp[2 * na + ni] = 1;
101 mp_limb_t inv21 = lmmp_inv_2_1_(numa[na - 1], numa[na - 2]);
102 lmmp_div_basecase_(dstq, bnp, 2 * na + ni + 1, numa, na, inv21);
103 } else {
104 mp_srcptr restrict a_hat;
105
106 mp_size_t N = na + ni;
107 mp_size_t a_hatn = N / 2 + 1;
108 mp_size_t remn = N - a_hatn;
109 mp_size_t ni_hat;
110 if (remn > ni) {
111 ni_hat = 0;
112 a_hat = numa + na - a_hatn;
113 } else {
114 ni_hat = ni - remn;
115 a_hat = numa;
116 a_hatn = na;
117 }
118 mp_size_t q_hatn = a_hatn + ni_hat + 1;
119 mp_size_t qrn = N + 1 - q_hatn;
120 mp_ptr restrict q_hat = dstq + qrn;
121
122 mp_ptr restrict q_hat_sqr = TALLOC_TYPE(2 * q_hatn, mp_limb_t);
123 mp_ptr restrict q_hat_sqr_a = TALLOC_TYPE(2 * q_hatn + na, mp_limb_t);
124
125 lmmp_bninv_appr_newton_(q_hat, a_hat, a_hatn, ni_hat);
126 lmmp_sqr_(q_hat_sqr, q_hat, q_hatn);
127 lmmp_mul_(q_hat_sqr_a, q_hat_sqr, 2 * q_hatn, numa, na);
128 // we can assert q_hat_sqr_a[2*q_hatn+na-1] == 0
129 lmmp_zero(dstq, qrn);
130 if (2 * qrn + ni > 2 * N) {
131 mp_size_t start = 2 * qrn + ni - 2 * N;
132 lmmp_shl_(q_hat, q_hat, q_hatn, 1); // assert no carry
133 lmmp_sub_n_(dstq + start, dstq + start, q_hat_sqr_a, N + 1 - start);
134 } else {
135 mp_size_t start = 2 * N - 2 * qrn - ni;
136 lmmp_shl_(q_hat, q_hat, q_hatn, 1); // assert no carry
137 lmmp_sub_n_(dstq, dstq, q_hat_sqr_a + start, N + 1);
138 }
139 }
140 TEMP_FREE;
141}
142
144 lmmp_param_assert(na > 0);
145 lmmp_param_assert(dstq != NULL && numa != NULL);
146 lmmp_param_assert(numa[na - 1] > 0);
147 TEMP_DECL;
148 if (na == 1) {
149 lmmp_zero(dstq, 2 + ni);
150 dstq[2 + ni] = 1;
151 lmmp_div_1_(dstq, dstq, 3 + ni, numa[0]);
152 } else if (na == 2) {
153 mp_size_t bn = 2 * 2 + ni + 1;
155 lmmp_zero(bnp, bn - 1);
156 bnp[bn - 1] = 1;
157 mp_limb_t d[2] = {numa[0], numa[1]};
158 lmmp_div_2_(dstq, bnp, bn, d);
159 } else if (ni > na) {
160 mp_ptr restrict B = TALLOC_TYPE(2 * na + ni + 1, mp_limb_t);
161 lmmp_zero(B, 2 * na + ni);
162 B[2 * na + ni] = 1;
163 lmmp_div_(dstq, NULL, B, 2 * na + ni + 1, numa, na);
164 } else {
165 int shift = lmmp_leading_zeros_(numa[na - 1]);
166 if (shift > 0) {
167 mp_ptr restrict numa_shift = TALLOC_TYPE(na, mp_limb_t);
168 lmmp_shl_(numa_shift, numa, na, shift);
169 lmmp_bninv_appr_newton_(dstq, numa_shift, na, ni + 1);
170 lmmp_shr_(dstq, dstq, na + ni + 2, LIMB_BITS - shift);
171 } else {
172 lmmp_bninv_appr_newton_(dstq, numa, na, ni + 1);
173 lmmp_copy(dstq, dstq + 1, na + ni + 1);
174 dstq[na + ni + 1] = 0;
175 }
176 }
177 TEMP_FREE;
178 return;
179}
static void lmmp_bninv_appr_newton_(mp_ptr restrict dstq, mp_srcptr restrict numa, mp_size_t na, mp_size_t ni)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 bninv.c:92
#define B
#define bn
#define lmmp_leading_zeros_
#define lmmp_sqr_
#define LIMB_B_2
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#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
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define BNINV_NEWTON_THRESHOLD
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
void lmmp_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
定义 div.c:294
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
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_bninv_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_size_t ni)
近似逆元计算 [dstq,na+ni+2] = B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|-ept]
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_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
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_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)
基础除法运算
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)