44 u64 seed = 0x123456789abcdef0ull;
45 for (
int i = 0; i < 500; ++i) {
46 u32 a = (
u32)(xorshift64(&seed) | 1);
50 u64 b = xorshift64(&seed) | 1;
59 u64 seed = 0x1020304050607080ull;
60 for (
int i = 0; i < 300; ++i) {
62 random_limbs(
a2, 2, &seed);
68 random_limbs(
a3, 3, &seed);
74 random_limbs(
a4, 4, &seed);
82 u64 seed = 0x0f1e2d3c4b5a6978ull;
83 const mp_size_t n_values[] = {1, 2, 3, 4, 5, 10, 20, 40, 80, 120};
84 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
86 mp_ptr a = alloc_limbs(
n), inv = alloc_limbs(
n),
tp = alloc_limbs((5 *
n + 5) / 2);
87 random_limbs(a,
n, &seed);
97 u64 seed = 0xc0ffee1234567890ull;
98 const mp_size_t na_values[] = {8, 40, 80};
99 for (
size_t na_index = 0; na_index <
ARRAY_SIZE(na_values); ++na_index) {
102 mp_ptr a = alloc_limbs(na), inv = alloc_limbs(
n);
103 random_limbs(a, na, &seed);
115 u64 seed = 0x9d1f2e3c4b5a6978ull;
116 const mp_size_t na_values[] = {3, 8, 40};
117 for (
size_t na_index = 0; na_index <
ARRAY_SIZE(na_values); ++na_index) {
119 const u64 top_values[] = {1ull, 4ull, 1ull << 32, 1ull << 63};
120 for (
size_t top_index = 0; top_index <
ARRAY_SIZE(top_values); ++top_index) {
121 u64 top = top_values[top_index];
122 const mp_size_t ni0_values[] = {na, na / 2};
123 for (
size_t ni0_index = 0; ni0_index <
ARRAY_SIZE(ni0_values); ++ni0_index) {
126 mp_ptr a = alloc_limbs(na);
127 mp_ptr q = alloc_limbs(na + ni + 2);
128 random_limbs(a, na, &seed);
136 mp_ptr den = alloc_limbs(dn);
138 memcpy(den + ni, a, (
size_t)na * 8);
140 mp_ptr numer = alloc_limbs(nn);
143 mp_ptr quot = alloc_limbs(nn - dn + 1), rem = alloc_limbs(dn);
144 lmmp_div_(quot, rem, numer, nn, den, dn);
148 mp_ptr diff = alloc_limbs(ln + 1);
154 for (
mp_size_t i = 1; i < ln; ++i) small = small && (diff[i] == 0);
155 TEST_CHECK_MSG(small && diff[0] <= 2,
"bninv close to reference quotient");
164TEST_CASE(
"numth/binvert", binvert_unbalanced_variants) {
165 u64 seed = 0xa1b2c3d4e5f60718ull;
168 const mp_size_t n_values[] = {2, 3, 5, 10, 30, 80};
169 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
171 mp_ptr a = alloc_limbs(1), inv = alloc_limbs(
n);
172 a[0] = xorshift64(&seed) | 1;
179 const mp_size_t n_values2[] = {3, 4, 10, 30, 80};
180 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values2); ++n_index) {
182 mp_ptr a = alloc_limbs(2), inv = alloc_limbs(
n);
183 random_limbs(a, 2, &seed);
191 const mp_size_t n_values3[] = {3, 5, 10, 30, 80};
192 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values3); ++n_index) {
196 if (na >=
n) na =
n - 1;
197 mp_ptr a = alloc_limbs(na), inv = alloc_limbs(
n),
tp = alloc_limbs((9 * na + 5) / 2 + 1);
198 random_limbs(a, na, &seed);
211 TEST_RUN(
"numth/binvert", binvert_uint_ulong);
212 TEST_RUN(
"numth/binvert", binvert_2_3_4);
213 TEST_RUN(
"numth/binvert", binvert_n_dc);
214 TEST_RUN(
"numth/binvert", binvert_near_balanced);
215 TEST_RUN(
"numth/binvert", bninv_power2_top_limb);
216 TEST_RUN(
"numth/binvert", binvert_unbalanced_variants);
#define lmmp_zero(dst, n)
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
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]
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
void lmmp_binvert_unbalance_1_(mp_ptr dst, mp_limb_t a, mp_size_t n)
计算 a 在 B^n 下的逆元
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
void lmmp_binvert_n_dc_(mp_ptr dst, mp_srcptr numa, mp_size_t n, mp_ptr tp)
计算 [numa,n] 在 B^n 下的逆元
uint lmmp_binvert_uint_(uint a)
计算 a 在2^32下的逆元
void lmmp_binvert_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n, mp_ptr tp)
计算 [numa,na] 在 B^n 下的逆元
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
void lmmp_binvert_3_(mp_ptr dst, mp_srcptr numa)
计算 [numa,3] 在 B^3 下的逆元
void lmmp_binvert_4_(mp_ptr dst, mp_srcptr numa)
计算 [numa,4] 在 B^4 下的逆元
void lmmp_binvert_unbalance_2_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
计算 [numa,2] 在 B^n 下的逆元
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CHECK_MSG(cond, msg)
#define TEST_CASE(category, name)
#define TEST_CHECK_EQ(a, b)
#define TEST_RUN(category, name)
static void verify_inverse(const mp_limb_t *num, mp_size_t na, const mp_limb_t *dst, mp_size_t n)
Copyright (C) 2026 HJimmyK (Jericho Knox)