Calculating 3^3^3^3 (very large exponent / how did Wolfram do it?)

Question

I can't find a right algorithm / struct to calculate the number simply in C or Go. However, a class can easily be created in Python.

At first glance, the calculation seems to be very straight forward. However, when you look at the sample calculation from Wolfram Alpha.

https://www.wolframalpha.com/input/?i=3%5E3%5E3%5E3

This breaks both long long (integer, 18-19 digits) and double (float / IEEE 754, up to e+308 digits, with 17 digits' precision).

However, I can cheat a little with Python, as it will automatically allocate more bytes for integer.

Still, 3^(7.625e+13) takes abnormally very long time... (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 is giving you an approximate answer, which is much easier than calculating an exact answer. Most likely it's using the transform log(a^b) = b * log(a) to calculate log(3^3^3^3) = (3^3^3) log(3) = 7625597484987 * log(3), which works out to about 3638334640024.09968557 if you take logs base 10. You'll notice that the integer part of that gives you the number of digits, and if you take 10^0.09968557, you end up with 1.2580143 or so. Wolfram worked it out to a few more digits than I did, but this is pretty basic stuff with logarithms and not as expensive as computing 3^3^3^3 in integer arithmetic.

They also give the "last few digits" as 6100739387, but that's easily done using modular exponentiation: a recent version of Python will instantly return the same value for pow(3, 3**3**3, 10_000_000_000). Even though the power is rather large, the numbers being multiplied never get more than 10 digits long, so everything is easy to work out, and repeated squaring provides a major shortcut for the exponentiation.