LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
36typedef struct {
42 mp_size_t qa; // 实际非零商 limb 数(顶 limb 恒 0)
44
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
70static 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
77static 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];);
82 return us;
83}
84
85/* 宽窗(qn >> dn):主循环全宽步进的稳态区 */
86static 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) 截断与收缩尾的受益区 */
91static 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 生效的截断区 */
96static const mp_size_t DIVX_NARROW[][2] = {
97 {24, 16}, {48, 32}, {64, 48}, {72, 48},
98};
99
100static 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
107static 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
114static 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
121int main(void) {
122 setvbuf(stdout, NULL, _IONBF, 0);
124 puts("[numth/divexact/wide]");
125 run_wide();
126 puts("[numth/divexact/square]");
127 run_square();
128 puts("[numth/divexact/narrow]");
129 run_narrow();
131 return 0;
132}
int main(void)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 main.c:26
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)
void lmmp_global_init(void)
全局初始化函数(线程局部的)
uint64_t mp_limb_t
定义 lmmp.h:92
void lmmp_global_deinit(void)
全局释放函数(线程局部的)
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_size_t lmmp_seed_random_(mp_ptr dst, mp_size_t n, mp_limb_t seed, unsigned seed_type)
生成随机大整数(0 - B^n-1 均匀分布)
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)
mp_size_t qa
static DivexactCtx make_divexact_ctx(mp_size_t nn, mp_size_t dn, mp_limb_t seed)
mp_size_t qn
static const mp_size_t DIVX_SQUARE[][2]
static void run_wide(void)
static void run_square(void)
static void run_narrow(void)
static void free_divexact_ctx(const DivexactCtx *c)
static double bench_divexact(mp_size_t nn, mp_size_t dn, const bench_options *o)
static const mp_size_t DIVX_NARROW[][2]
static const mp_size_t DIVX_WIDE[][2]
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define BENCH_MEASURE(result, options,...)
定义 perf.h:93