LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
36 lmmp_param_assert(exp >= 3);
37 lmmp_param_assert(exp % 2 == 1);
39
40#define b1 base
41#define b1n n
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 }
98
99 mul_b(1);
100
101 TEMP_FREE;
102 return rn;
103
104#undef b1
105#undef b1n
106#undef new_b
107}
#define lmmp_leading_zeros_
#define lmmp_sqr_
#define LIMB_B_2
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
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
#define n
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
uint64_t ulong
定义 numth.h:39
#define mul_b(i)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)