LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
nthroot_ulong.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 "
lmmp/numth.h
"
26
27
28
static
inline
ulong
pow_n
(
ulong
x,
ulong
n
) {
29
ulong
ret = 1;
30
for
(
ulong
i = 0; i <
n
; ++i) {
31
ret *= x;
32
}
33
return
ret;
34
}
35
36
static
const
float
inv_table
[] = {
37
0.200000000000000, 0.166666666666667, 0.142857142857143, 0.125000000000000, 0.111111111111111, 0.100000000000000,
38
0.090909090909091, 0.083333333333333, 0.076923076923077, 0.071428571428571, 0.066666666666667, 0.062500000000000,
39
0.058823529411765, 0.055555555555556, 0.052631578947368, 0.050000000000000, 0.047619047619048, 0.045454545454545,
40
0.043478260869565, 0.041666666666667, 0.040000000000000, 0.038461538461538, 0.037037037037037, 0.035714285714286,
41
0.034482758620690, 0.033333333333333, 0.032258064516129, 0.031250000000000, 0.030303030303030, 0.029411764705882,
42
0.028571428571429, 0.027777777777778, 0.027027027027027, 0.026315789473684, 0.025641025641026, 0.025000000000000,
43
};
44
45
/* This table has the max possible base for a given root. For n >= 4,
46
max_base[n-4] = floor(UWORD_MAX^(1/n)).*/
47
static
const
uint16_t
max_base
[] = {
48
65535, 7131, 1625, 565, 255, 138, 84, 56, 40, 30, 23, 19, 15, 13, 11, 10, 9, 8, 7, 6, 6, 5, 5, 5, 4, 4, 4, 4, 3, 3,
49
3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2};
50
51
ulong
lmmp_nthroot_ulong_
(
ulong
n
,
ulong
root) {
52
ulong
x, currval, base, upper_limit;
53
54
if
(
n
== 0 || root == 0)
55
return
0;
56
if
(root == 1)
57
return
n
;
58
if
(root == 2)
59
return
lmmp_sqrt_ulong_
(
n
);
60
if
(root == 3)
61
return
lmmp_cbrt_ulong_
(
n
);
62
63
if
(root >=
LIMB_BITS
||
n
< (1ULL << root))
64
return
1;
65
66
/* n <= upper_limit^root */
67
upper_limit =
max_base
[root - 4];
68
69
if
(upper_limit == 2)
70
return
upper_limit;
71
72
/* upper_limit = 2 for root >= 41 */
73
lmmp_debug_assert
(root <= 40);
74
75
if
(root == 4)
76
x = sqrt(sqrt(
n
));
77
else
78
x = expf(
inv_table
[root - 5] * logf(
n
));
79
80
base = x;
81
82
if
(base >= upper_limit)
83
base = upper_limit - 1;
84
85
currval =
pow_n
(base, root);
86
if
(currval ==
n
)
87
return
base;
88
89
while
(currval <=
n
) {
90
base++;
91
currval =
pow_n
(base, root);
92
if
(base == upper_limit)
93
break
;
94
}
95
96
while
(currval >
n
) {
97
base--;
98
currval =
pow_n
(base, root);
99
}
100
101
return
base;
102
}
lmmp_debug_assert
#define lmmp_debug_assert(x)
定义
lmmp.h:498
LIMB_BITS
#define LIMB_BITS
定义
lmmp.h:102
n
#define n
inv_table
static const float inv_table[]
定义
nthroot_ulong.c:36
pow_n
static ulong pow_n(ulong x, ulong n)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
nthroot_ulong.c:28
max_base
static const uint16_t max_base[]
定义
nthroot_ulong.c:47
numth.h
lmmp_cbrt_ulong_
ulong lmmp_cbrt_ulong_(ulong n)
计算算数立方根 floor(cbrt(n))
定义
cbrt_ulong.c:139
lmmp_sqrt_ulong_
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
定义
sqrt_1.c:31
lmmp_nthroot_ulong_
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
定义
nthroot_ulong.c:51
ulong
uint64_t ulong
定义
numth.h:39
src
lmmp
numth
nthroot_ulong.c
生成于
, 为 LMMP使用
1.18.0