LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
pow_basecase.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 "
impl/inlines.h
"
24
#include "mparam.h"
25
#include "
impl/tmp_alloc.h
"
26
#include "
lmmp/lmmpn.h
"
27
#include "
lmmp/numth.h
"
28
29
30
#define mul_b(_i_) \
31
lmmp_mul_(dst, sq, rn, b##_i_, b##_i_##n); \
32
rn += b##_i_##n; \
33
rn -= (dst[rn - 1] == 0) ? 1 : 0
34
35
mp_size_t
lmmp_pow_basecase_
(
mp_ptr
restrict
dst,
mp_size_t
rn,
mp_srcptr
restrict
base,
mp_size_t
n
,
ulong
exp) {
36
lmmp_param_assert
(exp >= 3);
37
lmmp_param_assert
(exp % 2 == 1);
38
TEMP_DECL
;
39
40
#define b1 base
41
#define b1n n
42
mp_ptr
restrict
sq =
TALLOC_TYPE
(rn,
mp_limb_t
);
43
rn =
n
;
44
lmmp_copy
(dst, base,
n
);
45
lmmp_sqr_
(sq, dst, rn);
46
rn <<= 1;
47
rn -= (sq[rn - 1] == 0) ? 1 : 0;
48
int
lz =
lmmp_leading_zeros_
(exp);
49
int
i = 62 - lz;
50
exp <<= lz + 1;
51
/*
52
For the intermediate 0, we will skip it entirely until the next 1,
53
and then perform a multiplication. This can reduce the extra copying
54
caused by sparse 1s and improve efficiency.
55
*/
56
for
( ; i > 0; ) {
57
lz =
lmmp_leading_zeros_
(exp);
58
if
(lz == 0) {
59
mul_b
(1);
60
61
lmmp_sqr_
(sq, dst, rn);
62
rn <<= 1;
63
rn -= (sq[rn - 1] == 0) ? 1 : 0;
64
--i;
65
exp <<= 1;
66
}
else
{
67
int
j = 2;
68
if
(lz & 1) {
69
lmmp_copy
(dst, sq, rn);
70
lmmp_sqr_
(sq, dst, rn);
71
rn <<= 1;
72
rn -= (sq[rn - 1] == 0);
73
++j;
74
for
(; j <= lz; j += 2) {
75
lmmp_sqr_
(dst, sq, rn);
76
rn <<= 1;
77
rn -= (dst[rn - 1] == 0);
78
lmmp_sqr_
(sq, dst, rn);
79
rn <<= 1;
80
rn -= (sq[rn - 1] == 0);
81
}
82
}
else
{
83
for
(; j <= lz; j += 2) {
84
lmmp_sqr_
(dst, sq, rn);
85
rn <<= 1;
86
rn -= (dst[rn - 1] == 0);
87
lmmp_sqr_
(sq, dst, rn);
88
rn <<= 1;
89
rn -= (sq[rn - 1] == 0);
90
}
91
}
92
93
i -= lz;
94
exp <<= lz;
95
}
96
}
97
lmmp_debug_assert
(exp ==
LIMB_B_2
);
98
99
mul_b
(1);
100
101
TEMP_FREE
;
102
return
rn;
103
104
#undef b1
105
#undef b1n
106
#undef new_b
107
}
inlines.h
lmmp_leading_zeros_
#define lmmp_leading_zeros_
定义
inlines.h:162
lmmp_sqr_
#define lmmp_sqr_
定义
inlines.h:168
LIMB_B_2
#define LIMB_B_2
定义
mparam.h:40
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
lmmp_copy
#define lmmp_copy(dst, src, n)
定义
lmmp.h:474
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
lmmp_debug_assert
#define lmmp_debug_assert(x)
定义
lmmp.h:498
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
n
#define n
numth.h
lmmp_pow_basecase_
mp_size_t lmmp_pow_basecase_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算奇数次幂算法 [dst,rn] = [base,n] ^ exp
ulong
uint64_t ulong
定义
numth.h:39
mul_b
#define mul_b(i)
定义
pow_1.c:344
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
tmp_alloc.h
TEMP_DECL
#define TEMP_DECL
定义
tmp_alloc.h:145
TEMP_FREE
#define TEMP_FREE
定义
tmp_alloc.h:175
TALLOC_TYPE
#define TALLOC_TYPE(n, type)
定义
tmp_alloc.h:173
src
lmmp
numth
pow_basecase.c
生成于
, 为 LMMP使用
1.18.0