A double exponential function is a
constant raised to the power of an
exponential function. The general formula is
(where ''a''>1 and ''b''>1), which grows much more quickly than an exponential function. For example, if ''a'' = ''b'' = 10:
*''f''(x) = 10
10x
*''f''(0) = 10
*''f''(1) = 10
10
*''f''(2) = 10
100 =
googol
*''f''(3) = 10
1000
*''f''(100) = 10
10100 =
googolplex.
Factorial
In mathematics, the factorial of a non-negative denoted is the Product (mathematics), product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times ...
s grow faster than exponential functions, but much more slowly than double exponential functions. However,
tetration and the
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...
grow faster. See
Big O notation for a comparison of the rate of growth of various functions.
The inverse of the double exponential function is the
double logarithm log(log(''x'')). The complex double exponential function is
entire, because it is the composition of two entire functions
and
.
Double exponential sequences
A sequence of positive integers (or real numbers) is said to have ''double exponential rate of growth'' if the function giving the th term of the sequence is bounded above and below by double exponential functions of .
Examples include
* The
Fermat number
In mathematics, a Fermat number, named after Pierre de Fermat (1601–1665), the first known to have studied them, is a natural number, positive integer of the form:F_ = 2^ + 1, where ''n'' is a non-negative integer. The first few Fermat numbers ...
s
* The harmonic primes: The primes ''p'', in which the sequence exceeds 0, 1, 2, 3, …The first few numbers, starting with 0, are 2, 5, 277, 5195977, ...
* The
Double Mersenne numbers
* The elements of
Sylvester's sequence where ''E'' ≈ 1.264084735305302 is
Vardi's constant .
* The number of
''k''-ary Boolean functions:
* The prime numbers 2, 11, 1361, ...
where ''A'' ≈ 1.306377883863 is
Mills' constant.
Aho and
Sloane observed that in several important
integer sequence
In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers.
An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...
s, each term is a constant plus the square of the previous term. They show that such sequences can be formed by rounding to the nearest integer the values of a double exponential function with middle exponent 2.
Ionaşcu and Stănică describe some more general sufficient conditions for a sequence to be the floor of a double exponential sequence plus a constant.
Applications
Algorithmic complexity
In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
,
2-EXPTIME is the class of decision problems solvable in double exponential time. It is equivalent to AEXPSPACE, the set of decision problems solvable by an
alternating Turing machine in exponential space, and is a superset of
EXPSPACE. An example of a problem in 2-EXPTIME that is not in EXPTIME is the problem of proving or disproving statements in
Presburger arithmetic.
In some other problems in the design and analysis of algorithms, double exponential sequences are used within the design of an algorithm rather than in its analysis. An example is
Chan's algorithm for computing
convex hulls, which performs a sequence of computations using test values ''h''
''i'' = 2
2''i'' (estimates for the eventual output size), taking time O(''n'' log ''h''
''i'') for each test value in the sequence. Because of the double exponential growth of these test values, the time for each computation in the sequence grows singly exponentially as a function of ''i'', and the total time is dominated by the time for the final step of the sequence. Thus, the overall time for the algorithm is O(''n'' log ''h'') where ''h'' is the actual output size.
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).
The maximal volume of a
polytope in a ''d''-dimensional
integer lattice
In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice (group), lattice in the Euclidean space whose lattice points are tuple, -tuples of integers. The two-dimensional integer lattice is also called the s ...
with ''k'' ≥ 1
interior lattice points is at most
:
a result of Pikhurko (2001).
The
largest known prime number 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.
Theoretical biology
In
population dynamics the growth of human population is sometimes supposed to be double exponential. Varfolomeyev and Gurevich experimentally fit
:
where ''N''(''y'') is the population in millions in year ''y''.
Physics
In the
Toda oscillator 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.
[.]
Dendritic
macromolecules have been observed to grow in a doubly-exponential fashion.
References
{{reflist, 2
Elementary special functions
Exponentials