Dvojitá exponenciální funkce - Double exponential function

Dvojitá exponenciální funkce (červená křivka) ve srovnání s jedinou exponenciální funkcí (modrá křivka).

A dvojitý exponenciál funkce je a konstantní povýšen na sílu exponenciální funkce. Obecný vzorec je ${ displaystyle f (x) = a ^ {b ^ {x}} = a ^ {(b ^ {x})}}$ (kde A> 1 a b> 1), která roste mnohem rychleji než exponenciální funkce. Například pokud A = b = 10:

• F(0) = 10
• F(1) = 10¹⁰
• F(2) = 10¹⁰⁰ = googol
• F(3) = 10¹⁰⁰⁰
• F(100) = 10¹⁰¹⁰⁰ = googolplex.

Faktoriály rostou rychleji než exponenciální funkce, ale mnohem pomaleji než dvojnásobně exponenciální funkce. Nicméně, tetování a Ackermannova funkce rostou rychleji. Vidět Velká O notace pro srovnání rychlosti růstu různých funkcí.

Inverzní funkcí dvojité exponenciální funkce je dvojitý logaritmus ln (ln (X)).

Dvojnásobně exponenciální sekvence

Aho a Sloane poznamenal, že v několika důležitých celočíselné sekvence, každý člen je konstanta plus druhá mocnina předchozího členu. Ukazují, že takové posloupnosti lze vytvořit zaokrouhlením hodnot dvojnásobně exponenciální funkce, ve které je prostřední exponent dvě, na nejbližší celé číslo.^[1] Celé sekvence s tímto čtvercovým chováním zahrnují

• The Fermat čísla

${ displaystyle F (m) = 2 ^ {2 ^ {m}} + 1}$

• Harmonické prvočísla: Prvočísla p, ve kterých posloupnost 1/2 + 1/3 + 1/5 + 1/7 + ... + 1 / p přesahuje 0, 1, 2, 3, ...

Prvních několik čísel, počínaje 0, je 2, 5, 277, 5195977, ... (sekvence A016088 v OEIS )

• The Zdvojnásobte čísla Mersenne

${ displaystyle MM (p) = 2 ^ {2 ^ {p} -1} -1}$

• Prvky Sylvestrova sekvence (sekvence A000058 v OEIS )

${ displaystyle s_ {n} = left lfloor E ^ {2 ^ {n + 1}} + { frac {1} {2}} right rfloor}$

kde E ≈ 1,264084735305302 je Vardiho konstanta (sekvence A076393 v OEIS ).

• Počet k-ary Booleovské funkce:

${ displaystyle 2 ^ {2 ^ {k}}}$

Obecněji, pokud nta hodnota celé řady je úměrná dvojnásobné exponenciální funkci n„Ionaşcu a Stănică nazývají posloupnost„ téměř dvojnásobně exponenciální “a popisují podmínky, za kterých ji lze definovat jako minimum dvojnásobně exponenciální posloupnosti plus konstantu.^[2] Mezi další sekvence tohoto typu patří

• Prvočísla 2, 11, 1361, ... (sekvence A051254 v OEIS )

${ displaystyle a (n) = vlevo lfloor A ^ {3 ^ {n}} vpravo rfloor}$

kde A ≈ 1,306377883863 je Millsova konstanta.

Aplikace

Algoritmická složitost

v teorie výpočetní složitosti, některé algoritmy trvají dvojnásobně exponenciální čas:

• Každý rozhodovací postup pro Presburgerova aritmetika prokazatelně vyžaduje alespoň dvojnásobně exponenciální čas ^[3]
• Výpočet a Gröbnerův základ přes pole. V nejhorším případě může mít Gröbnerova báze řadu prvků, které jsou v počtu proměnných dvojnásobně exponenciální. Na druhou stranu nejhorší případ složitosti algoritmů Gröbnerovy báze je dvojnásobně exponenciální v počtu proměnných i ve velikosti vstupu.^[4]
• Nalezení úplné sady asociativně-komutativních unifikátorů ^[5]
• Uspokojující CTL⁺ (což je ve skutečnosti 2-EXPTIME -kompletní) ^[6]
• Vyloučení kvantifikátoru na skutečná uzavřená pole trvá dvojnásobně exponenciální čas (viz Válcový algebraický rozklad ).
• Výpočet doplněk a regulární výraz ^[7]

U některých dalších problémů při navrhování a analýze algoritmů se v návrhu algoritmu spíše než při jeho analýze používají dvojnásobně exponenciální sekvence. Příkladem je Chanův algoritmus pro výpočet konvexní trupy, který provádí posloupnost výpočtů pomocí testovacích hodnot h_i = 2²ⁱ (odhady pro případnou velikost výstupu), čas O (n logh_i) pro každou testovanou hodnotu v pořadí. Kvůli dvojitému exponenciálnímu růstu těchto testovacích hodnot čas pro každý výpočet v posloupnosti roste jednotlivě exponenciálně jako funkce ia celkovému času dominuje čas pro poslední krok sekvence. Celkový čas pro algoritmus je tedy O (n logh) kde h je skutečná velikost výstupu.^[8]

Teorie čísel

Nějaký číslo teoretické hranice jsou dvojité exponenciální. Zvláštní perfektní čísla s n je známo, že jsou nejvýraznější hlavní faktory

${ displaystyle 2 ^ {4 ^ {n}}}$

výsledek Nielsena (2003).^[9] Maximální objem a d-lattice polytop s k ≥ 1 vnitřní mřížové body je nanejvýš

${ displaystyle (8d) ^ {d} cdot 15 ^ {d cdot 2 ^ {2d + 1}}}$

výsledek Pikhurko.^[10]

The největší známé prvočíslo v elektronické éře se od té doby zhruba zdvojnásobila exponenciální funkce roku Mlynář a Kolář našel 79místný prime EDSAC 1 v roce 1951.^[11]

Teoretická biologie

v populační dynamika růst lidské populace je někdy považován za dvojnásobně exponenciální. Varfolomeyev a Gurevich^[12] experimentálně fit

${ displaystyle N (y) = 375,6 cdot 1,00185 ^ {1,00737 ^ {y-1000}} ,}$

kde N(y) je počet obyvatel v milionech za rok y.

Fyzika

V Toda oscilátor model vlastní pulzace, logaritmus amplitudy se mění exponenciálně s časem (pro velké amplitudy), takže se amplituda mění jako dvojnásobně exponenciální funkce času.^[13]

Dendritický makromolekuly bylo pozorováno, že rostou dvojnásobně exponenciálním způsobem.^[14]

Reference