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

浏览该文件的源代码.

函数

mp_limb_t lmmp_div_mulinv_ (mp_ptr restrict dstq, mp_ptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb, mp_srcptr restrict invappr, mp_size_t ni)
void lmmp_inv_prediv_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t ni)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ lmmp_div_mulinv_()

mp_limb_t lmmp_div_mulinv_ ( mp_ptr restrict dstq,
mp_ptr restrict numa,
mp_size_t na,
mp_srcptr restrict numb,
mp_size_t nb,
mp_srcptr restrict invappr,
mp_size_t ni )

在文件 div_mulinv.c 第 56 行定义.

64 {
65 lmmp_param_assert(na >= nb && nb >= ni);
66 lmmp_param_assert(ni > 0);
67 lmmp_param_assert(dstq != NULL && numa != NULL);
68 lmmp_param_assert(invappr != NULL && numb != NULL);
70 mp_size_t nq = na - nb, ntp = LMMP_MIN(ni, nq) + nb;
71 mp_limb_t qh;
74
75 numa += nq;
76 dstq += nq;
77
78 qh = lmmp_cmp_(numa, numb, nb) >= 0;
79 if (qh) {
80 lmmp_sub_n_(numa, numa, numb, nb);
81 }
82
83 fft_gr_cache mersenne_ctx;
84 int mersenne_flag = 0;
85 fft_cache fft_ctx;
86 int fft_flag = 0;
87 int small_flag = 0;
88
89 while (nq) {
90 if (nq < ni) {
91 invappr += ni - nq;
92 ni = nq;
93 small_flag = 1;
94 }
95 numa -= ni;
96 dstq -= ni;
97 nq -= ni;
98
99 mp_size_t mn, wn;
100 mp_limb_t cy;
101
102 if (small_flag == 1 || ni < MUL_FFT_THRESHOLD)
103 lmmp_mul_n_(tp, numa + nb, invappr, ni);
104 else {
105 if (fft_flag == 0) {
106 mp_size_t hn = lmmp_fft_next_size_((2 * ni + 1) / 2);
107 lmmp_mul_fft_cache_init_(tp, hn, numa + nb, ni, invappr, ni, &fft_ctx);
108 fft_flag = 1;
109 } else {
110 lmmp_mul_fft_cache_(tp, numa + nb, &fft_ctx);
111 }
112 }
113 cy = lmmp_add_n_(dstq, tp + ni, numa + nb, ni);
114 lmmp_assert(cy == 0);
115
116 /* 档位先行:缓存档取 fft 可行尺寸(缓存仅 fft),分发档取梅森细粒度 */
118 : lmmp_mersenne_next_size_(nb + 1);
119 if (nb < DIV_MULINV_MODM_THRESHOLD || mn >= nb + ni) {
120 lmmp_mul_(tp, numb, nb, dstq, ni); // nb+ni limbs, high 'ni' cancels
121 } else {
122 // 0<wn<ni<=nb<mn<nb+ni
123 wn = nb + ni - mn;
124
125 // x=b*q
126 // tp=x mod 2^mn-1(中档/尾块走分发入口不缓存,循环体缓存仅 fft)
127 if (small_flag == 1 || nb < DIV_MULINV_MODM_CACHE_THRESHOLD)
128 lmmp_mul_mersenne_(tp, mn, dstq, ni, numb, nb);
129 else {
130 if (mersenne_flag == 0) {
131 lmmp_mul_mersenne_cache_init_(tp, mn, dstq, ni, numb, nb, &mersenne_ctx);
132 mersenne_flag = 1;
133 } else {
134 lmmp_mul_mersenne_cache_(tp, dstq, &mersenne_ctx);
135 }
136 }
137
138 // tp-=ah:0 mod B^mn-1, if result=0, represent it as B^mn-1
139 cy = lmmp_sub_nc_(tp, tp, numa + mn, wn, 1);
140 if (cy)
141 cy = lmmp_sub_1_(tp + wn, tp + wn, mn - wn, 1);
142 if (!cy)
143 lmmp_inc(tp);
144
145 // if al<<tp,
146 if (lmmp_cmp_(numa + nb, tp + nb, mn - nb) < 0) {
147 // maybe ah=xh+1 and al<<xl,
148 // so we subtracted 1 too much when tp-=ah,
149 // now tp=xl-1 mod B^mn-1, and 0<=al<<xl-1<B^mn-1, so tp=xl-1
150 // or ah=xh and al>=xl,
151 // tp=xl mod B^mn-1, the only possibility is we represented xl=0 as tp=B^mn-1
152 // whatever, just inc and then tp=xl
153 tp[mn] = 0; // set a limit
154 lmmp_inc(tp);
155 }
156 }
157
158 mp_limb_t r = numa[nb] - tp[nb];
159 cy = lmmp_sub_n_(numa, numa, tp, nb);
160
161 while ((r -= cy) || lmmp_cmp_(numa, numb, nb) >= 0) {
162 lmmp_inc(dstq);
163 cy = lmmp_sub_n_(numa, numa, numb, nb);
164 }
165 }
166
167 if (mersenne_flag == 1)
168 lmmp_fft_gr_cache_free_(&mersenne_ctx);
169 if (fft_flag == 1)
170 lmmp_fft_cache_free_(&fft_ctx);
171 TEMP_FREE;
172 return qh;
173}
#define lmmp_mul_n_
#define LIMB_B_2
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_assert(x)
定义 lmmp.h:481
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define MUL_FFT_THRESHOLD
#define DIV_MULINV_MODM_CACHE_THRESHOLD
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
#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]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
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_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_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
void lmmp_mul_mersenne_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static void lmmp_fft_cache_free_(fft_cache *ctx)
释放FFT模乘法缓存上下文
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
void lmmp_mul_fft_cache_init_(mp_ptr dst, mp_size_t hn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_cache *ctx)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] 第二个操作数将被缓存
void lmmp_mul_fft_cache_(mp_ptr dst, mp_srcptr numa, fft_cache *ctx)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_mersenne_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1 第二个操作数将被缓存
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define numb
#define tp
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 DIV_MULINV_MODM_CACHE_THRESHOLD, LIMB_B_2, lmmp_add_n_(), lmmp_assert, lmmp_cmp_(), lmmp_div_mulinv_(), lmmp_fft_cache_free_(), lmmp_fft_gr_cache_free_(), lmmp_fft_next_size_(), lmmp_inc, lmmp_mersenne_next_size_(), LMMP_MIN, lmmp_mul_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_cache_init_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_n_, lmmp_param_assert, lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_(), MUL_FFT_THRESHOLD, numb, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图:

◆ lmmp_inv_prediv_()

void lmmp_inv_prediv_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t na,
mp_size_t ni )

Copyright (C) 2026 HJimmyK (Jericho Knox)

除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B

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

Copyright (C) 2026 HJimmyK (Jericho Knox)

参数
dst输出预计算逆元的缓冲区,长度为ni
numa输入操作数,长度为na
na输入操作数的 limb 长度
ni预计算逆元的目标尺寸
警告
na>=ni>0, MSB(numa)=1, eqsep(dst,numa), dst!=NULL, numa!=NULL
注解
if (ni=na) [dst,na] = (B^(2*na)-1) / [numa,na] - B^na

在文件 div_mulinv.c 第 30 行定义.

30 {
31 lmmp_param_assert(na >= ni);
32 lmmp_param_assert(ni > 0);
33 lmmp_param_assert(dst != NULL && numa != NULL);
34 lmmp_param_assert(numa[na - 1] >= LIMB_B_2);
36 mp_limb_t cy;
38
39 if (na == ni) {
40 lmmp_copy(tp + 1, numa, ni);
41 tp[0] = 1;
42 cy = 0;
43 } else {
44 cy = lmmp_add_1_(tp, numa + na - (ni + 1), ni + 1, 1);
45 }
46 if (cy)
47 lmmp_zero(dst, ni);
48 else {
49 mp_ptr restrict invappr = TALLOC_TYPE(ni + 1, mp_limb_t);
50 lmmp_invappr_(invappr, tp, ni + 1);
51 lmmp_copy(dst, invappr + 1, ni);
52 }
54}
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
void lmmp_invappr_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算 (invappr)
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x

引用了 LIMB_B_2, lmmp_add_1_(), lmmp_copy, lmmp_inv_prediv_(), lmmp_invappr_(), lmmp_param_assert, lmmp_zero, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

被这些函数引用 dec_pow_extend_(), lmmp_div_(), lmmp_div_s_(), lmmp_inv_prediv_() , 以及 lmmp_to_str_().

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