How do you calculate 3^3^3^3? (What algo / struct?)

At first glance, it 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).

class Int:
    MAX_LEN = 10

    def __init__(self, val: int) -> None:
        if isinstance(val, Int):
            self.val = val.val
        else:
            self.val = 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:
        s = str(self.val)

        if len(s) > self.MAX_LEN:
            h = int(self.MAX_LEN / 2)
            return f"{s[:h]}...{s[-h:]} ({s[0]}.{s[1:4]}e+{Int(len(s))})"

        return s

Comments

[Pacharapol Withayasakpunt]

I made it, but I could get the first digits right (according to WolframAlpha).

12577936...00739387 (1.2577936e+3638334640024)
# Wolfram - 12580142...00739387 (3638334640025 digits)

import math


class BigInt:
    """BigInt gives integer approximation and easy to read strings"""

    _first = ""
    _last = ""
    _length = None  # BigInt

    val: int = None  # actual int, if applicable

    def __init__(self, val: int = 0) -> None:
        """BigInt gives integer approximation and easy to read strings

        Args:
            val (int | BigInt, optional): Defaults to 0.
        """

        self.set(val)

    def set(self, val: int):
        """Update large integer with int or BigInt

        Args:
            val (int | BigInt): integer to update

        Returns:
            BigInt: returns self
        """
        if isinstance(val, BigInt):
            self.val = val.val

            if val.val is None:
                self._first = val._first
                self._last = val._last
                self._length = val._length
                return
        else:
            self.val = val

        try:
            float(self.val)
        except OverflowError:
            self._first = self.first
            self._last = self.last
            self._length = None
            self.val = None

        return self

    @property
    def first(self) -> str:
        """

        Returns:
            str: initial part of BigInt
        """

        if self._first:
            return self._first

        if not self.val:
            return ""

        return str(self.val)[:8]

    @property
    def last(self) -> str:
        """

        Returns:
            str: ending part of BigInt.
        """

        if self._last:
            return self._last

        if not self.val:
            return ""

        return str(self.val)[-8:]

    @property
    def length(self):
        """

        Returns:
            BigInt | None: length of BigInt, as another BigInt, if applicable
        """

        if self._length:
            return self._length

        if not self.val:
            return None

        return BigInt(len(str(self.val)))

    def __repr__(self) -> str:
        if not self.val or self.val > 10 ** 16:
            s = ""
            if self.last:
                s = f"{self.first}...{self.last}"

            e = ""
            if self.length:
                m = ""
                if self.first:
                    m = self.first[0]

                    if len(self.first) > 1:
                        m += "." + self.first[1:]

                e = f"{m}e+{self.length}"

            if s:
                if e:
                    return f"{s} ({e})"
                return s
            return e

        return f"{self.val}"


class Tower(BigInt):
    """Exponent tower, of 3 by default"""

    k: int
    base: int

    def __init__(self, k: int, base: int = 3) -> None:
        """Exponent tower, of 3 by default

        Args:
            k (int): Number of bases in the tower
            base (int, optional): Defaults to 3.
        """

        self.k = k
        self.base = base

        super().__init__(base)

        prev = BigInt(1)

        def up_pow(m: int) -> None:
            out = BigInt()

            if self.val:
                try:
                    float(base) ** self.val
                    self.set(base ** self.val)
                    return
                except OverflowError:
                    pass

                log = self.val * math.log10(base)
                fl = math.floor(log)

                r = log - fl

                out._first = f"{(10 ** r):.7f}".replace(".", "") if r > 0 else ""
                out._length = BigInt(fl)
            elif prev.val:
                loglog = prev.val * math.log10(base) + math.log10(math.log10(base))
                fl = math.floor(loglog)

                r = loglog - fl

                length = BigInt()
                length._first = f"{(10 ** r):.7f}".replace(".", "") if r > 0 else ""
                length._length = BigInt(fl)

                out._length = length

            out._last = tetmod_digits(int(BigInt(base).last), m)
            out.val = None

            self.set(out)

        for m in range(2, k + 1):
            next_prev = BigInt(self)
            up_pow(m)
            prev = next_prev


def modpow(base: int, exp: int, mod: int) -> int:
    """Modular exponentiation

    Adapted from https://en.wikipedia.org/wiki/Modular_exponentiation#Implementation_in_Lua

    ```

py
    (base ** exp) % mod


    ```

    Args:
        base (int):
        exp (int):
        mod (int):

    Returns:
        int:
    """

    r = 1
    base = base % mod
    while exp:
        if exp % 2:
            r = (r * base) % mod

        exp = exp // 2
        base = (base ** 2) % mod

    return r


def modpow_digits(base: int, exp: int, digits: int = 8) -> str:
    """Last digits of exponentiation

    ```

py
    (base ** exp) % (10 ** digits)  # With frontmost "0" padding


    ```

    Args:
        base (int):
        exp (int):
        digits (int, optional): Defaults to 8.

    Returns:
        str: string of digits, representing n last digits
    """

    mod = 10 ** digits
    return str(modpow(base, exp, mod)).rjust(digits, "0")


def tetmod(base: int, k: int, mod: int) -> int:
    """Tetration with modulo

    Adapted from https://math.stackexchange.com/a/4225702/958918

    ```

py
    (base ↑↑↑ k) % mod


    ```

    Args:
        base (int):
        k (int):
        mod (int):

    Returns:
        int:
    """

    if k == 1:
        return base % mod
    elif k == 2:
        return modpow(base, base, mod)

    phi = euler_phi(mod)
    return modpow(base, phi + tetmod(base, k - 1, phi) % phi, mod)


def tetmod_digits(base: int, k: int, digits: int = 8) -> str:
    """Last digits of tetration

    ```

py
    (base ↑↑↑ k) % (10 ** digits)  # With frontmost "0" padding


    ```

    Args:
        base (int):
        k (int):
        digits (int, optional): Defaults to 8.

    Returns:
        str: string of digits, representing n last digits
    """

    mod = 10 ** digits
    return str(tetmod(base, k, mod)).rjust(digits, "0")


def euler_phi(n: int) -> int:
    """Euler's Phi

    From https://www.geeksforgeeks.org/eulers-totient-function/

    Args:
        n (int):

    Returns:
        int: the count (number) of coprimes less than n
    """

    # Initialize result as n
    result = n

    # Consider all prime factors
    # of n and subtract their
    # multiples from result
    p = 2
    while p * p <= n:

        # Check if p is a
        # prime factor.
        if n % p == 0:

            # If yes, then
            # update n and result
            while n % p == 0:
                n = int(n / p)
            result -= int(result / p)
        p += 1

    # If n has a prime factor
    # greater than sqrt(n)
    # (There can be at-most
    # one such prime factor)
    if n > 1:
        result -= int(result / n)
    return result


if __name__ == "__main__":
    for n in range(2, 6 + 1):
        print("-", n, Tower(n))

[Snehit Sah]

You could see this StackOverflow answer : math.stackexchange.com/a/176257

That being said, I suppose that 3^3^3^3 will use about 3639GB memory to store. (if I've got my maths right)

Edit: I certainly got my mathematics wrong I suppose :(

[Pacharapol Withayasakpunt]

I tried, but not to the end, with exponentiation by squaring.

I stopped at

(3.2485963e+6846169)^3 == (3.4283664e+20538506)

And I cached the file storing 6846170 + 20538507 digits, and it takes 27 MB

[0] % du -sh cache/k_cubed/* | sort -h | tail -n 1
27M     cache/k_cubed/32485...48187 (3.248e+6846169)

BTW, the expected result is

12577936...00739387 (1.2577936e+3638334640024)

I may get some of the first digits wrong, though.