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.
Umocňování na přirozený exponent lze definovat jako opakované násobení, což Knuth označil jednou šipkou vzhůru
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:
Operátor tetrace
Zobecněním tohoto postupu za operaci umocňování vznikne tetrace, pro kterou zavedl Knuth operátor „dvojité šipky“,
Zde je vhodné připomenout, že umocňování je asociativní zprava. Konkrétně to lze ilustrovat např.
pro číslo . Stejně tak i další hyperoperace budou (v šipkovém zápisu) asociativní zprava.
Příklady:
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,
Příklady:
Velikost čísel roste opravdu velmi rychle
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
Vyšší operátory
Dále operátor „čtyř šipek“,
atd. Obecně je „-šipkový operátor“ sekvencí „()-šipkových operátorů“. S využitím zápisu
vznikne
Základní operace a nevýhody značení
Základní operace lze vyjádřit pomocí Knuthova zápisu následovně:
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).
Programátorská implementace Knuthova zápisu
Knuthův zápis v jazyce JavaScript
Implementace správně funguje (z hlediska logiky) pouze pro nezáporná celá čísla. Teoreticky se zde předpokládá, že proměnné jsou celočíselné a lze to nich uložit libovolně velkou hodnotu.
Nejdříve je potřeba vysvětlit dno rekurze:
0 šipek je násobení, to je jednoduché. Pokud je počet nenulový, je potřeba jít dále.
Pokud je pravá strana 0, tak je výsledkem triviálně číslo 1. Cokoliv umocněno na 0 je rovno 1 a toto platí to obecně i pro vyšší hyperoperace.
Dále už se jedná o netriviální případ a postup je tento:
Rekurzivně se bude volat o jeden stupeň nižší hyperoperace, proto "arrowCount--".
Počet opakování rekurze je také o 1 nižší. Neboť například 33 je tři na třetí, tedy 3 x 3 x 3. Trojka se opakuje 3x, nicméně počet iterací násobení je o 1 menší. Toto platí rovněž obecně, proto "right--".
Následně se do proměnné "result" přiřadí levá proměnná (číslo, které se opakuje) a na ní se pak rekurzivně opakuje operace, kde pravou vstupní proměnou je výsledek z předchozího cyklu.
Reference
V tomto článku byl použit překlad textu z článku Knuth's up-arrow notation na anglické Wikipedii.