LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
49 lmmp_param_assert(exp > 0);
51 lmmp_param_assert(dst != NULL);
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;
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}
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
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]
#define b1
#define b2
#define n
#define b3
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
uint64_t ulong
定义 numth.h:39
#define b2n
#define mul_b(i)
#define b1n
#define new_b(_i_)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define BALLOC_TYPE(n, type)