algorithm - 计算 3^3^3^3(非常大的指数/Wolfram 是怎么做到的？)

Question

我找不到合适的算法/结构来简单地在 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))

Answer 1

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 位，所以一切都很容易计算，重复平方是求幂的主要捷径。