“On the shoulders of giant numbers”
http://www.allergrootste.com/big/book/ch2/ch2_1.html
bigΨ
Ψ.2. Up to the Ackermann numbers
chapter 2.1, edit 0.2.9
published: 2011-01-07
updated: 2011-12-30
# 2.1. Super-calculation
The great teacher said,
"The supreme ineffable Way of all enlightened ones
involves ages of effort, carrying out what is difficult to carry out,
enduring what is difficult to endure.
How can you hope for true religion with little virtue,
little wisdom, a shallow heart, and an arrogant mind?
It would just be a waste of effort."
– Bodhidharma to Hui K'o
Transmission of Light
§2.1.1. Backslashing
To compare the size of two very large numbers we can often only aim for an approximation,
specially when we have to deal with expressions of different algorithms
(different sets of rules).
An unknown algorithm would be explored starting with
superpowers
(our stars or Knuth's arrows) as a benchmark for
example.
Step by step the value of the unknown expression is build up
and translated into the familiar benchmark format.
This chapter explains backslashed operations.
With backslash notation we write compound expressions more easily,
keep pace with the reduction train of new algorithms and express
Big numbers
with just the right precision.
The main rule in an algorithm typically replaces an operation
a×..b1
{×#c1}
by a series of lower operations, either in one sweep
a×....
{×#c a#b1}
or by iterating over a substitution step
a×..(a×..b)
{×#c ×#c1}
where the number of iterations b
equals the number of lower operators
×..
{×#c}
in the resulting
series.
Each term in this series of host operation H
can be addressed with
an index k
starting at index k=1 (this may be omitted).
Then a guest operation G
is invited
by backslashing H\k'G
which applies G
to the (subscripted) k
th term alone,
or by H\k"G
to apply G
to that part of the series starting at the (superscripted)
k
th
index.
We always count terms from the top H\
(the right) of the series where the value has most impact,
because iterators b
are nested from right to left
(if substituted as above).
On other occassions (nesting from the left)
you may like to address terms from the bottom up
G×\H
but only if there's no risk of mistaking the
guest for the host.
We dare use the prefix backslash only when G
adds a number or variable.
The backslash is resolved when the host iterator is counted down
and the guest joined in with a subexpression
at the invited position, as follows…
a^^3
\**b
=
a^^3\1'^b =
a^^3\1"^b =
a^a^a^b a^^4\2"*b = a^a^(a^a
*b
)a^^5\3'*b = a^a^(
a*b
)^a^a
a***3\1'*3\2'2\3'b = ab**a2**a*3
a***3\*3\*b = a***3\(*3\*b) = a**a**aa(a*b)
= a**a**a*b2 = a***3\*b2
a^^3\2"(***2\b) = a^(a^a)^(a^a+b)
3^^2\\2'^a = 3^3\2'**a = 3*(3**a)*3
A party of all kinds of backslashed guests is less practical,
but can be
fun!
Note that star operations *..
are ruled by minority
and arrows ^..
by majority
precedence.
But the original backslashed operations stay unresolved,
until the host has shed a star
and it's time for a backslashed operation to step in,
then it's granted the highest priority.
A few more instructive examples –
backslashes are particularly useful when iterations can get long.
p****1111\***111\**11 = p***p***p***p**p**p*p
5^^n\(^2+2)×2\n'^2 = 25^5^...^54 {5#n--}
a***b2\b'1 = a**a**a1**a... {**a#b}
2^^^3\\2"^5 = 2^^4\2"^5 = 2^2^(2^2)^5
; = 2^2^4^5 = 2^2^1024 = 2^^3\^10
With a^^b1\2'1
< a^^b1\1 < a1^^b1
we put our new backslash notation to good use.
The next subchapter zooms in on tetration and
shows
some advanced uses of backslashing.
§2.1.2. Pushing beyond powers
We start with superpowers and calculate a few
pentation squares
m****2
= m^^m
and find a rule to approximate tetration.
We use brown here to highlight the real exponent,
corresponding to an approximation rule with an integer coefficient.
After <~
comes
the larger and significantly better approximation,
closer to m^^n
at the end.
5^^5 = 5^5^5^5^5 ~ (5^4.12)^^4 ~ (5^3120.)^^3
m^^n ~> (m^(m-1))^^n-
<~ (m^(m^m - m))^^n--
<~ (m^(m^^d - m^^(d-1)))^^(n-d) {0<d<n-}
We'll compare expressions of the form (a*..b)*..c
with those of the form a*..bd
and with those beyond.
If you just want to get the big picture you can skip the original
details!
-
(a*b)*2 = a*bb
extends to:
(a*b)*b = a*b^2 generally:
(.a.)*b.. {#n#} = a*b^n -
(a^b)^2 = a^(b*2)
extend:
(a^b)^b = a^b^2 generalize:
(.a.)^b.. {#n#} = a^b^n -
a^^b1 =
a^a^^b <~
(a^^2)^^2 = a^a^a1
(a^^3)^^2 {a↑ω} = a^a^(a1^a /ê)
(a^^b)^^2 = a^a^(a^^(b-1)+a^^(b-2)) <~
1\3'a^^b1 {b>2} = a^a^(a+1)^a^^(b-2)
< a^^b2 extend to: -
a^^bb- <~
(a^^b)^^b = a^(a^b-*..a^^b.) {#b-#} <~
(a^^b)^^3 ~ a^a^a^a1^a^^b-- = a^^(b+2)\b-'1
a^^(b+b-1)\b-'1 = 1\b1'a^^bb-
< a^^(b*2) generalize: -
a^^b(b-*n-) <~
(.a.)^^b.. {#n#} <~
((a^^b)^^b)^^2 ~ a^^bb-^a^^bb- ~ a^^bb\b-'1
((a^^b)^^b)^^b ~ a^^bbb--
a^^((b-1)*n+1)\b-'1 < a^^(b-*n)2
< a^^(b*n)
From three arrows onwards these comparisons are exceedingly difficult to resolve.
It can be guessed from the estimated ranges above that pentation
^^^
leaves very large holes,
where most numbers are lost in jeopardy.
Consider the following operations –
in between there are widening
number holes
looming.
Again these equations won't stop at anything –
click here!
(3^^^2)^^^2 = (3^^3)^^3^^3
= 3^^3^...3^^3 {#(3^^3)-}
~ 3^^3^...3^^4 {#(3^^3)--}
~ 3^^(3^27+2) <
3^^4^^3 = 3^^(4^256) <
3^^3^^4 = 3^^(3^7625597484987) <
3^^^4 = 3^^3^^(3^27) <~
(3^^^3)^^^2 = 3^^^3^^3^^^3
= 3^^^3^...3^^^3 {#(3^^^3)-}
~ 3^^^3^...3^3^^3^^3 {#(3^^^3)--}
~ 3^^^3^...3^^(2+3^27) {#(3^^^3)---}
~ 3^^(3^^3^^3-1+3^27) <~
(3^^^2)^^^3 = (3^^3)^^(3^^^2)^^^2
(substitute and..
~ 3^^(3^^(3^27+2)+2)
..iterate as in line 2 above)
~ 3^^^4\2"+2 <
(3^^^3)^^^3 ~ (3^^^3)^^3^^(3^^3^^3+3^27-1)
~ 3^^(3^^(3^^3^^3+3^27)+3^27)
~ 3^^^5\3"+3^^3
We boldly generalize this to a
comparison formula for superpowers.
Calculations you can find in the
<page source>.
In the cases below let ^..
{^#c c>2}
and its reduction *..
{*#c}
continue from where we left, after
tetration.
Mark the specified repetition dots
...
in violet.
As usual arrows take precedence before stars.
-
a^..b1 =
a*..a^..b
<~
(a^..b)^..2 = a^..b*..a^..b <~
(a^..b-)\2"a^..b1 < 1\3'a^..b1 < a^..b2 -
a^..bm =
a*.. ...a^..b
{#m}
<~
(a^..b)^..m1 = a^..b*.. ...a^..b {#m} -
a^..(b*n)1
<~
(.a.)^..b1.. {#n#} <
a^..(b1*n) .