我找不到一个正确的算法/结构来简单地在C或Go中计算数字。但是，在Python中可以很容易地创建一个类。
乍一看，计算似乎很简单。但是，当您查看Wolfram Alpha的示例计算时。
https://www.wolframalpha.com/input/?i=3%5E3%5E3%5E3
这将long long(整数，18-19位)和double(浮点数/IEEE 754，最多e+308位，精度为17位)拆分。
然而，我可以在Python中欺骗一点，因为它会自动为整数分配更多的字节。
尽管如此，3^(7.625e+13)需要非常长的时间…(3^3^3 = 7.625e+13).
import math
from decimal import Decimal
class Int:
_first = ""
_last = ""
_length = None # Int
val: int = None # actual int, if applicable
def __init__(self, val: int = 0) -> None:
if isinstance(val, Int):
if val.val is None:
self._first = val._first
self._last = val._last
self._length = val._length
return
self.val = val.val
else:
self.val = val
try:
float(self.val)
except OverflowError:
self._first = self.first
self._last = self.last
self._length = self.length
self.val = None
@property
def first(self) -> str:
if self._first:
return self._first
return str(self.val)[:8]
@property
def last(self) -> str:
if self._last:
return self._last
return str(self.val)[-8:]
@property
def length(self):
if self._length:
return self._length
return Int(len(str(self.val)))
def exp3(self):
return Int(3) ** self.val
def tetrate3(self, n: int):
first = Int(self)
for _ in range(n - 1):
first = first.exp3()
return first
def __repr__(self) -> str:
if self.val is None:
return f"{self.first}...{self.last} ({self.first[0]}.{self.first[1:]}e+{self.length})"
return f"{self.val}"
def __pow__(self, _other):
base = Int(self)
exp = Int(_other)
if base.val and exp.val:
try:
float(base.val) ** exp.val
return Int(base.val ** exp.val)
except OverflowError:
pass
log = Decimal(exp.val) * Decimal(math.log10(base.val))
fl = math.floor(float(log))
out = Int()
out._first = f"{(10 ** float(log - fl)):.7f}".replace(".", "")
out._last = str(pow(int(base.last), exp.val, 10_000_000_000))[-8:]
out._length = Int(fl)
out.val = None
return out
if __name__ == "__main__":
# After the third digits may be imprecise
# => 12579723...00739387 (1.2579723e+3638334640024)
print(Int(3).tetrate3(4))
Wolfram Alpha会给你一个近似的答案，这比计算一个确切的答案要容易得多。最有可能的是使用变换log(a^b) = b * log(a)来计算log(3^3^3^3) = (3^3^3) log(3) = 7625597484987 * log(3)，如果取以10为底的对数，结果大约是3638334640024.09968557。你会注意到其中的整数部分给出了位数，如果你取10^0.09968557，你最终会得到1.2580143左右。Wolfram算出来的数字比我多几个，但这是非常基本的东西，有对数和，而不是，像在整数算术中计算3^3^3^3那样昂贵。
还会给出"最后几位数";作为6100739387，但这很容易使用模块化幂运算来完成:Python的最新版本将立即为pow(3, 3**3**3, 10_000_000_000)返回相同的值。尽管幂相当大，但相乘的数字不会超过10位，所以一切都很容易计算，重复平方为求幂提供了一个主要的捷径。
这分隔了long long(整数，18-19位)和double
c++编译器还提供了一个128位类型__int128_t取值范围为−2^127…2^127−1(约−10^38…10 ^ 38)
3^(7.625e+13)耗时异常长
，因为你只是这样计算pow:return Int(base.val ** exp.val)猜一下，需要O(N)
你可以用快速赋能算法(或二进制幂运算)来优化它
def bin_pow( a, n ):
"""
calculates a ^ n
complexity O(log n)
a -> integer
b -> integer
ans -> integer
"""
ans = 1
while n:
if( n % 2 != 0 ):
ans *= a
a*=a
n /= 2
return ans
或https://github.com/ampl/gsl是C/c++
的另一种选择WolframAlpha显示前几位数字和位数:
1.25801429062749131786039069820328121551804671431659……×10 ^ 3638334640024
我们自己可以在不到一毫秒的时间内完成，只保留前50位。每次都取整一次，这样就得到了实数的下界。再做一次，我们把一直向上取整，这样我们就得到了实际值的上界。下界和上界匹配的数字是正确的:
lower bound: 1.2580142906274913178603906982032812155096427774056 × 10^3638334640024
correct: 1.2580142906274913178603906982032812155... × 10^3638334640024
upper bound: 1.2580142906274913178603906982032812155218895229290 × 10^3638334640024
0.0003557720046956092 seconds
如果您想要更多的正确数字，只需保留更多的数字，并且下界和上界将匹配更多的数字。例如keep = 100:
lower bound: 1.258014290627491317860390698203281215518046714316596015189674944381211011300017785310803884345530895 × 10^3638334640024
correct: 1.258014290627491317860390698203281215518046714316596015189674944381211011300017785310803... × 10^3638334640024
upper bound: 1.258014290627491317860390698203281215518046714316596015189674944381211011300017785310803933426563879 × 10^3638334640024
0.0004895620222669095 seconds
我的代码(在线试试!)将一个数字表示为两个整数mantissa和exponent，代表数字mantissa × 10^exponent。每当mantissa增长得太大(超过keep的位数)，它就从mantissa中删除位数，并相应地增加exponent的位数:
def power(b, e):
'''Compute b to the power of e.'''
result = Int(1)
while e:
if e % 2:
result *= b
b *= b
e //= 2
return result
class Int:
def __init__(self, mantissa, exponent=0):
n = len(str(mantissa))
if n > keep:
remove = n - keep
if round == 'down':
mantissa //= 10**remove
else:
mantissa = -(-mantissa // 10**remove)
exponent += remove
self.mantissa = mantissa
self.exponent = exponent
def __mul__(self, other):
return Int(self.mantissa * other.mantissa,
self.exponent + other.exponent)
def __str__(self):
m = str(self.mantissa)
e = self.exponent
if len(m) > 1:
e += len(m) - 1
m = m[0] + '.' + m[1:]
return f'{m} × 10^{e}'
from os.path import commonprefix
from timeit import default_timer as timer
t0 = timer()
keep = 50
round = 'down'
lower = str(power(Int(3), 3**3**3))
round = 'up'
upper = str(power(Int(3), 3**3**3))
m, e = lower.split(' × ')
M, E = upper.split(' × ')
assert e == E
m = commonprefix([m, M])
print('lower bound:', lower)
print('correct: ', m + '...', '×', e)
print('upper bound:', upper)
print(timer() - t0, 'seconds')