Knuthův zápis

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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 = \underbrace{a+a+\dots+a}_{b\text{ opakování }a}.

Příklad:

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

Operátor umocňování[editovat | editovat zdroj]

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 = \underbrace{a\times a\times\dots\times a}_{b\text{ opakování }}.

Příklad:

4\uparrow 3= 4^3 = \underbrace{4\times 4\times 4}_{3\text{ opakování }4} = 64

Operátor tetrace[editovat | editovat zdroj]

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


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

Příklady:


  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\uparrow\uparrow2=3^3=27
3\uparrow\uparrow3=3^{3^3}=3^{27}=7\,625\,597\,484\,987
3\uparrow\uparrow4=3^{3^{3^3}}=3^{7\,625\,597\,484\,987}
3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7\,625\,597\,484\,987}}

Operátor pentace[editovat | editovat zdroj]

Již "operátor dvou šipek" 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 = 
  \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:


  \begin{align}
  3\uparrow\uparrow\uparrow2 &= 3\uparrow\uparrow3 = {}^33 = \\
  & = 3\uparrow(3\uparrow3) = 3^{3^3} = 3^{27}=7\,625\,597\,484\,987 \\
  \end{align}

Velikost čísel opravdu velmi rychle roste


  \begin{align}
  3\uparrow\uparrow\uparrow3 &= 3\uparrow\uparrow(3\uparrow\uparrow3) = {}^{ {}^3 3} 3 = {}^{7\,625\,597\,484\,987}3 = \\
  & = 3\uparrow\uparrow(3\uparrow(3\uparrow3)) = 
  \underbrace{3\uparrow(3\uparrow(\dots\uparrow 3))}_{3\uparrow(3\uparrow3)=7\,625\,597\,484\,987\text{ opakování }3}
  = \underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{3\uparrow(3\uparrow3)\text{ opakování }3} 
  \approx \exp_{10}^{7\,625\,597\,484\,987}(1.09902)
  \end{align}

Následující číslo má v klasickém zápisu více než 10102184 číslic

5 \uparrow\uparrow\uparrow2 = 5\uparrow\uparrow5 = {^{5}5} = 5^{5^{5^{5^5}}} = 5^{5^{5^{3125}}} \approx \exp_{10}^4(3.33928)

Vyšší operátory[editovat | editovat zdroj]

Dále operátor "čtyř šipek",


  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ě "n-šipkový operátor" zavedeme jako sekvenci "(n - 1)-šipkových operátorů". S využitím zápisu

a \uparrow^n b=a\,\underbrace{\uparrow\uparrow\!\!\dots\!\!\uparrow}_{n\text{ šipek}}\,b

dostaneme


  a\uparrow^nb = 
  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 | editovat zdroj]

Základní operace můžeme vyjádřit pomocí Knuthova zápisu následovně:


\begin{array}{ll}
  a\uparrow^0b=a\times b & \text{ (násobení),} \\
  a\uparrow^1b=a^b       & \text{ (umocňování),} \\
  a\uparrow^2b={}^ba     & \text{ (tetrace),} \\
  a\uparrow^3b=a\!\uparrow\uparrow\uparrow\!b & \text{ (pentace),}
\end{array}

atd.

Zjevnou nevýhodou je, že pro sčítání bychom potřebovali 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, tj. čtvrtá, resp. pátá operace jsou značeny pomocí dvou, resp. tří šipek).

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Knuth's up-arrow notation na anglické Wikipedii.