Knuthův zápis je způsob zápisu velkých čísel zavedený Donaldem Knuthem v roce 1976. Idea zápisu je, že násobení se může brát jako opakované sčítání, a umocňování jako opakované násobení. Pokračování tímto způsobem spěje k opakovanému umocňování (tetraci ) a k dalším operacím.
Základní matematické operace sčítání , násobení a umocňování jsou přirozeně rozšířeny do sekvence hyperoperací následujícím způsobem.
Násobení přirozeným číslem lze definovat jako opakované sčítání
a
×
b
=
a
+
a
+
⋯
+
a
⏟
b
opakování
a
.
{\displaystyle a\times b=\underbrace {a+a+\dots +a} _{b{\text{ opakování }}a}.}
Příklad:
4
×
3
=
4
+
4
+
4
⏟
3
opakování
4
=
12
{\displaystyle 4\times 3=\underbrace {4+4+4} _{3{\text{ opakování }}4}=12}
Umocňování na přirozený exponent
b
{\displaystyle b}
lze definovat jako opakované násobení, což Knuth označil jednou šipkou vzhůru
a
↑
b
=
a
b
=
a
×
a
×
⋯
×
a
⏟
b
opakování
.
{\displaystyle a\uparrow b=a^{b}=\underbrace {a\times a\times \dots \times a} _{b{\text{ opakování }}}.}
Tento zápis se běžně užívá k psaní mocnin v některých programovacích jazycích, případně při psaní s omezenou znakovou sadou (např. ASCII , bez možnosti sázet horní indexy) s využitím symbolu stříšky (cicumflexu) a^b
.
Příklad:
4
↑
3
=
4
3
=
4
×
4
×
4
⏟
3
opakování
4
=
64
{\displaystyle 4\uparrow 3=4^{3}=\underbrace {4\times 4\times 4} _{3{\text{ opakování }}4}=64}
Zobecněním tohoto postupu za operaci umocňování vznikne tetrace, pro kterou zavedl Knuth operátor „dvojité šipky“,
a
↑↑
b
=
b
a
=
a
a
.
.
.
a
⏟
b
opakování
a
=
a
↑
(
a
↑
(
⋯
↑
a
)
)
⏟
b
opakování
a
.
{\displaystyle a\uparrow \uparrow b={\ ^{b}a}=\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} _{b{\text{ opakování }}a}=\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} _{b{\text{ opakování }}a}.}
Zde je vhodné připomenout, že umocňování je asociativní zprava . Konkrétně to lze ilustrovat např.
a
↑↑
3
=
a
a
a
=
a
↑
(
a
↑
a
)
≠
(
a
↑
a
)
↑
a
=
(
a
a
)
a
=
a
a
⋅
a
=
a
a
2
{\displaystyle a\uparrow \uparrow 3=a^{a^{a}}=a\uparrow (a\uparrow a)\neq (a\uparrow a)\uparrow a={(a^{a})}^{a}=a^{a\cdot a}=a^{a^{2}}}
pro číslo
a
≠
2
{\displaystyle a\neq 2}
. Stejně tak i další hyperoperace budou (v šipkovém zápisu) asociativní zprava.
Příklady:
4
↑↑
3
=
3
4
=
4
4
4
⏟
3
opakování
4
=
4
↑
(
4
↑
4
)
⏟
3
opakování
4
=
4
256
≈
1
,
3
×
10
154
{\displaystyle 4\uparrow \uparrow 3={\ ^{3}4}=\underbrace {4^{4^{4}}} _{3{\text{ opakování }}4}=\underbrace {4\uparrow (4\uparrow 4)} _{3{\text{ opakování }}4}=4^{256}\approx 1,3\times 10^{154}}
3
↑↑
2
=
3
3
=
27
{\displaystyle 3\uparrow \uparrow 2=3^{3}=27}
3
↑↑
3
=
3
3
3
=
3
27
=
7
625
597
484
987
{\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987}
3
↑↑
4
=
3
3
3
3
=
3
7
625
597
484
987
{\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}}
3
↑↑
5
=
3
3
3
3
3
=
3
3
7
625
597
484
987
{\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{7\,625\,597\,484\,987}}}
Již „dvoušipkový“ operátor vede na velká čísla , ale Knuth notaci rozšířil. Definoval operátor „trojité šipky“ pro opakování operátoru „dvojité šipky“ neboli pentaci ,
a
↑↑↑
b
=
a
⋅
⋅
⋅
a
a
⏟
b
opakování
a
=
a
↑↑
(
a
↑↑
(
…
↑↑
a
)
)
⏟
b
opakování
a
.
{\displaystyle a\uparrow \uparrow \uparrow b=\underbrace {{}^{{}^{{}^{{}^{{}^{a}\cdot }\cdot }\cdot }a}a} _{b{\text{ opakování }}a}=\underbrace {a\,\uparrow \uparrow \,(a\,\uparrow \uparrow \,(\dots \,\uparrow \uparrow \,a))} _{b{\text{ opakování }}a}.}
Příklady:
3
↑↑↑
2
=
3
↑↑
3
=
3
3
=
=
3
↑
(
3
↑
3
)
=
3
3
3
=
3
27
=
7
625
597
484
987
{\displaystyle {\begin{aligned}3\uparrow \uparrow \uparrow 2&=3\uparrow \uparrow 3={}^{3}3=\\&=3\uparrow (3\uparrow 3)=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987\\\end{aligned}}}
Velikost čísel roste opravdu velmi rychle
3
↑↑↑
3
=
3
↑↑
(
3
↑↑
3
)
=
3
3
3
=
7
625
597
484
987
3
=
=
3
↑↑
(
3
↑
(
3
↑
3
)
)
=
3
↑
(
3
↑
(
⋯
↑
3
)
)
⏟
3
↑
(
3
↑
3
)
=
7
625
597
484
987
opakování
3
=
3
3
⋅
⋅
⋅
3
⏟
3
↑
(
3
↑
3
)
opakování
3
≈
exp
10
7
625
597
484
987
(
1.09902
)
.
{\displaystyle {\begin{aligned}3\uparrow \uparrow \uparrow 3&=3\uparrow \uparrow (3\uparrow \uparrow 3)={}^{{}^{3}3}3={}^{7\,625\,597\,484\,987}3=\\&=3\uparrow \uparrow (3\uparrow (3\uparrow 3))=\underbrace {3\uparrow (3\uparrow (\dots \uparrow 3))} _{3\uparrow (3\uparrow 3)=7\,625\,597\,484\,987{\text{ opakování }}3}=\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{3\uparrow (3\uparrow 3){\text{ opakování }}3}\approx \exp _{10}^{7\,625\,597\,484\,987}(1.09902).\end{aligned}}}
Horní index u exponenciální funkce zde neznačí mocninu ale počet složenin, tj.
exp
k
n
(
x
)
=
exp
k
(
exp
k
n
−
1
(
x
)
)
=
k
exp
k
n
−
1
(
x
)
{\displaystyle \exp _{k}^{n}(x)=\exp _{k}(\exp _{k}^{n-1}(x))=k^{\,\exp _{k}^{n-1}(x)}}
.
Následující číslo má v klasickém zápisu více než 10102184 číslic
5
↑↑↑
2
=
5
↑↑
5
=
5
5
=
5
5
5
5
5
=
5
5
5
3125
≈
10
10
10
10
3.33928
=
exp
10
4
(
3.33928
)
{\displaystyle 5\uparrow \uparrow \uparrow 2=5\uparrow \uparrow 5={^{5}5}=5^{5^{5^{5^{5}}}}=5^{5^{5^{3125}}}\approx 10^{10^{10^{10^{3.33928}}}}=\exp _{10}^{4}(3.33928)}
Dále operátor „čtyř šipek“,
a
↑↑↑↑
b
=
a
↑↑↑
(
a
↑↑↑
(
⋯
↑↑↑
a
)
)
⏟
b
opakování
a
{\displaystyle a\uparrow \uparrow \uparrow \uparrow b=\underbrace {a\,\uparrow \uparrow \uparrow \,(a\,\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow \,a))} _{b{\text{ opakování }}a}}
atd. Obecně je „
n
{\displaystyle n}
-šipkový operátor“ sekvencí „(
n
−
1
{\displaystyle n-1}
)-šipkových operátorů“. S využitím zápisu
a
↑
n
b
=
a
↑↑
…
↑
⏟
n
šipek
b
{\displaystyle a\uparrow ^{n}b=a\,\underbrace {\uparrow \uparrow \!\!\dots \!\!\uparrow } _{n{\text{ šipek}}}\,b}
vznikne
a
↑
n
b
=
a
↑↑
…
↑
⏟
n
šipek
b
=
a
↑
…
↑
⏟
n
−
1
(
a
↑
…
↑
⏟
n
−
1
(
…
↑
…
↑
⏟
n
−
1
a
)
)
⏟
b
opakování
a
=
a
↑
n
−
1
(
a
↑
n
−
1
(
…
↑
n
−
1
a
)
)
⏟
b
opakování
a
.
{\displaystyle a\uparrow ^{n}b=a\,\underbrace {\uparrow \uparrow \!\!\dots \!\!\uparrow } _{n{\text{ šipek}}}\,b\;=\;\underbrace {a\,\underbrace {\uparrow \!\!\dots \!\!\uparrow } _{n-1}\,(a\,\underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\,(\dots \,\underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\,a))} _{b{\text{ opakování }}a}\;=\;\underbrace {a\uparrow ^{n-1}(a\uparrow ^{n-1}(\ldots \uparrow ^{n-1}a))} _{b{\text{ opakování }}a}.}
Základní operace a nevýhody značení
editovat
Základní operace lze vyjádřit pomocí Knuthova zápisu následovně:
a
↑
0
b
=
a
×
b
(násobení),
a
↑
1
b
=
a
b
(umocňování),
a
↑
2
b
=
b
a
(tetrace),
a
↑
3
b
=
a
↑↑↑
b
(pentace),
{\displaystyle {\begin{array}{ll}a\uparrow ^{0}b=a\times b&{\text{ (násobení),}}\\a\uparrow ^{1}b=a^{b}&{\text{ (umocňování),}}\\a\uparrow ^{2}b={}^{b}a&{\text{ (tetrace),}}\\a\uparrow ^{3}b=a\!\uparrow \uparrow \uparrow \!b&{\text{ (pentace),}}\end{array}}}
atd.
Zjevnou nevýhodou je, že pro sčítání by bylo třeba zavést symbol
↑
−
1
{\displaystyle \uparrow ^{-1}}
(tj.
a
↑
−
1
b
=
a
+
b
{\displaystyle a\uparrow ^{-1}b=a+b}
), který však evokuje inverzní operaci k
↑
{\displaystyle \uparrow }
.
S tím souvisí i posunutí názvosloví vzhledem k počtu
šipek použitých k označení operátoru
(tetrace, pentace, tedy čtvrtá, resp. pátá operace jsou značeny pomocí dvou, případně tří šipek).