Funcție exponențială dublă - Double exponential function

O funcție exponențială dublă (curbă roșie) comparată cu o singură funcție exponențială (curbă albastră).

O funcție exponențială dublă este o constantă ridicată la puterea unei funcții exponențiale . Formula generală este (unde a > 1 și b > 1), care crește mult mai repede decât o funcție exponențială. De exemplu, dacă a = b = 10: ${\ displaystyle f (x) = a ^ {b ^ {x}} = a ^ {(b ^ {x})}}$

f (0) = 10
f (1) = 10 ¹⁰
f (2) = 10 ¹⁰⁰ = googol
f (3) = 10 ¹⁰⁰⁰
f (100) = 10 ^{10 ¹⁰⁰} = googolplex .

Factorii cresc mai repede decât funcțiile exponențiale, dar mult mai încet decât funcțiile dublu exponențiale. Cu toate acestea, tetrarea și funcția Ackermann cresc mai repede. A se vedea notația Big O pentru o comparație a ratei de creștere a diferitelor funcții.

Inversa funcției exponențiale duble este logaritmul dublu ln (ln ( x )).

Secvențe dublu exponențiale

Se spune că o secvență de numere întregi pozitive (sau numere reale) are o rată de creștere dublu exponențială dacă funcția care dă al $n-$ lea termen al secvenței este delimitată deasupra și dedesubt de funcții dublu exponențiale ale lui $n$ . Exemplele includ

Cele Numerele Fermat ${\ displaystyle F (m) = 2 ^ {2 ^ {m}} + 1}$
Primele armonice: Primele p , în care secvența 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1 / p depășește 0, 1, 2, 3, ...
Primele câteva numere, începând cu 0, sunt 2, 5, 277, 5195977, ... (secvența A016088 din OEIS )
Cele Numerele dublu Mersenne ${\ displaystyle MM (p) = 2 ^ {2 ^ {p} -1} -1}$
Elementele secvenței lui Sylvester (secvența A000058 din OEIS ) ${\ displaystyle s_ {n} = \ left \ lfloor E ^ {2 ^ {n + 1}} + {\ frac {1} {2}} \ right \ rfloor}$ unde E ≈ 1.264084735305302 este constanta lui Vardi (secvența A076393 în OEIS ).
Numărul de funcții booleene k -ary : ${\ displaystyle 2 ^ {2 ^ {k}}}$
Numerele prime 2, 11, 1361, ... (secvența A051254 din OEIS ) ${\ displaystyle a (n) = \ left \ lfloor A ^ {3 ^ {n}} \ right \ rfloor}$ unde A ≈ 1.306377883863 este constanta lui Mills .

Aho și Sloane au observat că, în câteva secvențe întregi importante , fiecare termen este o constantă plus pătratul termenului anterior. Acestea arată că astfel de secvențe pot fi formate prin rotunjirea la cel mai apropiat număr întreg a valorilor unei funcții dublu exponențiale cu exponentul mediu 2. Ionașcu și Stănică descriu câteva condiții suficiente mai generale pentru ca o secvență să fie podeaua unei secvențe dublu exponențiale plus o constantă .

Aplicații

Complexitate algoritmică

În teoria complexității de calcul , unii algoritmi au timp dublu exponențial:

Fiecare procedură de decizie pentru aritmetica Presburger necesită în mod probabil timp de cel puțin dublu exponențial
Calculul unei baze Gröbner pe un câmp. În cel mai rău caz, o bază Gröbner poate avea un număr de elemente care este dublu exponențial în numărul de variabile. Pe de altă parte, complexitatea în cel mai rău caz a algoritmilor bazei Gröbner este dublu exponențială atât în numărul de variabile, cât și în dimensiunea intrării.
Găsirea unui set complet de unificatoare asociativ-comutative
Satisfăcător CTL ⁺ (care este, de fapt, 2-EXPTIME- complet)
Eliminarea cuantificatorului pe câmpuri închise reale necesită timp dublu exponențial (a se vedea Descompunerea algebrică cilindrică ).
Calculul complementului unei expresii regulate

În unele alte probleme legate de proiectarea și analiza algoritmilor, secvențele dublu exponențiale sunt utilizate în proiectarea unui algoritm, mai degrabă decât în analiza acestuia. Un exemplu este algoritmul lui Chan pentru calcularea corpurilor convexe , care efectuează o secvență de calcule folosind valorile de testare h _i = 2 ^{2 ⁱ} (estimări pentru eventuala dimensiune de ieșire), luând timp O ( n log h _i ) pentru fiecare valoare de test din secvență . Datorită creșterii duble exponențiale a acestor valori de testare, timpul pentru fiecare calcul din secvență crește exponențial individual în funcție de i , iar timpul total este dominat de timpul pentru pasul final al secvenței. Astfel, timpul total pentru algoritm este O ( n log h ) unde h este dimensiunea reală de ieșire.

Teoria numerelor

Unele limite teoretice sunt duble exponențiale. Se știe că numerele perfecte impare cu n factori primi distincti sunt cel mult

{\ displaystyle 2 ^ {4 ^ {n}}}

un rezultat al lui Nielsen (2003). Volumul maxim al unui politop d- rețea cu k ≥ 1 puncte de rețea interioare este cel mult

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

un rezultat al lui Pikhurko.

Cel mai mare număr prim cunoscut în era electronică a crescut aproximativ ca o funcție exponențială dublă a anului de când Miller și Wheeler au găsit un prim de 79 de cifre pe EDSAC 1 în 1951.

Biologie teoretică

În dinamica populației , creșterea populației umane se presupune că este uneori dublă exponențială. Varfolomeyev și Gurevich se potrivesc experimental

{\ displaystyle N (y) = 375,6 \ cdot 1.00185 ^ {1.00737 ^ {y-1000}} \,}

unde N ( y ) este populația în milioane în anul y .

Fizică

În modelul oscilator Toda de auto-pulsație , logaritmul amplitudinii variază exponențial cu timpul (pentru amplitudini mari), astfel amplitudinea variază ca funcție dublu exponențială a timpului.

S-a observat că macromoleculele dendritice cresc într-un mod dublu-exponențial.

Languages

In other projects