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 , 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
- The Fermat numbers
- The elements of Sylvester's sequence (sequence A000058 in OEIS)
-
- 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
-
- where A ≈ 1.306377883863 is Mills' constant.
[edit] Applications
[edit] Algorithmic complexity
In computational complexity theory, some algorithms take double-exponential time:
- Decision procedures for Presburger arithmetic
- Finding a complete set of associative-commutative unifiers [3]
- Satisfying CTL+ (which is, in fact, 2-EXPTIME-complete) [4]
[edit] Number theory
Some number theoretical bounds are double exponential. Odd perfect numbers with n distinct prime factors are known to be at most
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
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
- ^ 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>.
- ^ 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.
- ^ 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.
- ^ Jan Johannsen and Martin Lange, CTL+ is complete for double exponential time.
- ^ Pace P. Nielsen, An Upper Bound for Odd Perfect Numbers. INTEGERS: The Electronic Journal of Combinatorial Number Theory Vol. 3 (2003).
- ^ J. C. P. Miller D. J. Wheeler, "Large Prime Numbers" Nature 168 (1951), p. 838. [1]
- ^ Varfolomeyev, SD & Gurevich, KG, "The hyperexponential growth of the human population on a macrohistorical scale." Journal of Theoretical Biology, 212(3) (2001), p. 371.
- ^ 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: .