Dobbelt eksponentiel funktion - Double exponential function

En dobbelt eksponentiel funktion (rød kurve) sammenlignet med en enkelt eksponentiel funktion (blå kurve).

En dobbelt eksponentiel funktion er en konstant hævet til magten i en eksponentiel funktion . Den generelle formel er (hvor a > 1 og b > 1), som vokser meget hurtigere end en eksponentiel funktion. 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 hurtigere end eksponentielle funktioner, men meget langsommere end dobbelt eksponentielle funktioner. Men tetration og funktion Ackermann vokse hurtigere. Se Big O -notation for en sammenligning af væksthastigheden for forskellige funktioner.

Inversen af ​​den dobbelte eksponentielle funktion er den dobbelte logaritme ln (ln ( x )).

Dobbelt eksponentielle sekvenser

En sekvens af positive heltal (eller reelle tal) siges at have dobbelt eksponentiel vækst , hvis funktionen giver n th sigt af sekvensen er afgrænset foroven og forneden ved dobbelt eksponentielle funktioner af n . Eksempler omfatter

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

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

  
• Elementerne 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 ).
• Antallet af k -ary boolske funktioner :
  $${\ displaystyle 2^{2^{k}}}$$

  
• Primtalerne 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 observerede, at i flere vigtige heltalssekvenser er hvert udtryk en konstant plus kvadratet af det foregående udtryk. De viser, at sådanne sekvenser kan dannes ved at afrunde værdierne for en dobbelt eksponentiel funktion med midtereksponent 2. Ionaşcu og Stănică afrunder nogle mere generelle tilstrækkelige betingelser for, at en sekvens er gulvet i en dobbelt eksponentiel sekvens plus en konstant .

Ansøgninger

Algoritmisk kompleksitet

I beregningskompleksitetsteori tager nogle algoritmer dobbelt eksponentiel tid:

• Hver afgørelsesprocedure for Presburger -aritmetik kræver beviseligt mindst dobbelt eksponentiel tid
• Beregning af et Gröbner -grundlag over et felt. I værste fald kan et Gröbner -grundlag have et antal elementer, der er dobbelt eksponentielt i antallet af variabler. På den anden side er kompleksiteten i værste tilfælde af Gröbner-basisalgoritmer dobbelt eksponentiel i antallet af variabler såvel som i indgangsstørrelsen.
• At finde et komplet sæt associative-commutative unifiers
• Tilfredsstillende CTL ⁺ (hvilket faktisk er 2 -EXPTIME -complete )
• Eliminering af kvantificering på reelle lukkede felter tager dobbelt eksponentiel tid (se Cylindrisk algebraisk nedbrydning ).
• Beregning af komplementet til et regulært udtryk

I nogle andre problemer i design og analyse af algoritmer bruges dobbelt eksponentielle sekvenser inden for design af en algoritme frem for i dens analyse. Et eksempel er Chans algoritme til beregning af konvekse skrog , der udfører en sekvens af beregninger ved hjælp af testværdier h _i  = 2 ^{2 i} (estimater for den endelige outputstørrelse), hvilket tager tid O ( n  log  h _i ) for hver testværdi i sekvensen . På grund af den dobbelte eksponentielle vækst af disse testværdier vokser tiden for hver beregning i sekvensen enkeltvis eksponentielt som en funktion af i , og den samlede tid domineres af tiden for sekvensens sidste trin. Således er den samlede tid for algoritmen O ( n  log  h ), hvor h er den faktiske outputstørrelse.

Talteori

Nogle talteoretiske grænser er dobbelteksponentielle. Ulige perfekte tal med n adskilte primfaktorer vides højst at være

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

et resultat af Nielsen (2003). Den maksimale volumen af en d -lattice polytop med k ≥ 1 indvendige gitterpunkter er højst

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

et resultat af Pikhurko.

Det største kendte primtal i den elektroniske æra er vokset nogenlunde som en dobbelt eksponentiel funktion af året siden Miller og Wheeler fandt et 79-cifret primtal på EDSAC 1 i 1951.

Teoretisk biologi

I befolkningsdynamik formodes væksten i menneskelig befolkning undertiden at være dobbelt eksponentiel. Varfolomeyev og Gurevich passede eksperimentelt

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

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

Fysik

I Toda oscillator model af selv-pulsation , logaritmen af amplituden varierer eksponentielt med tiden (for store amplituder), således amplituden varierer som dobbelt eksponentiel funktion af tiden.

Der er observeret, at dendritiske makromolekyler vokser på en dobbelt-eksponentiel måde.

Referencer