LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_div.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 "mparam.h"
25#include "cases.h"
27
28#include <string.h>
29
30// 恒等式重建:q*d + r == n 且 r < d(乘法/加法全用库内路径)
31static void verify_div_relation(const mp_limb_t* n, mp_size_t na, const mp_limb_t* d, mp_size_t nb,
32 const mp_limb_t* q, mp_size_t qn, const mp_limb_t* r, mp_size_t rn) {
33 TEST_CHECK_MSG(mpn_cmp(r, rn, d, nb) < 0, "r < d");
34
35 mp_ptr t = alloc_limbs(na + 1);
36 lmmp_mul_(t, q, qn, d, nb); // t = q*d(qn >= nb 由调用方保证)
37 // t += r:r 零垫到 na+1 长后 add_n
38 mp_ptr rpad = alloc_limbs(na + 1);
39 memset(rpad, 0, (size_t)(na + 1) * 8);
40 memcpy(rpad, r, (size_t)rn * 8);
41 lmmp_add_n_(t, t, rpad, na + 1);
42 TEST_CHECK_MSG(mpn_eq(t, na + 1, n, na), "q*d+r == n");
43 lmmp_free(t);
44 lmmp_free(rpad);
45}
46
47TEST_CASE("div/single", div_1_mod_1) {
48 u64 seed = 0x3141592653589793ull;
49 for (size_t n = 1; n <= 80; ++n) {
50 for (int iter = 0; iter < 10; ++iter) {
51 mp_ptr a = alloc_limbs(n), q = alloc_limbs(n + 1), t = alloc_limbs(n + 1),
52 acopy = alloc_limbs(n);
53 random_limbs(a, n, &seed);
54 u64 x = xorshift64(&seed) | 1;
55
56 u64 rem = lmmp_mod_1_(a, n, x);
57 TEST_CHECK(rem < x);
58 u64 ret_rem = lmmp_div_1_(q, a, n, x);
59 TEST_CHECK_EQ(ret_rem, rem);
60
61 // mod_preinv_1: 同一 (x) 的预备逆元版,结果与 mod_1_ 一致
63 u64 inv = lmmp_inv_1_(x << k);
64 u64 rem_pi = lmmp_mod_preinv_1_(a, n, x, inv, k);
65 TEST_CHECK_EQ(rem_pi, rem);
66
67 // 重建:q*x + rem == a
68 u64 hi = lmmp_mul_1_(t, q, n, x);
69 t[n] = hi;
70 add_small_inplace(t, n + 1, rem);
71 TEST_CHECK(mpn_eq(t, n + 1, a, n));
72
73 // div_1_s: 归一化单精度除法(x 顶位为 1 档),结果与 div_1 一致
74 if (n > 1 && x >= LIMB_B_2) {
75 memcpy(acopy, a, n * 8);
76 u64 qh = lmmp_div_1_s_(q, acopy, n, x);
77 TEST_CHECK_EQ(acopy[0], rem);
78 TEST_CHECK_EQ(qh, q[n - 1]); // 商顶 limb
79 // 商低 n-1 limbs 与 div_1 一致(div_1 已由重建验证)
80 mp_ptr q2 = alloc_limbs(n + 1);
81 lmmp_div_1_(q2, a, n, x);
82 TEST_CHECK_EQ(memcmp(q, q2, (n - 1) * 8), 0);
83 lmmp_free(q2);
84 }
85
86 lmmp_free(a); lmmp_free(q); lmmp_free(t); lmmp_free(acopy);
87 }
88 }
89}
90
91TEST_CASE("div/single", mod_preinv_1_boundary) {
92 // 定向边界除数:x=1(k=63) / 2 的幂 / 归一化档(k=0, MSB=1) / B-1 档 / 一般奇偶
93 const u64 divisors[] = {
94 1, 2, 3, 5, 7, 0xFFFF, 0x100000001ull,
95 1ull << 62, (1ull << 62) + 1, (1ull << 62) - 1,
96 1ull << 63, (1ull << 63) + 1, (1ull << 63) - 1,
97 ~0ull, ~0ull - 1ull, ~0ull - 2ull, 0x123456789ABCDEFFull,
98 };
99 u64 seed = 0x89ABCDEF01234567ull;
100 for (size_t x_index = 0; x_index < ARRAY_SIZE(divisors); ++x_index) {
101 u64 x = divisors[x_index];
102 const u64 k = lmmp_leading_zeros_(x);
103 const u64 inv = lmmp_inv_1_(x << k);
104 for (size_t n = 1; n <= 34; ++n) {
105 for (int iter = 0; iter < 6; ++iter) {
106 mp_ptr a = alloc_limbs(n);
107 random_limbs(a, n, &seed);
108 u64 rem = lmmp_mod_1_(a, n, x);
109 u64 rem_pi = lmmp_mod_preinv_1_(a, n, x, inv, k);
110 TEST_CHECK_EQ(rem_pi, rem);
111 TEST_CHECK(rem_pi < x);
112
113 // 高位 0 容忍档:契约未要求归一化
114 a[n - 1] = 0;
115 rem = lmmp_mod_1_(a, n, x);
116 rem_pi = lmmp_mod_preinv_1_(a, n, x, inv, k);
117 TEST_CHECK_EQ(rem_pi, rem);
118 lmmp_free(a);
119 }
120 }
121 }
122}
123
124TEST_CASE("div/general", div_general_relation) {
125 u64 seed = 0x2718281828459045ull;
126 const mp_size_t sizes[][2] = {
127 {2, 1}, {3, 1}, {5, 2}, {10, 3}, {20, 5}, {30, 10},
128 {50, 10}, {80, 20}, {120, 30}, {200, 50}, {350, 80},
129 {600, 120}, {900, 200}, {1400, 300}, {1900, 400}, {2500, 500}
130 };
131 for (size_t c_index = 0; c_index < ARRAY_SIZE(sizes); ++c_index) {
132 const mp_size_t *c = sizes[c_index];
133 mp_size_t na = c[0], nb = c[1];
134 mp_ptr n = alloc_limbs(na), d = alloc_limbs(nb);
135 mp_ptr q = alloc_limbs(na - nb + 1), r = alloc_limbs(nb);
136 random_limbs(n, na, &seed);
137 random_limbs(d, nb, &seed); // MSB=1,除数归一化
138
139 lmmp_div_(q, r, n, na, d, nb);
140 verify_div_relation(n, na, d, nb, q, na - nb + 1, r, nb);
141
143 }
144}
145
146TEST_CASE("div/normalized", div_s_normalized_relation) {
147 u64 seed = 0x0badcafef00dfaceull;
148 const mp_size_t sizes[][2] = {
149 {3, 1}, {4, 2}, {10, 3}, {30, 10}, {60, 20}, {120, 40},
150 {300, 80}, {700, 150}, {1200, 300}, {1900, 400}
151 };
152 for (size_t c_index = 0; c_index < ARRAY_SIZE(sizes); ++c_index) {
153 const mp_size_t *c = sizes[c_index];
154 mp_size_t na = c[0], nb = c[1];
155 mp_ptr numa = alloc_limbs(na), numb = alloc_limbs(nb), nsave = alloc_limbs(na);
156 mp_ptr q = alloc_limbs(na - nb + 2);
157 random_limbs(numa, na, &seed);
158 random_limbs(numb, nb, &seed); // MSB=1,已归一化
159 memcpy(nsave, numa, (size_t)na * 8);
160
161 mp_limb_t qh = lmmp_div_s_(q, numa, na, numb, nb);
162 // 完整商 = q[0..na-nb-1] ++ [qh],余数 = [numa, nb]
163 q[na - nb] = qh;
164 verify_div_relation(nsave, na, numb, nb, q, na - nb + 1, numa, nb);
165
166 lmmp_free(numa); lmmp_free(numb); lmmp_free(nsave); lmmp_free(q);
167 }
168}
169
170TEST_CASE("div/basecase_divide", div_basecase_vs_divide) {
171 u64 seed = 0x1020304050607080ull;
172 const mp_size_t sizes[][2] = {
173 {6, 3}, {10, 4}, {20, 6}, {40, 10}, {60, 20}, {100, 30}, {160, 40}, {220, 50}
174 };
175 for (size_t c_index = 0; c_index < ARRAY_SIZE(sizes); ++c_index) {
176 const mp_size_t *c = sizes[c_index];
177 mp_size_t na = c[0], nb = c[1];
178 if (na < nb + 1) continue;
179 mp_ptr numa1 = alloc_limbs(na);
180 mp_ptr numa2 = alloc_limbs(na);
181 mp_ptr numb = alloc_limbs(nb);
182 mp_ptr q1 = alloc_limbs(na - nb + 1);
183 mp_ptr q2 = alloc_limbs(na - nb + 1);
184 random_limbs(numa1, na, &seed);
185 random_limbs(numb, nb, &seed);
186 memcpy(numa2, numa1, na * 8);
187
188 mp_limb_t inv21 = lmmp_inv_2_1_(numb[nb - 1], numb[nb - 2]);
189 mp_limb_t qh1 = lmmp_div_basecase_(q1, numa1, na, numb, nb, inv21);
190
191 // basecase 自身恒等式(全部尺寸;小除数档无 divide 对照时是唯一验证)
192 {
193 q1[na - nb] = qh1;
194 verify_div_relation(numa2, na, numb, nb, q1, na - nb + 1, numa1, nb);
195 }
196
197 // div_divide_ 的前置条件为 nb>=6 且 na>=2*nb。
198 if (nb >= 6 && na >= 2 * nb) {
199 mp_limb_t qh2 = lmmp_div_divide_(q2, numa2, na, numb, nb, inv21);
200 TEST_CHECK_EQ(qh1, qh2);
201 for (mp_size_t i = 0; i < na - nb; ++i) TEST_CHECK_EQ(q1[i], q2[i]);
202 for (mp_size_t i = 0; i < nb; ++i) TEST_CHECK_EQ(numa1[i], numa2[i]);
203 }
204
205 lmmp_free(numa1); lmmp_free(numa2); lmmp_free(numb); lmmp_free(q1); lmmp_free(q2);
206 }
207}
208
209/*
210 inv_1 契约:inv = floor((B^2-1)/x) - B,即 x*(B+inv) ∈ (B^2-1-x, B^2-1]。
211 积经 mul_1 双 limb 折算(x*B 并入高半,无溢出)。
212*/
213TEST_CASE("div/inv", inv_1_inv_2_1) {
214 u64 seed = 0x0f0e0d0c0b0a0908ull;
215
216 for (int i = 0; i < 500; ++i) {
217 u64 x = xorshift64(&seed) | LIMB_B_2; // inv_1_ 要求 MSB(x)=1
218 u64 inv = lmmp_inv_1_(x);
219 mp_limb_t prod[2];
220 u64 hi = lmmp_mul_1_(prod, &x, 1, inv);
221 prod[1] = hi;
222 u64 p_hi = prod[1] + x;
223 TEST_CHECK_EQ(p_hi, ~(u64)0);
224 TEST_CHECK(prod[0] >= (u64)(0 - x));
225 }
226
227 // inv_2_1 与 div_basecase 的交叉验证已在上一用例覆盖;此处仅非零检查。
228 for (int i = 0; i < 200; ++i) {
229 u64 xh = xorshift64(&seed) | LIMB_B_2;
230 u64 xl = xorshift64(&seed);
231 mp_limb_t inv = lmmp_inv_2_1_(xh, xl);
232 TEST_CHECK_MSG(inv != 0, "inv_2_1 nonzero");
233 }
234}
235
236void test_div(void) {
237 TEST_RUN("div/single", div_1_mod_1);
238 TEST_RUN("div/single", mod_preinv_1_boundary);
239 TEST_RUN("div/general", div_general_relation);
240 TEST_RUN("div/normalized", div_s_normalized_relation);
241 TEST_RUN("div/basecase_divide", div_basecase_vs_divide);
242 TEST_RUN("div/inv", inv_1_inv_2_1);
243}
#define k
#define prod
#define lmmp_leading_zeros_
#define LIMB_B_2
mp_limb_t * mp_ptr
定义 lmmp.h:96
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)
void test_div(void)
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
mp_limb_t lmmp_div_1_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_limb_t x)
单精度数除法(除数为1个limb)
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
mp_limb_t lmmp_mod_preinv_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x, mp_limb_t inv, mp_limb_t k)
单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_
定义 div.c:89
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
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
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
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)
基础除法运算
mp_limb_t lmmp_div_divide_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
分治除法运算
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
#define t
#define numb
#define n
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK(cond)
定义 test.h:37
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#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
static void verify_div_relation(const mp_limb_t *n, mp_size_t na, const mp_limb_t *d, mp_size_t nb, const mp_limb_t *q, mp_size_t qn, const mp_limb_t *r, mp_size_t rn)
Copyright (C) 2026 HJimmyK (Jericho Knox)