DEV Community

Pacharapol Withayasakpunt
Pacharapol Withayasakpunt

Posted on

2

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
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (3)

Collapse
 
patarapolw profile image
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)
Enter fullscreen mode Exit fullscreen mode
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))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
flyingcakes profile image
Snehit Sah • • Edited

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 :(

Collapse
 
patarapolw profile image
Pacharapol Withayasakpunt • • Edited

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

I stopped at

(3.2485963e+6846169)^3 == (3.4283664e+20538506)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

BTW, the expected result is

12577936...00739387 (1.2577936e+3638334640024)
Enter fullscreen mode Exit fullscreen mode

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

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

đź‘‹ Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay