LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
28static 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
36static 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)).*/
47static 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
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}
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LIMB_BITS
定义 lmmp.h:102
#define n
static const float inv_table[]
static ulong pow_n(ulong x, ulong n)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static const uint16_t max_base[]
ulong lmmp_cbrt_ulong_(ulong n)
计算算数立方根 floor(cbrt(n))
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
uint64_t ulong
定义 numth.h:39