LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
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 "
support/perf.h
"
24
#include "
lmmp/lmmpn.h
"
25
#include "
lmmp/mprand.h
"
26
#include "
lmmp/numth.h
"
27
28
/*
29
精确除法性能:lmmp_divexact_ 公共入口,尺寸全部落在 basecase 档
30
(nn < DIVEXACT_NN_THRESHOLD 且 dn < DIVEXACT_BASECASE_THRESHOLD)。
31
32
输入构造 n = q*d(q、d 顶 limb 置位),确保整除且商规模确定;
33
计时前用 memcmp 校验 dst == q。
34
*/
35
36
typedef
struct
{
37
mp_ptr
q
;
38
mp_ptr
d
;
39
mp_ptr
np
;
40
mp_ptr
dst
;
41
mp_size_t
qn
;
42
mp_size_t
qa
;
// 实际非零商 limb 数(顶 limb 恒 0)
43
}
DivexactCtx
;
44
45
static
DivexactCtx
make_divexact_ctx
(
mp_size_t
nn,
mp_size_t
dn,
mp_limb_t
seed) {
46
DivexactCtx
c;
47
c.
qn
= nn - dn + 1;
48
c.
qa
= c.
qn
- 1;
49
c.
q
= alloc_limbs(c.
qa
);
50
c.
d
= alloc_limbs(dn);
51
c.
np
= alloc_limbs(nn);
52
c.
dst
= alloc_limbs(c.
qn
+ 1);
53
lmmp_seed_random_
(c.
q
, c.
qa
, seed, 1);
54
lmmp_seed_random_
(c.
d
, dn, seed * 3 + 1, 1);
55
c.
d
[0] |= 1;
56
/* lmmp_mul_ 要求 na >= nb:窄窗形态商短于除数,需交换 */
57
if
(c.
qa
>= dn)
58
lmmp_mul_
(c.
np
, c.
q
, c.
qa
, c.
d
, dn);
59
else
60
lmmp_mul_
(c.
np
, c.
d
, dn, c.
q
, c.
qa
);
61
c.
dst
[c.
qn
] = 0x5eed5eed5eed5eedull;
62
lmmp_divexact_
(c.
dst
, c.
np
, nn, c.
d
, dn);
63
if
(memcmp(c.
dst
, c.
q
, (
size_t
)c.
qa
*
sizeof
(
mp_limb_t
)) != 0 || c.
dst
[c.
qa
] != 0) {
64
printf(
"divexact bench: WRONG QUOTIENT at nn=%lld dn=%lld\n"
, (
long
long
)nn,
65
(
long
long
)dn);
66
}
67
return
c;
68
}
69
70
static
void
free_divexact_ctx
(
const
DivexactCtx
*c) {
71
lmmp_free
(c->
q
);
72
lmmp_free
(c->
d
);
73
lmmp_free
(c->
np
);
74
lmmp_free
(c->
dst
);
75
}
76
77
static
double
bench_divexact
(
mp_size_t
nn,
mp_size_t
dn,
const
bench_options
*o) {
78
DivexactCtx
c =
make_divexact_ctx
(nn, dn, 0x9e3779b97f4a7c15ull + (
mp_limb_t
)nn * 31 + dn);
79
double
us;
80
BENCH_MEASURE
(us, o,
lmmp_divexact_
(c.
dst
, c.
np
, nn, c.
d
, dn); bench_sink += c.
dst
[0];);
81
free_divexact_ctx
(&c);
82
return
us;
83
}
84
85
/* 宽窗(qn >> dn):主循环全宽步进的稳态区 */
86
static
const
mp_size_t
DIVX_WIDE
[][2] = {
87
{16, 3}, {32, 6}, {64, 12}, {128, 24}, {256, 48}, {512, 48},
88
};
89
90
/* 方形窗(qn ≈ dn):dn=min(dn,qn) 截断与收缩尾的受益区 */
91
static
const
mp_size_t
DIVX_SQUARE
[][2] = {
92
{8, 4}, {16, 8}, {32, 16}, {64, 32}, {96, 48},
93
};
94
95
/* 窄窗(qn << dn):仅低 qn limb 生效的截断区 */
96
static
const
mp_size_t
DIVX_NARROW
[][2] = {
97
{24, 16}, {48, 32}, {64, 48}, {72, 48},
98
};
99
100
static
void
run_wide
(
void
) {
101
for
(
size_t
i = 0; i <
ARRAY_SIZE
(
DIVX_WIDE
); ++i) {
102
const
mp_size_t
* sz =
DIVX_WIDE
[i];
103
report_ab(
"divexact wide nn,dn"
, sz[0], sz[1],
bench_divexact
(sz[0], sz[1], &bench_default), 0);
104
}
105
}
106
107
static
void
run_square
(
void
) {
108
for
(
size_t
i = 0; i <
ARRAY_SIZE
(
DIVX_SQUARE
); ++i) {
109
const
mp_size_t
* sz =
DIVX_SQUARE
[i];
110
report_ab(
"divexact square nn,dn"
, sz[0], sz[1],
bench_divexact
(sz[0], sz[1], &bench_default), 0);
111
}
112
}
113
114
static
void
run_narrow
(
void
) {
115
for
(
size_t
i = 0; i <
ARRAY_SIZE
(
DIVX_NARROW
); ++i) {
116
const
mp_size_t
* sz =
DIVX_NARROW
[i];
117
report_ab(
"divexact narrow nn,dn"
, sz[0], sz[1],
bench_divexact
(sz[0], sz[1], &bench_default), 0);
118
}
119
}
120
121
int
main
(
void
) {
122
setvbuf(stdout, NULL, _IONBF, 0);
123
lmmp_global_init
();
124
puts(
"[numth/divexact/wide]"
);
125
run_wide
();
126
puts(
"[numth/divexact/square]"
);
127
run_square
();
128
puts(
"[numth/divexact/narrow]"
);
129
run_narrow
();
130
lmmp_global_deinit
();
131
return
0;
132
}
main
int main(void)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
main.c:26
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
lmmp_free
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
定义
memory.c:437
lmmp_global_init
void lmmp_global_init(void)
全局初始化函数(线程局部的)
定义
global.c:58
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_global_deinit
void lmmp_global_deinit(void)
全局释放函数(线程局部的)
定义
global.c:65
lmmpn.h
lmmp_mul_
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]
mprand.h
lmmp_seed_random_
mp_size_t lmmp_seed_random_(mp_ptr dst, mp_size_t n, mp_limb_t seed, unsigned seed_type)
生成随机大整数(0 - B^n-1 均匀分布)
numth.h
lmmp_divexact_
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)
DivexactCtx::q
mp_ptr q
定义
divexact.c:37
DivexactCtx::qa
mp_size_t qa
定义
divexact.c:42
DivexactCtx::dst
mp_ptr dst
定义
divexact.c:40
DivexactCtx::d
mp_ptr d
定义
divexact.c:38
make_divexact_ctx
static DivexactCtx make_divexact_ctx(mp_size_t nn, mp_size_t dn, mp_limb_t seed)
定义
divexact.c:45
DivexactCtx::qn
mp_size_t qn
定义
divexact.c:41
DIVX_SQUARE
static const mp_size_t DIVX_SQUARE[][2]
定义
divexact.c:91
run_wide
static void run_wide(void)
定义
divexact.c:100
run_square
static void run_square(void)
定义
divexact.c:107
run_narrow
static void run_narrow(void)
定义
divexact.c:114
free_divexact_ctx
static void free_divexact_ctx(const DivexactCtx *c)
定义
divexact.c:70
bench_divexact
static double bench_divexact(mp_size_t nn, mp_size_t dn, const bench_options *o)
定义
divexact.c:77
DIVX_NARROW
static const mp_size_t DIVX_NARROW[][2]
定义
divexact.c:96
DivexactCtx::np
mp_ptr np
定义
divexact.c:39
DIVX_WIDE
static const mp_size_t DIVX_WIDE[][2]
定义
divexact.c:86
DivexactCtx
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
divexact.c:36
perf.h
ARRAY_SIZE
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
perf.h:40
BENCH_MEASURE
#define BENCH_MEASURE(result, options,...)
定义
perf.h:93
bench_options
定义
perf.h:44
src
lmmp
numth
perf
divexact.c
生成于
, 为 LMMP使用
1.18.0