Dobbel eksponentiell funksjon - Double exponential function

En dobbel eksponensiell funksjon (rød kurve) sammenlignet med en enkelt eksponentiell funksjon (blå kurve).

En dobbel eksponensiell funksjon er en konstant hevet til makten til en eksponensiell funksjon . Den generelle formelen er (hvor a > 1 og b > 1), som vokser mye raskere enn en eksponensiell funksjon. For eksempel, hvis 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 100} = googolplex .

Factorials vokser raskere enn eksponensielle funksjoner, men mye saktere enn dobbelt eksponentielle funksjoner. Men tetration og Ackermann funksjon vokse raskere. Se Big O -notasjon for en sammenligning av veksthastigheten til forskjellige funksjoner.

Det inverse av den doble eksponensielle funksjonen er den doble logaritmen ln (ln ( x )).

Dobbelt eksponentielle sekvenser

En sekvens med positive heltall (eller reelle tall) sies å ha en dobbel eksponentiell veksthastighet hvis funksjonen som gir den n. Termen i sekvensen er begrenset over og under av dobbelt eksponentielle funksjoner til n . Eksempler inkluderer

• De Fermat-tall
  $${\ displaystyle F (m) = 2^{2^{m}}+1}$$

  
• De harmoniske primtalene: Primene p , der sekvensen 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/ p overstiger 0, 1, 2, 3, ...
  De første tallene, som begynner med 0, er 2, 5, 277, 5195977, ... (sekvens A016088 i OEIS )
• The Double Mersenne numbers
  $${\ displaystyle MM (p) = 2^{2^{p} -1} -1}$$

  
• Elementene i Sylvesters sekvens (sekvens A000058 i OEIS )
  $${\ displaystyle s_ {n} = \ left \ lfloor E^{2^{n+1}}+{\ frac {1} {2}} \ right \ rfloor}$$

  
  hvor E ≈ 1.264084735305302 er Vardis konstant (sekvens A076393 i OEIS ).
• Antall k -ary boolske funksjoner :
  $${\ displaystyle 2^{2^{k}}}$$

  
• Primtallene 2, 11, 1361, ... (sekvens A051254 i OEIS )
  $${\ displaystyle a (n) = \ left \ lfloor A^{3^{n}} \ right \ rfloor}$$

  
  hvor A ≈ 1.306377883863 er Mills 'konstant .

Aho og Sloane observerte at i flere viktige heltallssekvenser er hvert begrep en konstant pluss kvadratet til forrige ledd. De viser at slike sekvenser kan dannes ved å avrunde verdiene til en dobbelt eksponentiell funksjon med midtre eksponent til nærmeste heltall 2. Ionaşcu og Stănică beskriver noen mer generelle tilstrekkelige betingelser for at en sekvens skal være gulvet i en dobbel eksponentiell sekvens pluss en konstant .

applikasjoner

Algoritmisk kompleksitet

I beregningskompleksitetsteori tar noen algoritmer dobbel eksponentiell tid:

• Hver beslutningsprosedyre for Presburger -aritmetikk krever sannsynligvis minst dobbelt eksponentiell tid
• Beregning av et Gröbner -grunnlag over et felt. I verste fall kan et Gröbner -grunnlag ha en rekke elementer som er dobbelt eksponentiell i antall variabler. På den annen side er kompleksiteten i verste tilfelle av Gröbner-basisalgoritmer dobbelt eksponentiell i antall variabler så vel som i oppføringsstørrelsen.
• Finne et komplett sett med assosiativ-kommutative unifiers
• Tilfredsstillende CTL ⁺ (som faktisk er 2 -EXPTIME -fullstendig )
• Kvantifiseringseliminering på virkelige lukkede felt tar dobbelt eksponentiell tid (se sylindrisk algebraisk dekomponering ).
• Beregning av komplementet til et vanlig uttrykk

I noen andre problemer ved design og analyse av algoritmer brukes dobbelt eksponentielle sekvenser i utformingen av en algoritme i stedet for i analysen. Et eksempel er Chans algoritme for å beregne konvekse skrog , som utfører en sekvens av beregninger ved hjelp av testverdier h _i  = 2 ^{2 i} (estimater for den endelige utgangsstørrelsen), og tar tid O ( n  log  h _i ) for hver testverdi i sekvensen . På grunn av den doble eksponentielle veksten av disse testverdiene, vokser tiden for hver beregning i sekvensen enkeltvis eksponentielt som en funksjon av i , og den totale tiden domineres av tiden for det siste trinnet i sekvensen. Dermed er den totale tiden for algoritmen O ( n  log  h ) hvor h er den faktiske utgangsstørrelsen.

Tallteori

Noen tallteoretiske grenser er doble eksponentielle. Uvanlige perfekte tall med n distinkte primfaktorer er kjent for å være på det meste

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

et resultat av Nielsen (2003). Den maksimale volumet av en d -lattice polytop med k ≥ 1 indre gitterpunkter er høyst

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

et resultat av Pikhurko.

Det største kjente primtallet i den elektroniske epoken har vokst omtrent som en dobbel eksponentiell funksjon av året siden Miller og Wheeler fant en 79-sifret prim på EDSAC 1 i 1951.

Teoretisk biologi

I befolkningsdynamikk skal veksten i menneskelig befolkning noen ganger være dobbel eksponentiell. Varfolomeyev og Gurevich passet eksperimentelt

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

hvor N ( y ) er befolkningen i millioner i år y .

Fysikk

I Toda oscillator modell av selv-pulsering , logaritmen av amplituden varierer eksponensielt med tiden (for store amplituder), og således amplituden varierer som dobbelt eksponentiell funksjon av tiden.

Dendrittiske makromolekyler har blitt observert å vokse på en dobbelt-eksponentiell måte.

Referanser