二重指数関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動
単一の指数関数(青い曲線)と比較した二重指数関数(赤い曲線)。

二重指数関数(にじゅうしすうかんすう、: double exponential function)とは、指数関数の肩に指数関数を持つ関数である。一般形は 。 指数関数と同様に、二重指数関数型積分公式など、応用上はネイピア数を底に取ったものがよく使われる。

指数の底が a > 1, b > 1 を満たすなら、二重指数関数は通常の指数関数よりも速く大きくなる。 また二重指数関数は階乗より急速に増大する。階乗は通常の(一重の)指数関数よりも速く増大するため、充分大きい x について以下の関係が成り立つ(e はネイピア数):

二重指数関数に比べて速く増大する関数として、例えばテトレーションアッカーマン関数がよく知られている(その他さまざまな関数の増加率ついては例えばランダウの記号を参照のこと)。

二重指数関数 逆関数は、二重対数 である。

二重指数列[編集]

正の整数(または実数)の数列で、数列のn番目の項を与える関数がnの二重指数関数で上下を押さえられるものを、二重指数関数的に成長する数列という。

  • 調和素数:1/2 + 1/3 + 1/5 + 1/7 + ... + 1 / pが0、1、2、3、..を超える素数p 0で始まる最初のいくつかの番号は、2、5、277、5195977、...(A016088)である。
  • 二重メルセンヌ数
  • シルベスター数列の要素(A000058
なお、E ≈ 1.264084735305302 はヴァルディの定数A076393)である
  • k-aryブール関数:
なお、A ≈ 1.306377883863はミルズの定数英語版である。

アルフレッド・エイホニール・スローンは、いくつかの重要な整数列で、各項が定数に前の項の2乗を加えたものであることを観察した。それらは、そのような数列が、中間の指数2を持つ二重指数関数の値を最も近い整数に丸めることによって形成できることを示している[1] IonaşcuとStănicăは、数列が二重指数列と定数のフロアになるためのより一般的な十分条件について説明している[2]

微分・積分[編集]

自然二重指数関数[編集]

微分

積分

テイラー展開[編集]

応用[編集]

複雑なアルゴリズム[編集]

In computational complexity theory, some algorithms take doubly exponential time:

  • Each decision procedure for Presburger arithmetic provably requires at least doubly exponential time
  • Computing a Gröbner basis over a field. In the worst case, a Gröbner basis may have a number of elements which is doubly exponential in the number of variables. On the other hand, the worst-case complexity of Gröbner basis algorithms is doubly exponential in the number of variables as well as in the entry size.
  • Finding a complete set of associative-commutative unifiers [3]
  • Satisfying CTL+ (which is, in fact, 2-EXPTIME-complete) [4]
  • Quantifier elimination on real closed fields takes doubly exponential time (see Cylindrical algebraic decomposition).
  • Calculating the complement of a regular expression [5]

In some other problems in the design and analysis of algorithms, doubly 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 hi = 22i (estimates for the eventual output size), taking time O(n log hi) 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.[6]

数論[編集]

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).[7] The maximal volume of a d-lattice polytope with k ≥ 1 interior lattice points is at most

a result of Pikhurko.[8]

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.[9]

理論生物学[編集]

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

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

物理学[編集]

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

Dendritic macromolecules have been observed to grow in a doubly-exponential fashion.[12]

関連項目[編集]

参考文献[編集]

 

  1. ^ Aho, A. V.; Sloane, N. J. A. (1973), “Some doubly exponential sequences”, Fibonacci Quarterly 11: 429–437, http://neilsloane.com/doc/doubly.html .
  2. ^ Ionaşcu, Eugen-Julien; Stănică, Pantelimon (2004), “Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences”, Acta Mathematica Universitatis Comenianae LXXIII (1): 75–87, http://faculty.nps.edu/pstanica/research/AMUC04.pdf .
  3. ^ Kapur, Deepak; Narendran, Paliath (1992), “Double-exponential complexity of computing a complete set of AC-unifiers”, Proc. 7th IEEE Symp. Logic in Computer Science (LICS 1992), pp. 11–21, doi:10.1109/LICS.1992.185515, ISBN 0-8186-2735-2, http://citeseer.ist.psu.edu/337363.html .
  4. ^ Johannsen, Jan; Lange, Martin (2003), “CTL+ is complete for double exponential time”, in Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim et al., Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Lecture Notes in Computer Science, 2719, Springer-Verlag, pp. 767–775, doi:10.1007/3-540-45061-0_60, ISBN 978-3-540-40493-4, オリジナルの2007-09-30時点におけるアーカイブ。, https://web.archive.org/web/20070930220755/http://www.tcs.informatik.uni-muenchen.de/~mlange/papers/icalp03.pdf 2006年12月22日閲覧。 .
  5. ^ Gruber, Hermann; Holzer, Markus (2008). “Finite Automata, Digraph Connectivity, and Regular Expression Size”. Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). 5126. pp. 39–50. doi:10.1007/978-3-540-70583-3_4. http://www.hermann-gruber.com/data/icalp08.pdf 
  6. ^ Chan, T. M. (1996), “Optimal output-sensitive convex hull algorithms in two and three dimensions”, Discrete and Computational Geometry 16 (4): 361–368, doi:10.1007/BF02712873, MR1414961 
  7. ^ Nielsen, Pace P. (2003), “An upper bound for odd perfect numbers”, INTEGERS: The Electronic Journal of Combinatorial Number Theory 3: A14, http://www.integers-ejcnt.org/vol3.html .
  8. ^ Pikhurko, Oleg (2001), “Lattice points in lattice polytopes”, Mathematika 48: 15–24, arXiv:math/0008028, Bibcode2000math......8028P, doi:10.1112/s0025579300014339 
  9. ^ Miller, J. C. P.; Wheeler, D. J. (1951), “Large prime numbers”, Nature 168 (4280): 838, Bibcode1951Natur.168..838M, doi:10.1038/168838b0 .
  10. ^ Varfolomeyev, S. D.; Gurevich, K. G. (2001), “The hyperexponential growth of the human population on a macrohistorical scale”, Journal of Theoretical Biology 212 (3): 367–372, doi:10.1006/jtbi.2001.2384, PMID 11829357 .
  11. ^ Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), “Self-pulsing laser as oscillator Toda: Approximation through elementary functions”, Journal of Physics A 40 (9): 1–18, Bibcode2007JPhA...40.2107K, doi:10.1088/1751-8113/40/9/016, http://www.iop.org/EJ/abstract/-search=15823442.1/1751-8121/40/9/016 .
  12. ^ Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). “Double Exponential Dendrimer Growth”. Journal of the American Chemical Society 117 (8): 2159–2165. doi:10.1021/ja00113a005.