Knuthův zápis

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í

$a\times b=\underset{b\text{ opakování }a}{\underbrace{a+a+\dots +a}}.$

Příklad:

$4\times 3=\underset{3\text{ opakování }4}{\underbrace{4+4+4}}=12$

Operátor umocňování

Umocňování na přirozený exponent $b$ lze definovat jako opakované násobení, což Knuth označil jednou šipkou vzhůru

$a\uparrow b=a^b=\underset{b\text{ opakování }}{\underbrace{a\times a\times \dots \times a}}.$

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\uparrow 3=4^3=\underset{3\text{ opakování }4}{\underbrace{4\times 4\times 4}}=64$

Operátor tetrace

Zobecněním tohoto postupu za operaci umocňování vznikne tetrace, pro kterou zavedl Knuth operátor „dvojité šipky“,

$a\uparrow \uparrow b={}^{b}a=\underset{b\text{ opakování }a}{\underbrace{a^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}}=\underset{b\text{ opakování }a}{\underbrace{a\uparrow (a\uparrow (\dots \uparrow a))}}.$

Zde je vhodné připomenout, že umocňování je asociativní zprava. Konkrétně to lze ilustrovat např.

$a\uparrow \uparrow 3=a^{a^a}=a\uparrow (a\uparrow a)\ne (a\uparrow a)\uparrow a={(a^a)}^a=a^{a\cdot a}=a^{a^2}$

pro číslo $a\ne 2$. Stejně tak i další hyperoperace budou (v šipkovém zápisu) asociativní zprava.

Příklady:

$4\uparrow \uparrow 3={}^{3}4=\underset{3\text{ opakování }4}{\underbrace{4^{4^4}}}=\underset{3\text{ opakování }4}{\underbrace{4\uparrow (4\uparrow 4)}}=4^{256}\approx 1,3\times 10^{154}$

$3\uparrow \uparrow 2=3^3=27$

$3\uparrow \uparrow 3=3^{3^3}=3^{27}=7625597484987$

$3\uparrow \uparrow 4=3^{3^{3^3}}=3^{7625597484987}$

$3\uparrow \uparrow 5=3^{3^{3^{3^3}}}=3^{3^{7625597484987}}$

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,

$a\uparrow \uparrow \uparrow b=\underset{b\text{ opakování }a}{\underbrace{{}^{{}^{{}^{{}^{{}^a\cdot }\cdot }\cdot }a}a}}=\underset{b\text{ opakování }a}{\underbrace{a\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))}}.$

Příklady:

$\begin{array}{cc}3\uparrow \uparrow \uparrow 2& =3\uparrow \uparrow 3={}^{3}3=\\ & =3\uparrow (3\uparrow 3)=3^{3^3}=3^{27}=7625597484987\\ \end{array}$

Velikost čísel roste opravdu velmi rychle

$\begin{array}{cc}3\uparrow \uparrow \uparrow 3& =3\uparrow \uparrow (3\uparrow \uparrow 3)={}^{{}^{3}3}3={}^{7625597484987}3=\\ & =3\uparrow \uparrow (3\uparrow (3\uparrow 3))=\underset{3\uparrow (3\uparrow 3)=7625597484987\text{ opakování }3}{\underbrace{3\uparrow (3\uparrow (\dots \uparrow 3))}}=\underset{3\uparrow (3\uparrow 3)\text{ opakování }3}{\underbrace{3^{3^{{\cdot }^{{\cdot }^{{\cdot }^3}}}}}}\approx {\exp }_{10}^{7625597484987}(1.09902).\end{array}$

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)}$.

Následující číslo má v klasickém zápisu více než 10¹⁰²¹⁸⁴ číslic

$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)$

Vyšší operátory

Dále operátor „čtyř šipek“,

$a\uparrow \uparrow \uparrow \uparrow b=\underset{b\text{ opakování }a}{\underbrace{a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))}}$

atd. Obecně je „$n$-šipkový operátor“ sekvencí „($n-1$)-šipkových operátorů“. S využitím zápisu

$a{\uparrow }^{n}b=a\underset{n\text{ šipek}}{\underbrace{\uparrow \uparrow \dots \uparrow }}b$

vznikne

$a{\uparrow }^{n}b=a\underset{n\text{ šipek}}{\underbrace{\uparrow \uparrow \dots \uparrow }}b=\underset{b\text{ opakování }a}{\underbrace{a\underset{n-1}{\underbrace{\uparrow \dots \uparrow }}(a\underset{n-1}{\underbrace{{\uparrow }_{}\dots \uparrow }}(\dots \underset{n-1}{\underbrace{{\uparrow }_{}\dots \uparrow }}a))}}=\underset{b\text{ opakování }a}{\underbrace{a{\uparrow }^{n-1}(a{\uparrow }^{n-1}(\dots {\uparrow }^{n-1}a))}}.$

Základní operace a nevýhody značení

Základní operace lze vyjádřit pomocí Knuthova zápisu následovně:

$\begin{array}{cc}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 ${\uparrow }^{-1}$ (tj. $a{\uparrow }^{-1}b=a+b$), který však evokuje inverzní operaci k $\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).

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;
}