## DEV Community is a community of 733,030 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Pacharapol Withayasakpunt

Posted on

# 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}.{s[1:4]}e+{Int(len(s))})"

return s
``````

## Discussion (3) 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

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

```

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

```

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 • 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 :( Pacharapol Withayasakpunt • Edited

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

`````` % 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.