LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
pow_win2.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 "
impl/tmp_alloc.h
"
25
#include "
lmmp/lmmpn.h
"
26
#include "
lmmp/numth.h
"
27
28
29
#define mul_b(_i_) \
30
if (rsq) { \
31
if (b##_i_##n >= rn) \
32
lmmp_mul_(dst, b##_i_, b##_i_##n, sq, rn); \
33
else \
34
lmmp_mul_(dst, sq, rn, b##_i_, b##_i_##n); \
35
rn += b##_i_##n; \
36
rn -= (dst[rn - 1] == 0) ? 1 : 0; \
37
rsq = false; \
38
} else { \
39
if (b##_i_##n >= rn) \
40
lmmp_mul_(sq, b##_i_, b##_i_##n, dst, rn); \
41
else \
42
lmmp_mul_(sq, dst, rn, b##_i_, b##_i_##n); \
43
rn += b##_i_##n; \
44
rn -= (sq[rn - 1] == 0) ? 1 : 0; \
45
rsq = true; \
46
}
47
48
mp_size_t
lmmp_pow_win2_
(
mp_ptr
restrict
dst,
mp_size_t
rn,
mp_srcptr
restrict
base,
mp_size_t
n
,
ulong
exp) {
49
lmmp_param_assert
(exp > 0);
50
lmmp_param_assert
(
n
> 0);
51
lmmp_param_assert
(dst != NULL);
52
TEMP_DECL
;
53
54
#define b1 base
55
#define b1n n
56
#define new_b(_i_) mp_ptr restrict b##_i_ = TALLOC_TYPE(b##_i_##n, mp_limb_t)
57
58
mp_size_t
b2n
=
n
<< 1, b3n =
b2n
+
n
;
59
new_b
(2);
60
new_b
(3);
61
62
lmmp_sqr_
(
b2
,
b1
,
b1n
);
63
b2n
=
b1n
<< 1;
64
b2n
-=
b2
[
b2n
- 1] == 0 ? 1 : 0;
65
lmmp_mul_
(
b3
,
b2
,
b2n
,
b1
,
b1n
);
66
b3n =
b2n
+
b1n
;
67
b3n -=
b3
[b3n - 1] == 0 ? 1 : 0;
68
69
bool
rsq =
true
;
70
mp_ptr
restrict
sq =
BALLOC_TYPE
(rn,
mp_limb_t
);
71
rn = 1;
72
int
i = 31, j;
73
while
((exp & (0x3ull << ((i--) * 2))) == 0);
74
75
/*
76
模拟一次,让最后一次计算结果恰好是dst,避免最后一次可能的拷贝
77
*/
78
for
(j = i + 1; j != -1; --j) {
79
int
p = (exp & (0x3ull << (j * 2))) >> (j * 2);
80
if
(p != 0)
81
rsq = !rsq;
82
}
83
if
(rsq) {
84
dst[0] = 1;
85
rsq =
false
;
86
}
else
{
87
sq[0] = 1;
88
rsq =
true
;
89
}
90
91
for
(++i; i != -1; --i) {
92
int
p = (exp & (0x3ull << (i * 2))) >> (i * 2);
93
if
(p == 0) {
94
;
95
}
else
if
(p == 1) {
96
mul_b
(1)
97
}
else
if
(p == 2) {
98
mul_b
(2)
99
}
else
{
100
mul_b
(3)
101
}
102
103
if
(i > 0) {
104
if
(rsq) {
105
lmmp_sqr_
(dst, sq, rn);
106
rn <<= 1;
107
rn -= (dst[rn - 1] == 0) ? 1 : 0;
108
lmmp_sqr_
(sq, dst, rn);
109
rn <<= 1;
110
rn -= (sq[rn - 1] == 0) ? 1 : 0;
111
}
else
{
112
lmmp_sqr_
(sq, dst, rn);
113
rn <<= 1;
114
rn -= (sq[rn - 1] == 0) ? 1 : 0;
115
lmmp_sqr_
(dst, sq, rn);
116
rn <<= 1;
117
rn -= (dst[rn - 1] == 0) ? 1 : 0;
118
}
119
}
120
}
121
lmmp_debug_assert
(rsq ==
false
);
122
123
TEMP_FREE
;
124
return
rn;
125
126
#undef b1
127
#undef b1n
128
#undef new_b
129
}
inlines.h
lmmp_sqr_
#define lmmp_sqr_
定义
inlines.h:168
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
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
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]
b1
#define b1
b2
#define b2
n
#define n
b3
#define b3
numth.h
lmmp_pow_win2_
mp_size_t lmmp_pow_win2_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方2比特窗口快速幂算法 [dst,rn] = [base,n] ^ exp
ulong
uint64_t ulong
定义
numth.h:39
b2n
#define b2n
mul_b
#define mul_b(i)
定义
pow_1.c:344
b1n
#define b1n
new_b
#define new_b(_i_)
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
BALLOC_TYPE
#define BALLOC_TYPE(n, type)
定义
tmp_alloc.h:171
src
lmmp
numth
pow_win2.c
生成于
, 为 LMMP使用
1.18.0