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.
Úvod
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í
![{\displaystyle a\times b=\underbrace {a+a+\dots +a} _{b{\text{ opakování }}a}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/653b462a2c9f73c1b1053193f55263fcb6861bfe)
Příklad:
![{\displaystyle 4\times 3=\underbrace {4+4+4} _{3{\text{ opakování }}4}=12}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c4a22bedc9484368a977ad52a1c8ae8da9c2cf6)
Operátor umocňování
Umocňování na přirozený exponent
lze definovat jako opakované násobení, což Knuth označil jednou šipkou vzhůru
![{\displaystyle a\uparrow b=a^{b}=\underbrace {a\times a\times \dots \times a} _{b{\text{ opakování }}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7298ed934495cb148713951bbd8e39535eb6c4cf)
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:
![{\displaystyle 4\uparrow 3=4^{3}=\underbrace {4\times 4\times 4} _{3{\text{ opakování }}4}=64}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a66a3e40cc282c23d688bbcd32ee33fe866cf41)
Operátor tetrace
Zobecněním tohoto postupu za operaci umocňování vznikne tetrace, pro kterou zavedl Knuth operátor „dvojité šipky“,
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ca6fa32fa0efc503b0ef62506afb4f19aa74f09)
Zde je vhodné připomenout, že umocňování je asociativní zprava. Konkrétně to lze ilustrovat např.
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d855597762ef6ef9b87f91679b0feeb46853522a)
pro číslo
. Stejně tak i další hyperoperace budou (v šipkovém zápisu) asociativní zprava.
Příklady:
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72aa92133ed2c244e6b7d29417beedcf9fa882a7)
![{\displaystyle 3\uparrow \uparrow 2=3^{3}=27}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5217b6f0699e9e634d31a294211ccbc027f3cd0)
![{\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05918a69459c2c53cc55438a5fc3720146bc1c93)
![{\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2889355bb8f046103e7280d96e638fcce362abe)
![{\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{7\,625\,597\,484\,987}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f47b9249251839ab16f441b2c30ceef86b9211a2)
Operátor pentace
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,
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eaeb751cc6933822127ea515dbda86baf341f220)
Příklady:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc677853ca2048c79b81234d1acea608fab9a709)
Velikost čísel roste opravdu velmi rychle
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c484841b22398f5861b42611aad0a7869adae0a)
Horní index u exponenciální funkce zde neznačí mocninu ale počet složenin, tj.
.
Následující číslo má v klasickém zápisu více než 10102184 číslic
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30ea0ca9ee4815f3f23119f8e60e1b564dbeb712)
Vyšší operátory
Dále operátor „čtyř šipek“,
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/968d3e260a4a48d5d7ec499104fd6da322bc27ee)
atd. Obecně je „
-šipkový operátor“ sekvencí „(
)-šipkových operátorů“. S využitím zápisu
![{\displaystyle a\uparrow ^{n}b=a\,\underbrace {\uparrow \uparrow \!\!\dots \!\!\uparrow } _{n{\text{ šipek}}}\,b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecc6c7c48132293c516010501b8ce7bb192664e7)
vznikne
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b06db62e1ca5d1011e067ab57809d184f1e8e53d)
Základní operace a nevýhody značení
Základní operace lze vyjádřit pomocí Knuthova zápisu následovně:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b07e42c4d55e5cfe63e825cc9f5ab961ddc319ad)
atd.
Zjevnou nevýhodou je, že pro sčítání by bylo třeba zavést symbol
(tj.
), který však evokuje inverzní operaci k
.
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).
Teoretická programátorská implementace Knuthova zápisu v jazyce JavaScript
// non-negative integers only
function Knuth(left, arrowCount, right) {
if (arrowCount <= 0)
return left * right;
if (right <= 0)
return 1;
arrowCount--;
right--;
var result = left;
for (var i = 0; i < right; i++)
result = Knuth(left, arrowCount, result);
return result;
}
Reference
V tomto článku byl použit překlad textu z článku Knuth's up-arrow notation na anglické Wikipedii.
Portály: Matematika