LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
pow.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 <math.h>
24
25#include "impl/inlines.h"
26#include "mparam.h"
27#include "impl/tmp_alloc.h"
28#include "lmmp/lmmpn.h"
29#include "lmmp/numth.h"
30
31
32/**
33 * @brief 将x转换为不小于x的double(提取高53位)
34 * @param x 输入
35 * @return double值d,满足 d >= x 且 d/x <= 1 + 2^-52
36 * @note 仅当x超出53位有效数字时,舍弃低位并对高位进位。
37 * pow的位数估计中,exp可达2^64,超出双精度有效数字,
38 * 提取高位既保留全部有效数字,又保证转换不会引入低估。
39 */
40static inline double ulong_upper_d(ulong x) {
41 int bits = lmmp_limb_bits_(x);
42 if (bits <= 53) {
43 return (double)x; // 本身可精确表示
44 }
45 int sh = bits - 53;
46 uint64_t h = x >> sh;
47 h += (x & (((uint64_t)1 << sh) - 1)) != 0; // 舍弃非0低位时进位
48 return ldexp((double)h, sh);
49}
50
51/**
52 * @brief 计算floor(r)+1并转为mp_size_t
53 * @param r 位数估计值(非负)
54 * @return floor(r)+1,即以bit计的长度;超出64bit范围时钳制为最大值
55 * @note 位数 = floor(log2(x))+1。当估计值恰为整数(如底数是2的幂)时,
56 * ceil会少计1bit,故统一使用floor+1
57 */
58static inline mp_size_t floor1_u64(double r) {
59 if (r >= 0x1p63) {
60 return MP_SIZE_MAX;
61 }
62 return (mp_size_t)floor(r) + 1;
63}
64
66 lmmp_param_assert(base >= 1);
67 lmmp_param_assert(exp > 0);
68 if (base == 1) {
69 return 1;
70 } else if (exp <= 2) {
71 return 3;
72 } else {
73 /*
74 base = mant * 2^E,E = bits(base)-1,mant in [1,2]。
75 base^exp 的位数为 exp*log2(mant) + exp*E:
76 整数部分 exp*E 走整数运算;log2 仅作用于 [1,2] 区间
77 (ulp为2^-52,完整保留53位有效数字),exp 提取高53位并
78 向上舍入为double,保证转换不引入低估。
79 */
80 int bits = lmmp_limb_bits_(base);
81 double mant;
82 if (bits <= 53) {
83 mant = ldexp((double)base, 1 - bits);
84 } else {
85 // 高53位无条件进位:base < h*2^(bits-53)
86 uint64_t h = (base >> (bits - 53)) + 1;
87 mant = ldexp((double)h, -52); // in (1,2]
88 }
89 double expd = ulong_upper_d(exp);
90 mp_size_t rn = floor1_u64(expd * log2(mant));
91 if (rn == MP_SIZE_MAX) {
92 return rn;
93 }
94 mp_size_t l = floor1_u64(expd * (double)(bits - 1));
95 if (l == MP_SIZE_MAX) {
96 return l;
97 }
98 rn += l;
99 return (rn + LIMB_BITS - 1) / LIMB_BITS + 2;
100 }
101}
102
104 lmmp_param_assert(n > 0);
105 lmmp_param_assert(base[n - 1] != 0);
106 if (n == 1) {
107 return lmmp_pow_1_size_(base[0], exp);
108 }
109 if (exp == 1) {
110 return n;
111 } else if (exp == 2) {
112 return n * 2;
113 } else {
114 /*
115 直接提取base的最高53位为h(无条件进位,base < h*2^sh,
116 sh为被舍弃的低位位数),mant = h*2^-52 in (1,2],
117 E = bits(base)-1 = sh+52 为log2的整数部分。
118 base^exp 的位数为 exp*log2(mant) + exp*E:
119 整数部分 exp*E 走整数运算;log2 仅作用于 (1,2] 区间,
120 完整保留53位有效数字;exp 提取高53位并向上舍入为double。
121 */
122 int t = lmmp_limb_bits_(base[n - 1]);
123 uint64_t h;
124 if (t >= 53) {
125 h = (base[n - 1] >> (t - 53)) + 1;
126 } else {
127 // n >= 2 必然成立(单limb已在前面处理)
128 h = ((base[n - 1] << (53 - t)) | (base[n - 2] >> (LIMB_BITS - 53 + t))) + 1;
129 }
130 mp_bitcnt_t e_int = (n - 1) * LIMB_BITS + t - 1;
131
132 double expd = ulong_upper_d(exp);
133 mp_size_t rn = floor1_u64(expd * log2(ldexp((double)h, -52)));
134 if (rn == MP_SIZE_MAX) {
135 return rn;
136 }
137 mp_size_t l = floor1_u64(expd * (double)e_int);
138 if (l == MP_SIZE_MAX) {
139 return l;
140 }
141 rn += l;
142 rn = (rn + LIMB_BITS - 1) / LIMB_BITS;
143 return rn + 2;
144 }
145}
146
148 lmmp_param_assert(n > 0);
149 lmmp_param_assert(exp > 0);
150 lmmp_param_assert(base[n - 1] != 0);
151 if (exp == 1) {
152 lmmp_copy(dst, base, n);
153 return n;
154 } else if (exp == 2) {
155 lmmp_sqr_(dst, base, n);
156 rn = n << 1;
157 rn -= (dst[rn - 1] == 0);
158 return rn;
159 } else {
160 mp_size_t base_tz = 0;
161 while (*base == 0) {
162 ++base_tz;
163 ++base;
164 --n;
165 }
166 base_tz *= exp;
167 lmmp_zero(dst, base_tz);
168 dst += base_tz;
169 if (n == 1) {
170 if (exp <= POW_1_EXP_THRESHOLD) {
171 dst[0] = base[0];
172 rn = 1;
173 for (ulong i = 1; i < exp; ++i) {
174 dst[rn] = lmmp_mul_1_(dst, dst, rn, base[0]);
175 ++rn;
176 rn -= (dst[rn - 1] == 0);
177 }
178 return rn + base_tz;
179 } else {
180 return lmmp_pow_1_(dst, rn, base[0], exp) + base_tz;
181 }
182 } else { /* n > 2 */
184 if ((exp % 4 == 3) || (2 * lmmp_limb_popcnt_(exp) >= (lmmp_limb_bits_(exp)))) {
185 return lmmp_pow_win2_(dst, rn, base, n, exp) + base_tz;
186 }
187 }
188 if (exp & 1) {
189 return lmmp_pow_basecase_(dst, rn, base, n, exp) + base_tz;
190 }
191
192 int tz = lmmp_tailing_zeros_(exp);
193 TEMP_DECL;
194 mp_ptr restrict sq = TALLOC_TYPE((rn + 2) >> 1, mp_limb_t);
195 exp >>= tz;
196
197 if (tz & 1) {
198 if (exp == 1) {
199 lmmp_copy(sq, base, n);
200 rn = n;
201 } else {
202 mp_size_t rn1 = lmmp_pow_size_(base, n, exp);
203 rn = lmmp_pow_basecase_(sq, rn1, base, n, exp);
204 }
205 int i = 2;
206 for (; i <= tz; i += 2) {
207 lmmp_sqr_(dst, sq, rn);
208 rn <<= 1;
209 rn -= (dst[rn - 1] == 0);
210 lmmp_sqr_(sq, dst, rn);
211 rn <<= 1;
212 rn -= (sq[rn - 1] == 0);
213 }
214 lmmp_sqr_(dst, sq, rn);
215 rn <<= 1;
216 rn -= (dst[rn - 1] == 0);
217 } else {
218 if (exp == 1) {
219 lmmp_copy(dst, base, n);
220 rn = n;
221 } else {
222 mp_size_t rn1 = lmmp_pow_size_(base, n, exp);
223 rn = lmmp_pow_basecase_(dst, rn1, base, n, exp);
224 }
225 int i = 2;
226 for (; i <= tz; i += 2) {
227 lmmp_sqr_(sq, dst, rn);
228 rn <<= 1;
229 rn -= (sq[rn - 1] == 0);
230 lmmp_sqr_(dst, sq, rn);
231 rn <<= 1;
232 rn -= (dst[rn - 1] == 0);
233 }
234 }
235 TEMP_FREE;
236 return rn + base_tz;
237 }
238 }
239}
#define lmmp_limb_bits_
#define lmmp_sqr_
#define lmmp_limb_popcnt_
#define lmmp_tailing_zeros_
#define MP_SIZE_MAX
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
#define t
#define n
#define POW_WIN2_EXP_THRESHOLD
#define POW_1_EXP_THRESHOLD
#define POW_WIN2_N_THRESHOLD
mp_size_t lmmp_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
定义 pow.c:65
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
mp_size_t lmmp_pow_1_(mp_ptr dst, mp_size_t rn, mp_limb_t base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
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
mp_size_t lmmp_pow_(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
mp_size_t lmmp_pow_size_(mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
定义 pow.c:103
static mp_size_t floor1_u64(double r)
计算floor(r)+1并转为mp_size_t
定义 pow.c:58
static double ulong_upper_d(ulong x)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 pow.c:40
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)