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

浏览该文件的源代码.

宏定义

#define MONT63_MAX   ((ulong)(0x7fffffffffffffff))
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

mp_limb_t lmmp_mod_4chunk_1_ (mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
 4 链折叠取模:r = [numa,na] mod d
mp_limb_t lmmp_mod_8chunk_1_ (mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
 8 链折叠取模:r = [numa,na] mod d
static ulong mont63_mul (ulong a, ulong b, ulong m, ulong m_inv)
 蒙域乘:a*b*R^-1 mod m(R=B)
static ulong mont63_reduce (u128 t, ulong m, ulong m_inv)
 蒙域约化 REDC

宏定义说明

◆ MONT63_MAX

#define MONT63_MAX   ((ulong)(0x7fffffffffffffff))

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

在文件 mod_chunk.c 第 31 行定义.

函数说明

◆ lmmp_mod_4chunk_1_()

mp_limb_t lmmp_mod_4chunk_1_ ( mp_srcptr numa,
mp_size_t na,
mp_limb_t d,
mp_limb_t dinv,
mp_limb_t r2,
mp_limb_t base,
mp_limb_t mi )

4 链折叠取模:r = [numa,na] mod d

参数
numa被除数(长度为 na 个limb)
na被除数的 limb 长度
d除数(单个 limb)
dinv除数的逆元(d*dinv==1 mod 2^64)
r2蒙域预处理(r2=B^2 mod d)
base蒙域预处理(base=B mod d)
mi蒙域预处理(mi=-dinv mod 2^64)
警告
na>0, numa!=NULL, d%2==1, d<2^63, d*dinv==1 mod 2^64, dinv+mi==0 (mod B), r2=B^2 mod d, base=B mod d
返回
[numa,na] mod d

在文件 mod_chunk.c 第 52 行定义.

53 {
54 lmmp_param_assert(na > 0);
55 lmmp_param_assert(numa != NULL);
56 lmmp_param_assert(d % 2 == 1);
58 lmmp_param_assert(dinv * d == 1);
59 lmmp_param_assert(dinv + mi == 0);
60 lmmp_param_assert(base < d);
62
63 mp_size_t L = na >> 2, t = na & 3;
64 ulong bw = r2, wm = base;
65 for (mp_size_t ee = L; ee; ee >>= 1) {
66 if (ee & 1) wm = mont63_mul(wm, bw, d, mi);
67 bw = mont63_mul(bw, bw, d, mi);
68 }
69 ulong bt = r2; /* mont(B^t):t=0 时终段有 if(t) 守卫 */
70 for (mp_size_t k = 1; k < t; ++k) bt = mont63_mul(bt, r2, d, mi);
71
72 const mp_limb_t *p0 = numa + t, *p1 = numa + t + L, *p2 = numa + t + 2 * L,
73 *p3 = numa + t + 3 * L, *e = numa + t + L;
74 ulong c0 = 0, c1 = 0, c2 = 0, c3 = 0;
75 while (p0 < e) {
76 ulong s, l, q;
77 s = *p0++;
78 l = s - c0;
79 q = l * dinv;
80 c0 = _u128high((u128)q * d) + (s < c0);
81 s = *p1++;
82 l = s - c1;
83 q = l * dinv;
84 c1 = _u128high((u128)q * d) + (s < c1);
85 s = *p2++;
86 l = s - c2;
87 q = l * dinv;
88 c2 = _u128high((u128)q * d) + (s < c2);
89 s = *p3++;
90 l = s - c3;
91 q = l * dinv;
92 c3 = _u128high((u128)q * d) + (s < c3);
93 }
94 ulong cb = 0;
95 for (mp_size_t i = 0; i < t; ++i) {
96 ulong s = numa[i], l = s - cb;
97 ulong q = l * dinv;
98 cb = _u128high((u128)q * d) + (s < cb);
99 }
100 ulong cj[4] = {c0, c1, c2, c3}, wT = wm, acc = 0;
101 for (int j = 0; j < 3; ++j) {
102 acc += mont63_mul(cj[j], wm, d, mi);
103 acc = acc >= d ? acc - d : acc;
104 wm = mont63_mul(wm, wT, d, mi);
105 }
106 acc += mont63_mul(cj[3], wm, d, mi);
107 acc = acc >= d ? acc - d : acc;
108 acc += cb; /* 底组项权重 B^t*w^0 */
109 acc = acc >= d ? acc - d : acc;
110 if (t) acc = mont63_mul(acc, bt, d, mi); /* ×B^t:N ≡ -B^t*acc */
111 return acc ? d - acc : 0;
112}
#define k
#define MONT63_MAX
Copyright (C) 2026 HJimmyK (Jericho Knox)
static ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv)
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define r2
#define t
#define s
#define c1
#define c0
uint64_t ulong
定义 numth.h:39

引用了 c0, c1, k, lmmp_mod_4chunk_1_(), lmmp_param_assert, MONT63_MAX, mont63_mul(), r2, s , 以及 t.

被这些函数引用 lmmp_mod_4chunk_1_(), lmmp_trialdiv_() , 以及 trialdiv_leg_4_().

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

◆ lmmp_mod_8chunk_1_()

mp_limb_t lmmp_mod_8chunk_1_ ( mp_srcptr numa,
mp_size_t na,
mp_limb_t d,
mp_limb_t dinv,
mp_limb_t r2,
mp_limb_t base,
mp_limb_t mi )

8 链折叠取模:r = [numa,na] mod d

参数
numa被除数(长度为 na 个limb)
na被除数的 limb 长度
d除数(单个 limb)
dinv除数的逆元(d*dinv==1 mod 2^64)
r2蒙域预处理(r2=B^2 mod d)
base蒙域预处理(base=B mod d)
mi蒙域预处理(mi=-dinv mod 2^64)
警告
na>0, numa!=NULL, d%2==1, d<2^63, d*dinv==1 mod 2^64, dinv+mi==0 (mod B), r2=B^2 mod d, base=B mod d
返回
[numa,na] mod d

在文件 mod_chunk.c 第 114 行定义.

115 {
116 lmmp_param_assert(na > 0);
117 lmmp_param_assert(numa != NULL);
118 lmmp_param_assert(d % 2 == 1);
120 lmmp_param_assert(dinv * d == 1);
121 lmmp_param_assert(dinv + mi == 0);
122 lmmp_param_assert(base < d);
124
125 mp_size_t L = na >> 3, t = na & 7;
126 ulong bw = r2, wm = base;
127 for (mp_size_t ee = L; ee; ee >>= 1) {
128 if (ee & 1) wm = mont63_mul(wm, bw, d, mi);
129 bw = mont63_mul(bw, bw, d, mi);
130 }
131 ulong bt = r2; /* mont(B^t):t=0 时终段有 if(t) 守卫 */
132 for (mp_size_t k = 1; k < t; ++k) bt = mont63_mul(bt, r2, d, mi);
133
134 const mp_limb_t *p0 = numa + t, *p1 = numa + t + L, *p2 = numa + t + 2 * L,
135 *p3 = numa + t + 3 * L, *p4 = numa + t + 4 * L, *p5 = numa + t + 5 * L,
136 *p6 = numa + t + 6 * L, *p7 = numa + t + 7 * L, *e = numa + t + L;
137 ulong c0 = 0, c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0, c7 = 0;
138 while (p0 < e) {
139 ulong s, l, q;
140 s = *p0++;
141 l = s - c0;
142 q = l * dinv;
143 c0 = _u128high((u128)q * d) + (s < c0);
144 s = *p1++;
145 l = s - c1;
146 q = l * dinv;
147 c1 = _u128high((u128)q * d) + (s < c1);
148 s = *p2++;
149 l = s - c2;
150 q = l * dinv;
151 c2 = _u128high((u128)q * d) + (s < c2);
152 s = *p3++;
153 l = s - c3;
154 q = l * dinv;
155 c3 = _u128high((u128)q * d) + (s < c3);
156 s = *p4++;
157 l = s - c4;
158 q = l * dinv;
159 c4 = _u128high((u128)q * d) + (s < c4);
160 s = *p5++;
161 l = s - c5;
162 q = l * dinv;
163 c5 = _u128high((u128)q * d) + (s < c5);
164 s = *p6++;
165 l = s - c6;
166 q = l * dinv;
167 c6 = _u128high((u128)q * d) + (s < c6);
168 s = *p7++;
169 l = s - c7;
170 q = l * dinv;
171 c7 = _u128high((u128)q * d) + (s < c7);
172 }
173 ulong cb = 0;
174 for (mp_size_t i = 0; i < t; ++i) {
175 ulong s = numa[i], l = s - cb;
176 ulong q = l * dinv;
177 cb = _u128high((u128)q * d) + (s < cb);
178 }
179 ulong cj[8] = {c0, c1, c2, c3, c4, c5, c6, c7}, wT = wm, acc = 0;
180 for (int j = 0; j < 7; ++j) {
181 acc += mont63_mul(cj[j], wm, d, mi);
182 acc = acc >= d ? acc - d : acc;
183 wm = mont63_mul(wm, wT, d, mi);
184 }
185 acc += mont63_mul(cj[7], wm, d, mi);
186 acc = acc >= d ? acc - d : acc;
187 acc += cb; /* 底组项权重 B^t*w^0 */
188 acc = acc >= d ? acc - d : acc;
189 if (t) acc = mont63_mul(acc, bt, d, mi); /* ×B^t:N ≡ -B^t*acc */
190 return acc ? d - acc : 0;
191}

引用了 c0, c1, k, lmmp_mod_8chunk_1_(), lmmp_param_assert, MONT63_MAX, mont63_mul(), r2, s , 以及 t.

被这些函数引用 lmmp_mod_8chunk_1_(), lmmp_trialdiv_() , 以及 trialdiv_leg_8_().

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

◆ mont63_mul()

ulong mont63_mul ( ulong a,
ulong b,
ulong m,
ulong m_inv )
inlinestatic

蒙域乘:a*b*R^-1 mod m(R=B)

在文件 mod_chunk.c 第 48 行定义.

48 {
49 return mont63_reduce((u128)a * b, m, m_inv);
50}
static ulong mont63_reduce(u128 t, ulong m, ulong m_inv)

引用了 mont63_mul() , 以及 mont63_reduce().

函数调用图:

◆ mont63_reduce()

ulong mont63_reduce ( u128 t,
ulong m,
ulong m_inv )
inlinestatic

蒙域约化 REDC

警告
m<2^63

在文件 mod_chunk.c 第 37 行定义.

37 {
38 // m < 2^63 时 k*m + t < 2^127,无 129 位溢出
39 ulong k = _u128low(t) * m_inv;
40 u128 sum = (u128)k * m + t;
41 ulong hi = _u128high(sum);
42 return hi >= m ? hi - m : hi;
43}

引用了 k, mont63_reduce() , 以及 t.

函数调用图: