LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
pow.c 文件参考
#include <math.h>
#include "impl/inlines.h"
#include "mparam.h"
#include "impl/tmp_alloc.h"
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
pow.c 的引用(Include)关系图:

浏览该文件的源代码.

函数

static mp_size_t floor1_u64 (double r)
 计算floor(r)+1并转为mp_size_t
mp_size_t lmmp_pow_ (mp_ptr restrict dst, mp_size_t rn, mp_srcptr restrict base, mp_size_t n, ulong exp)
mp_size_t lmmp_pow_1_size_ (mp_limb_t base, ulong exp)
 计算幂次方需要的limb缓冲区长度 base ^ exp
mp_size_t lmmp_pow_size_ (mp_srcptr base, mp_size_t n, ulong exp)
 计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
static double ulong_upper_d (ulong x)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ floor1_u64()

mp_size_t floor1_u64 ( double r)
inlinestatic

计算floor(r)+1并转为mp_size_t

参数
r位数估计值(非负)
返回
floor(r)+1,即以bit计的长度;超出64bit范围时钳制为最大值
注解
位数 = floor(log2(x))+1。当估计值恰为整数(如底数是2的幂)时, ceil会少计1bit,故统一使用floor+1

在文件 pow.c 第 58 行定义.

58 {
59 if (r >= 0x1p63) {
60 return MP_SIZE_MAX;
61 }
62 return (mp_size_t)floor(r) + 1;
63}
#define MP_SIZE_MAX
uint64_t mp_size_t
定义 lmmp.h:93

引用了 floor1_u64() , 以及 MP_SIZE_MAX.

被这些函数引用 floor1_u64(), lmmp_pow_1_size_() , 以及 lmmp_pow_size_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_pow_()

mp_size_t lmmp_pow_ ( mp_ptr restrict dst,
mp_size_t rn,
mp_srcptr restrict base,
mp_size_t n,
ulong exp )

在文件 pow.c 第 147 行定义.

147 {
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_
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
uint64_t mp_limb_t
定义 lmmp.h:92
#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 n
#define POW_WIN2_EXP_THRESHOLD
#define POW_1_EXP_THRESHOLD
#define POW_WIN2_N_THRESHOLD
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
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
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 lmmp_copy, lmmp_limb_bits_, lmmp_limb_popcnt_, lmmp_mul_1_(), lmmp_param_assert, lmmp_pow_(), lmmp_pow_1_(), lmmp_pow_basecase_(), lmmp_pow_size_(), lmmp_pow_win2_(), lmmp_sqr_, lmmp_tailing_zeros_, lmmp_zero, n, POW_1_EXP_THRESHOLD, POW_WIN2_EXP_THRESHOLD, POW_WIN2_N_THRESHOLD, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ lmmp_pow_1_size_()

mp_size_t lmmp_pow_1_size_ ( mp_limb_t base,
ulong exp )

计算幂次方需要的limb缓冲区长度 base ^ exp

参数
base底数
exp指数
警告
exp>0, base>=1
返回
返回值为 base^exp 需要的 limb 缓冲区长度(比实际长度多)

在文件 pow.c 第 65 行定义.

65 {
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}
#define LIMB_BITS
定义 lmmp.h:102
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

引用了 floor1_u64(), LIMB_BITS, lmmp_limb_bits_, lmmp_param_assert, lmmp_pow_1_size_(), MP_SIZE_MAX , 以及 ulong_upper_d().

被这些函数引用 check_pow1_agree(), check_pow1_laws(), lmmp_nCr_size_(), lmmp_nPr_size_(), lmmp_pow_1_size_(), lmmp_pow_size_(), lmmp_powmod_() , 以及 pow_nPr_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_pow_size_()

mp_size_t lmmp_pow_size_ ( mp_srcptr base,
mp_size_t n,
ulong exp )

计算幂次方需要的limb缓冲区长度 [base,n] ^ exp

参数
base底数指针
n底数 limb 长度
exp指数
警告
n>0, base[n-1]!=0, [base,n]>1
返回
返回值为 [base,n]^exp 需要的 limb 缓冲区长度(比实际长度多)

在文件 pow.c 第 103 行定义.

103 {
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}
size_t mp_bitcnt_t
定义 lmmp.h:98
#define t
mp_size_t lmmp_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
定义 pow.c:65

引用了 floor1_u64(), LIMB_BITS, lmmp_limb_bits_, lmmp_param_assert, lmmp_pow_1_size_(), lmmp_pow_size_(), MP_SIZE_MAX, n, t , 以及 ulong_upper_d().

被这些函数引用 lmmp_pow_(), lmmp_pow_size_(), lmmp_powmod_(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ ulong_upper_d()

double ulong_upper_d ( ulong x)
inlinestatic

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

将x转换为不小于x的double(提取高53位)

参数
x输入
返回
double值d,满足 d >= x 且 d/x <= 1 + 2^-52
注解
仅当x超出53位有效数字时,舍弃低位并对高位进位。 pow的位数估计中,exp可达2^64,超出双精度有效数字, 提取高位既保留全部有效数字,又保证转换不会引入低估。

在文件 pow.c 第 40 行定义.

40 {
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}

引用了 lmmp_limb_bits_ , 以及 ulong_upper_d().

被这些函数引用 lmmp_pow_1_size_(), lmmp_pow_size_() , 以及 ulong_upper_d().

函数调用图:
这是这个函数的调用关系图: