LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
gcd.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/numth.h
"
26
27
static
double
bench_gcd_lehmer
(
mp_size_t
n
,
const
bench_options
*o) {
28
mp_ptr
a = alloc_limbs(
n
), b = alloc_limbs(
n
), d = alloc_limbs(
n
);
29
fill_random(a,
n
, 0x120bce34ba89eull +
n
);
30
fill_random(b,
n
, 0x2cab5423322191ull +
n
* 3);
31
a[
n
- 1] |= (
mp_limb_t
)1 << 63;
32
b[
n
- 1] >>= 1;
33
if
(b[
n
- 1] == 0) b[
n
- 1] = 1;
34
a[0] |= 1;
35
b[0] |= 1;
/* 契约:输入须归一化(顶 limb 非零)且 a>=b */
36
double
us;
37
BENCH_MEASURE
(us, o, bench_sink += (
mp_limb_t
)
lmmp_gcd_lehmer_
(d, a,
n
, b,
n
););
38
lmmp_free
(a);
39
lmmp_free
(b);
40
lmmp_free
(d);
41
return
us;
42
}
43
44
static
double
bench_gcd_hgcd
(
mp_size_t
n
,
const
bench_options
*o) {
45
mp_ptr
a = alloc_limbs(
n
), b = alloc_limbs(
n
), d = alloc_limbs(
n
);
46
fill_random(a,
n
, 0x120e3489bce1ull +
n
);
47
fill_random(b,
n
, 0x92cab5432211ull +
n
* 3);
48
a[
n
- 1] |= (
mp_limb_t
)1 << 63;
49
b[
n
- 1] >>= 1;
50
if
(b[
n
- 1] == 0) b[
n
- 1] = 1;
51
a[0] |= 1;
52
b[0] |= 1;
/* 契约:输入须归一化且 un>=vn */
53
double
us;
54
BENCH_MEASURE
(us, o, bench_sink += (
mp_limb_t
)
lmmp_gcd_hgcd_
(d, a,
n
, b,
n
););
55
lmmp_free
(a);
56
lmmp_free
(b);
57
lmmp_free
(d);
58
return
us;
59
}
60
61
static
void
run_lehmer
(
void
) {
62
const
mp_size_t
SZ[] = {200, 1000, 2000};
63
for
(
size_t
i = 0; i <
ARRAY_SIZE
(SZ); ++i) {
64
mp_size_t
n
= SZ[i];
65
report_n(
"gcd_lehmer"
,
n
,
bench_gcd_lehmer
(
n
, &bench_default),
n
* 8.0);
66
}
67
}
68
69
static
void
run_hgcd
(
void
) {
70
const
mp_size_t
SZ[] = {64, 1000, 5000, 20000};
71
for
(
size_t
i = 0; i <
ARRAY_SIZE
(SZ); ++i) {
72
mp_size_t
n
= SZ[i];
73
report_n(
"gcd_hgcd"
,
n
,
bench_gcd_hgcd
(
n
, &bench_default),
n
* 8.0);
74
}
75
}
76
77
int
main
(
void
) {
78
setvbuf(stdout, NULL, _IONBF, 0);
79
lmmp_global_init
();
80
puts(
"[numth/gcd/lehmer]"
);
81
run_lehmer
();
82
puts(
"[numth/gcd/hgcd]"
);
83
run_hgcd
();
84
lmmp_global_deinit
();
85
return
0;
86
}
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
n
#define n
numth.h
lmmp_gcd_lehmer_
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
定义
gcd_lehmer.c:159
lmmp_gcd_hgcd_
mp_size_t lmmp_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
定义
hgcd.c:1217
run_lehmer
static void run_lehmer(void)
定义
gcd.c:61
run_hgcd
static void run_hgcd(void)
定义
gcd.c:69
bench_gcd_lehmer
static double bench_gcd_lehmer(mp_size_t n, const bench_options *o)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
gcd.c:27
bench_gcd_hgcd
static double bench_gcd_hgcd(mp_size_t n, const bench_options *o)
定义
gcd.c:44
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
gcd.c
生成于
, 为 LMMP使用
1.18.0