Двойная экспоненциальная функция

Двойная экспоненциальная функция (красная кривая) по сравнению с одинарной экспоненциальной функцией (синяя кривая).

Двойная экспоненциальная функция является постоянной , возведенным в силу с экспоненциальной функцией . Общая формула (где a > 1 и b > 1) растет намного быстрее, чем экспоненциальная функция. Например, если a = b = 10:${\ Displaystyle е (х) = а ^ {Ь ^ {х}} = а ^ {(Ь ^ {х})}}$

• f (0) = 10
• f (1) = 10 ¹⁰
• f (2) = 10 ¹⁰⁰ = гугол
• f (3) = 10 ¹⁰⁰⁰
• f (100) = 10 ^{10 100} = гуголплекс .

Факториалы растут быстрее экспоненциальных функций, но намного медленнее, чем дважды экспоненциальные функции. Однако тетрация и функция Аккермана растут быстрее. См. Обозначение Big O для сравнения скорости роста различных функций.

Обратным к двойной экспоненциальной функции является двойной логарифм ln (ln ( x )).

Двойные экспоненциальные последовательности [ править ]

Ахо и Слоан заметили, что в нескольких важных целочисленных последовательностях каждый член является константой плюс квадрат предыдущего члена. Они показывают, что такие последовательности могут быть сформированы округлением до ближайшего целого числа значений дважды экспоненциальной функции, в которой средний показатель степени равен двум. ^[1] Целочисленные последовательности с таким поведением возведения в квадрат включают

• Эти числа Ферма

${\ Displaystyle F (м) = 2 ^ {2 ^ {m}} + 1}$

• Гармонические простые числа: простые числа p, в которых последовательность 1/2 + 1/3 + 1/5 + 1/7 + ... + 1 / p превышает 0, 1, 2, 3, ...

Первые несколько чисел, начинающиеся с 0, это 2, 5, 277, 5195977, ... (последовательность A016088 в OEIS ).

• В число Мерсенна Double

${\ displaystyle MM (p) = 2 ^ {2 ^ {p} -1} -1}$

• Элементы последовательности Сильвестра (последовательность A000058 в OEIS )

${\displaystyle s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor }$

где E ≈ 1,264084735305302 - константа Варди (последовательность A076393 в OEIS ).

• Количество k -арных булевых функций :

${\displaystyle 2^{2^{k}}}$

В более общем смысле, если n- е значение целочисленной последовательности пропорционально двойной экспоненциальной функции от n , Ионашку и Станика называют последовательность «почти дважды экспоненциальной» и описывают условия, при которых она может быть определена как нижняя граница дважды экспоненциальной последовательность плюс константа. ^[2] Дополнительные последовательности этого типа включают

• Простые числа 2, 11, 1361, ... (последовательность A051254 в OEIS )

${\displaystyle a(n)=\left\lfloor A^{3^{n}}\right\rfloor }$

где A ≈ 1.306377883863 - постоянная Миллса .

Приложения [ править ]

Алгоритмическая сложность [ править ]

В теории сложности вычислений некоторые алгоритмы занимают дважды экспоненциальное время:

• Каждая процедура принятия решения для арифметики Пресбургера доказуемо требует как минимум дважды экспоненциального времени ^[3]
• Вычисление базиса Грёбнера над полем. В худшем случае базис Грёбнера может иметь количество элементов, которое является дважды экспоненциальным по количеству переменных. С другой стороны, сложность алгоритмов на основе базиса Грёбнера в наихудшем случае является дважды экспоненциальной по количеству переменных, а также по размеру входа. ^[4]
• Нахождение полного набора ассоциативно-коммутативных унификаторов ^[5]
• Удовлетворение CTL ⁺ (что, по сути, является полным 2-EXPTIME ) ^[6]
• Исключение кванторов на вещественных замкнутых полях занимает дважды экспоненциальное время (см. Цилиндрическое алгебраическое разложение ).
• Вычисление дополнения к регулярному выражению ^[7]

В некоторых других задачах разработки и анализа алгоритмов дважды экспоненциальные последовательности используются при разработке алгоритма, а не при его анализе. Примером может служить алгоритм Чана для вычисления выпуклой оболочки , который выполняет последовательность вычислений с использованием тестовых значений h _i  = 2 ^{2 i} (оценки конечного размера выходных данных), занимая время O ( n  log  h _i ) для каждого тестового значения в последовательности . Из-за двойного экспоненциального роста этих тестовых значений время для каждого вычисления в последовательности растет однократно экспоненциально как функция от i, а общее время преобладает над временем последнего шага последовательности. Таким образом, общее время для алгоритма составляет O ( n  log  h ), где h - фактический размер вывода. ^[8]

Теория чисел [ править ]

Некоторые теоретические оценки числа являются двойной экспоненциальной. Известно, что нечетные совершенные числа с n различными простыми множителями не более

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

результат Nielsen (2003). ^[9] Максимальный объем d -решеточного многогранника с k ≥ 1 внутренними точками решетки не превосходит

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

результат Пихурко. ^[10]

Самый крупное известное простое число в электронной эре выросло примерно как двойная экспоненциальную функцию года , так как Миллер и Wheeler нашли 79-значное простое число на EDSAC 1 в 1951 году ^[11]

Теоретическая биология [ править ]

В динамике населения иногда предполагается, что рост численности населения происходит в два раза экспоненциально. Варфоломеев и Гуревич ^[12] экспериментально подходят

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

где N ( y ) - численность населения в миллионах в год y .

Физика [ править ]

В гетеродине Toda модели самостоятельной пульсации , логарифм амплитуды экспоненциально меняется со временем (для больших амплитуд), таким образом , амплитуда изменяется как двойной экспоненциальная функция времени. ^[13]

Было обнаружено, что дендритные макромолекулы растут дважды экспоненциально. ^[14]

Ссылки [ править ]