Computing 3âââ3 (In Python)
<p>I'm giving a presentation on <a href="https://en.wikipedia.org/wiki/Graham%27s_number" rel="nofollow">Graham's Number</a> and I wanted to compute the first few âs (i.e. 3â3, 3ââ3, and 3âââ3) to give them an idea of how huge it gets in such a short time. I wrote some naive/direct code in python, based on the definitions of arrow notation, shown below:</p>

<pre><code>def arrow2(a,b):
    c=1
    for i in np.arange(b):
        c=a**c
    return c

def arrow3(a,b):
    c=1
    for i in np.arange(b):
        c=arrow2(a,c)
    return c
</code></pre>

<p>Although "long" integers (limitless) and numpy arrays (limitless) were used, naturally the code takes up far too much memory while running and will take a very long time to process. Is there a solution to this? (or does someone already know the answer?) Thank you!</p>

<p>Expanding on my comment, I just want to flesh out a bit just <em>how</em> hopeless it is to grasp numbers of this size.</p>

<p>I assume you already know that</p>

<pre><code>3 âââ 3 =
3 ââ (3 âââ 2) =
3 ââ (3 ââ 3) =
3 ââ (3 â 3 â 3) =
3 ââ (3 â 27) =
3 ââ 7625597484987
</code></pre>

<p>So this reduces to studying the growth of <code>3 ââ i</code>.  Let's see how that grows:</p>

<pre><code>3 ââ 0 = 1
3 ââ 1 = 3**(3ââ0) = 3**1 = 3
3 ââ 2 = 3**(3ââ1) = 3**3 = 27
3 ââ 3 = 3**(3ââ2) = 3**27 = 7625597484987
3 ââ 4 = 3**(3ââ3) = 3**7625597484987 = ...?
</code></pre>

<p>We're already beyond the limit of what's feasible to compute on most personal computers.  </p>

<pre><code>&gt;&gt;&gt; import math
&gt;&gt;&gt; math.log10(3) * 3**27
3638334640024.0996
</code></pre>

<p>That's the base 10 logarithm of <code>3 ââ 4</code>, showing that the latter has over 3 trillion (decimal) digits.  Even with a custom encoding using 4 bits per decimal digit, it would require over 1.5 terabytes of disk space to store it - and very few computers have enough RAM to compute it in a straightforward way.</p>

<p>Then <code>3 ââ 5</code> is in turn 3 raised to that multi-trillion digit power.  The words and notations we normally use are <em>already</em> inadequate to give any real idea of just how large that is, and there is no computer with enough RAM or disk space to deal with it.</p>

<p>And we're only up to <code>3 ââ 5</code>!  There are still <em>trillions</em> of layers to go to reach <code>3 ââ 7625597484987</code> = <code>3âââ3</code>.  It's beyond human comprehension.  Although, yes, infinitely many integers are even larger ;-)</p>

python memory bigdata