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

浏览该文件的源代码.

函数

void lmmp_bninv_ (mp_ptr restrict dstq, mp_srcptr restrict numa, mp_size_t na, mp_size_t ni)
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)

函数说明

◆ lmmp_bninv_()

void lmmp_bninv_ ( mp_ptr restrict dstq,
mp_srcptr restrict numa,
mp_size_t na,
mp_size_t ni )

在文件 bninv.c 第 143 行定义.

143 {
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_
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
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
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
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
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 B, bn, LIMB_BITS, lmmp_bninv_(), lmmp_bninv_appr_newton_(), lmmp_copy, lmmp_div_(), lmmp_div_1_(), lmmp_div_2_(), lmmp_leading_zeros_, lmmp_param_assert, lmmp_shl_(), lmmp_shr_(), lmmp_zero, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ lmmp_bninv_appr_newton_()

void lmmp_bninv_appr_newton_ ( mp_ptr restrict dstq,
mp_srcptr restrict numa,
mp_size_t na,
mp_size_t ni )
static

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

牛顿法求精确逆元(至多产生1的误差)

注解
dstq := B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|1]
警告
sep(dstq,numa), dstq!=NULL, numa!=NULL, na>=3, MSB(numa)=1

在文件 bninv.c 第 92 行定义.

92 {
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}
#define lmmp_sqr_
#define LIMB_B_2
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define BNINV_NEWTON_THRESHOLD
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]
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)
基础除法运算

引用了 BNINV_NEWTON_THRESHOLD, LIMB_B_2, lmmp_bninv_appr_newton_(), lmmp_div_basecase_(), lmmp_inv_2_1_(), lmmp_mul_(), lmmp_param_assert, lmmp_shl_(), lmmp_sqr_, lmmp_sub_n_(), lmmp_zero, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 lmmp_bninv_() , 以及 lmmp_bninv_appr_newton_().

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