Double exponential function

From Wikipedia, the free encyclopedia

This article is about double exponential functions. For the double exponential distribution, see Laplace distribution.

A double exponential function is a constant raised to the power of an exponential function. The general formula is f(x) = a^{b^x}, which grows even faster than an exponential function. For example, if a = b = 10:

  • f(−1) ≈ 1.26
  • f(0) = 10
  • f(1) = 1010
  • f(2) = 10100 = googol
  • f(3) = 101000
  • f(100) = 1010100 = googolplex

Factorials grow faster than exponential functions, but much slower than double-exponential functions. Compare the hyper-exponential function and Ackermann function, which grow even faster.

Contents

[edit] Doubly exponential sequences

Aho and Sloane observed that several important integer sequences satisfy a recurrence in which each term is a constant plus the square of the previous term, and show that such sequences can be formed by rounding to the nearest integer the values of a doubly exponential function in which the middle exponent is two.[1] Integer sequences with this squaring behavior include

F(m) = 2^{2^m}+1
MM(p) = 2^{2^p-1}-1
s_n = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor
where E ≈ 1.264084735305 is Vardi's constant.

More generally, if the nth value of an integer sequences is proportional to a double exponential function of n, Ionascu and Stanica call the sequence "almost doubly-exponential" and describe conditions under which it can be defined as the floor of a doubly-exponential sequence plus a constant.[2] Additional sequences of this type include

  • The prime numbers 2, 11, 1361, ... (sequence A051254 in OEIS)
a(n) = \left\lfloor A^{3^n}\right\rfloor
where A ≈ 1.306377883863 is Mills' constant.

[edit] Applications

[edit] Algorithmic complexity

In computational complexity theory, some algorithms take double-exponential time:

[edit] Number theory

Some number theoretical bounds are double exponential. Odd perfect numbers with n distinct prime factors are known to be at most

2^{4^n}

a result of Nielsen (2003).[5]

The largest known prime in the electronic era has grown roughly as a double exponential function of the year since Miller and Wheeler found a 79-digit prime on EDSAC1 in 1951.[6]

[edit] Theoretical biology

In population dynamics the growth of human population is sometimes supposed to be double exponential. Gurevich and Varfolomeyev[7] experimentally fit

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

where N(y) is the population in year y in millions.

[edit] Physics

In the Oscillator Toda model of self-pulsation, the logarithm of amplitude varies exponentially with time (for large amplitudes), thus the amplitude varies as double-exponential function of time.[8]

[edit] See also

[edit] References

  1. ^ Aho, A. V. & Sloane, N. J. A. (1973), “Some doubly exponential sequences”, Fibonacci Quarterly 11: 429–437, <http://www.research.att.com/~njas/doc/doubly.html> .
  2. ^ E. Ionascu and P. Stanica, "Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences". Acta Mathematica Universitatis Comenianae Vol. LXXIII, 1 (2004), pp. 75–87.
  3. ^ Deepak Kapur, Paliath Narendran, Double-exponential complexity of computing a complete set of AC-unifiers. Proceedings of the Seventh Symposium on Logic in Computer Science (1992), pp. 11–21.
  4. ^ Jan Johannsen and Martin Lange, CTL+ is complete for double exponential time.
  5. ^ Pace P. Nielsen, An Upper Bound for Odd Perfect Numbers. INTEGERS: The Electronic Journal of Combinatorial Number Theory Vol. 3 (2003).
  6. ^ J. C. P. Miller D. J. Wheeler, "Large Prime Numbers" Nature 168 (1951), p. 838. [1]
  7. ^ Varfolomeyev, SD & Gurevich, KG, "The hyperexponential growth of the human population on a macrohistorical scale." Journal of Theoretical Biology, 212(3) (2001), p. 371.
  8. ^ D.Kouznetsov; J.-F.Bisson, J.Li, K.Ueda (2007). "Self-pulsing laser as oscillator Toda: Approximation through elementary functions". Journal of Physics A 40: 1–18. doi:10.1088/1751-8113/40/9/016. 
Languages