LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_divexact.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 "lmmp/lmmpn.h"
24#include "lmmp/numth.h"
25#include "cases.h"
27
28#include <string.h>
29
30/*
31 精确除法验证:被除数经库乘法构造为 q*d(保证整除),各精确除法
32 变体须还原 q;并与普通除法 lmmp_div_ 交叉(商一致、余数为零)。
33 binvert 逆元经 mullh 低 64 位 == 1 验证。
34*/
35
36TEST_CASE("numth/divexact", divexact_1) {
37 u64 seed = 0x1111222233334444ull;
38 for (mp_size_t n = 1; n <= 120; ++n) {
39 for (int iter = 0; iter < 8; ++iter) {
40 u64 d = xorshift64(&seed) | 1;
41 u64 dinv = lmmp_binvert_ulong_(d);
42 mp_limb_t iv[2];
43 lmmp_mullh_(d, dinv, iv);
44 TEST_CHECK_EQ(iv[0], 1ull); // d*dinv ≡ 1 (mod B):低 limb 为 1 即可
45
46 // np = q*d 保留进位 limb(hi!=0 时为 n+1 limb 积,恰覆盖
47 // 顶 limb 非零形态;偶数迭代压制 q 顶位使两种形态都出现)
48 mp_ptr q = alloc_limbs(n), np = alloc_limbs(n + 1), dst = alloc_limbs(n + 1);
49 random_limbs_with_top(q, n, &seed, false);
50 if (iter % 2 == 0) q[n - 1] >>= 1; // 半数迭代强制 hi==0 形态
51 u64 hi = lmmp_mul_1_(np, q, n, d);
52 mp_size_t nn = n;
53 if (hi) np[n] = hi, nn = n + 1;
54 // 哨兵:nn==n 时被调只写 n limb(dst[n] 须原样),nn>n 时
55 // 恰写 nn limb、顶 limb 须被主动写 0(预置 0 会掩盖漏写)
56 const mp_limb_t sent = UINT64_C(0x5a5af00dcafebeef);
57 dst[n] = sent;
58 mp_ptr q2 = alloc_limbs(n + 1);
59 q2[n] = sent;
60
61 lmmp_divexact_1_(dst, np, nn, d, dinv);
62 TEST_CHECK_EQ(memcmp(dst, q, n * 8), 0);
63 if (nn > n)
64 TEST_CHECK_EQ(dst[n], 0ull);
65 else
66 TEST_CHECK_EQ(dst[n], sent);
67
68 // 与普通除法交叉:余数 0、商一致(同哨兵规则:写 na limb)
69 u64 rem = lmmp_div_1_(q2, np, nn, d);
70 TEST_CHECK_EQ(rem, 0ull);
71 TEST_CHECK_EQ(memcmp(q2, q, n * 8), 0);
72 if (nn > n)
73 TEST_CHECK_EQ(q2[n], 0ull);
74 else
75 TEST_CHECK_EQ(q2[n], sent);
76
77 lmmp_free(q); lmmp_free(np); lmmp_free(dst); lmmp_free(q2);
78 }
79 }
80}
81
82TEST_CASE("numth/divexact", divexact_2) {
83 u64 seed = 0x5555666677778888ull;
84 for (mp_size_t n = 3; n <= 80; ++n) { // n=3 覆盖 3 limb 被除数最小路径
85 for (int iter = 0; iter < 8; ++iter) {
86 // 商实际为 n-2 个 limb;divexact_2 会写 n-1 个 limb,最高位为 0。
87 mp_ptr q = alloc_limbs(n - 2), d = alloc_limbs(2), np = alloc_limbs(n),
88 dst = alloc_limbs(n - 1), dinv = alloc_limbs(2);
89 random_limbs_with_top(q, n - 2, &seed, false);
90 random_limbs(d, 2, &seed);
91 d[0] |= 1;
92 if (n == 3)
93 lmmp_mul_(np, d, 2, q, 1); // na=1<nb=2:交换操作数序保 mul_ 契约
94 else
95 lmmp_mul_(np, q, n - 2, d, 2); // np = q*d(恰 n limbs)
96
97 lmmp_binvert_2_(dinv, d);
98 lmmp_divexact_2_(dst, np, n, d, dinv);
99 TEST_CHECK_EQ(memcmp(dst, q, (n - 2) * 8), 0);
100 TEST_CHECK_EQ(dst[n - 2], 0u);
101
102 lmmp_free(q); lmmp_free(d); lmmp_free(np); lmmp_free(dst); lmmp_free(dinv);
103 }
104 }
105}
106
107TEST_CASE("numth/divexact", divexact_basecase_divide_cross) {
108 u64 seed = 0x1234432187655678ull;
109 typedef struct { mp_size_t nn; mp_size_t dn; } Case;
110 const Case cases[] = {
111 {2, 1}, {3, 1}, {5, 2}, {10, 3}, {20, 5}, {40, 10},
112 {60, 20}, {100, 30}, {150, 40}, {250, 60}, {400, 80},
113 // 近平衡形态(dn >= nn-dn+1):激活 divexact_divide_ 分支
114 {9, 8}, {12, 10}, {61, 41}, {100, 60}, {200, 120}
115 };
116 for (size_t c_index = 0; c_index < ARRAY_SIZE(cases); ++c_index) {
117 const Case c = cases[c_index];
118 mp_size_t nn = c.nn, dn = c.dn;
119 for (int iter = 0; iter < 5; ++iter) {
120 mp_ptr d = alloc_limbs(dn);
121 random_limbs(d, dn, &seed);
122 d[0] |= 1;
123
124 mp_size_t qn = nn - dn + 1;
125 // 生成 qn-1 个非零 limb 的商;最高位(qn-1)由库写为 0。
126 mp_size_t q_actual = qn - 1;
127 mp_ptr q = alloc_limbs(q_actual > 0 ? q_actual : 1);
128 random_limbs_with_top(q, q_actual, &seed, false);
129 mp_ptr np = alloc_limbs(nn);
130 mul_sorted(np, q, q_actual, d, dn); // np = q*d(近平衡时 q 短于 d)
131
132 // 通用精确除法
133 mp_ptr dst1 = alloc_limbs(qn + 1), np1 = alloc_limbs(nn);
134 memcpy(np1, np, nn * 8);
135 lmmp_divexact_(dst1, np1, nn, d, dn);
136 TEST_CHECK_EQ(memcmp(dst1, q, q_actual * 8), 0);
137 TEST_CHECK_EQ(dst1[q_actual], 0u);
138
139 // 分治精确除法
140 mp_ptr dst2 = alloc_limbs(qn + 1), np2 = alloc_limbs(nn);
141 memcpy(np2, np, nn * 8);
142 if (dn >= qn) { // divexact_divide 要求 dn >= nn-dn+1
143 lmmp_divexact_divide_(dst2, np2, nn, d, dn);
144 TEST_CHECK_EQ(memcmp(dst2, q, q_actual * 8), 0);
145 TEST_CHECK_EQ(dst2[q_actual], 0u);
146 }
147
148 // 朴素精确除法
149 mp_ptr dst3 = alloc_limbs(qn + 1), np3 = alloc_limbs(nn);
150 memcpy(np3, np, nn * 8);
151 lmmp_divexact_basecase_(dst3, np3, nn, d, dn);
152 TEST_CHECK_EQ(memcmp(dst3, q, q_actual * 8), 0);
153 TEST_CHECK_EQ(dst3[q_actual], 0u);
154
155 // 不平衡精确除法(自动逆元)
156 mp_ptr dst4 = alloc_limbs(qn + 1), np4 = alloc_limbs(nn);
157 memcpy(np4, np, nn * 8);
158 lmmp_divexact_unbalance_(dst4, np4, nn, d, dn, NULL);
159 TEST_CHECK_EQ(memcmp(dst4, q, q_actual * 8), 0);
160 TEST_CHECK_EQ(dst4[q_actual], 0u);
161
162 // 与普通除法交叉(用户指定对照):商一致、余数恰为零
163 mp_ptr qd = alloc_limbs(nn - dn + 2), rd = alloc_limbs(dn);
164 lmmp_zero(qd, nn - dn + 2); lmmp_zero(rd, dn);
165 lmmp_div_(qd, rd, np, nn, d, dn);
166 TEST_CHECK_EQ(norm_len(rd, dn), (mp_size_t)0);
167 TEST_CHECK(mpn_eq(qd, nn - dn + 2, q, q_actual));
168
169 lmmp_free(d); lmmp_free(q); lmmp_free(np);
170 lmmp_free(dst1); lmmp_free(np1); lmmp_free(dst2); lmmp_free(np2);
171 lmmp_free(dst3); lmmp_free(np3); lmmp_free(dst4); lmmp_free(np4);
172 lmmp_free(qd); lmmp_free(rd);
173 }
174 }
175}
176
177TEST_CASE("numth/divexact", divexact_unbalanced_preinv) {
178 u64 seed = 0x0a0b0c0d0e0f0102ull;
179 const mp_size_t dn_values[] = {1, 2, 3, 10, 30};
180 for (size_t dn_index = 0; dn_index < ARRAY_SIZE(dn_values); ++dn_index) {
181 mp_size_t dn = dn_values[dn_index];
182 for (mp_size_t nn = dn + 1; nn <= dn + 40; ++nn) {
183 mp_ptr d = alloc_limbs(dn);
184 random_limbs(d, dn, &seed);
185 d[0] |= 1;
186 mp_size_t qn = nn - dn + 1;
187 mp_size_t q_actual = qn - 1;
188 mp_ptr q = alloc_limbs(q_actual > 0 ? q_actual : 1);
189 random_limbs_with_top(q, q_actual, &seed, false);
190 mp_ptr np = alloc_limbs(nn);
191 if (q_actual >= dn) lmmp_mul_(np, q, q_actual, d, dn);
192 else lmmp_mul_(np, d, dn, q, q_actual);
193
194 mp_ptr dinv = alloc_limbs(dn + 1);
195 lmmp_binvert_(dinv, d, dn, dn); // 关于 B^dn 的逆元
196 mp_ptr dst = alloc_limbs(qn + 1), np2 = alloc_limbs(nn);
197 memcpy(np2, np, nn * 8);
198 lmmp_divexact_unbalance_(dst, np2, nn, d, dn, dinv);
199 TEST_CHECK_EQ(memcmp(dst, q, q_actual * 8), 0);
200 TEST_CHECK_EQ(dst[q_actual], 0u);
201
202 lmmp_free(d); lmmp_free(q); lmmp_free(np); lmmp_free(dinv); lmmp_free(dst);
203 lmmp_free(np2);
204 }
205 }
206}
207
208void test_divexact(void) {
209 TEST_RUN("numth/divexact", divexact_1);
210 TEST_RUN("numth/divexact", divexact_2);
211 TEST_RUN("numth/divexact", divexact_basecase_divide_cross);
212 TEST_RUN("numth/divexact", divexact_unbalanced_preinv);
213}
#define lmmp_mullh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
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_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_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
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 n
void test_divexact(void)
void lmmp_divexact_unbalance_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_ptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
void lmmp_divexact_basecase_(mp_ptr dst, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
void lmmp_divexact_1_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_limb_t d, mp_limb_t dinv)
精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
void lmmp_divexact_2_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_srcptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0)
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
void lmmp_divexact_divide_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_CHECK_EQ(a, b)
定义 test.h:39
#define TEST_RUN(category, name)
定义 test.h:36