我找不到合适的算法/结构来简单地在 C 或 Go 中计算数字。但是,可以很容易地在 Python 中创建一个类。
乍一看,计算似乎非常简单。但是,当您查看 Wolfram Alpha 的示例计算时。
https://www.wolframalpha.com/input/?i=3%5E3%5E3%5E3
这打破了long long
(整数,18-19 位数字)和double
( float /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 位,所以一切都很容易计算,重复平方是求幂的主要捷径。
关于algorithm - 计算 3^3^3^3(非常大的指数/Wolfram 是怎么做到的?),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68797298/