Email this article Calculation of hypergeometric series with quasi-linear time and linear space complexity
- Authors: Yakhontov S.V1
-
Affiliations:
- St. Petersburg State University, Mathematics and Mechanics Faculty
- Issue: Vol 5, No 3 (2011)
- Pages: 149-156
- Section: Articles
- URL: https://journal-vniispk.ru/1991-8615/article/view/20986
- ID: 20986
Cite item
Full Text
Abstract
A simple for practical implementation algorithm with the time complexity O(M(n)log(n)2) and space complexity O(n) for the evaluation of hypergeometric series with rational coefficients on the Schönhage machine is constructed (here M(n) is the complexity of integer multiplication). It is shown that this algorithm is suitable in practical informatics for constructive analogues of often used constants of analysis.
About the authors
Sergey V Yakhontov
St. Petersburg State University, Mathematics and Mechanics Faculty
Email: sergey_home_mail@inbox.ru
(к.ф.-м.н.), доцент, каф. информатики; Санкт-Петербургский государственный университет, математико-механический факультет; St. Petersburg State University, Mathematics and Mechanics Faculty
References
- Schönhage A., Grotefeld A. F. W, Vetter E. Fast algorithms. A multitape Turing machine implementation. Mannheim, Germany: BI-Wissenschaftsverlag, 1994. 298 pp.
- Haible B., Papanikolaou T. Fast multiprecision evaluation of series of rational numbers / In: Algorithmic number theory: Proceedings of 3rd international symposium (Portland, OR, 1998) / Lect. Notes Comput. Sci., 1423. Berlin: Springer, 1998. Pp. 338-350.
- Cheng H., Gergel B., Kim E., Zima E. Space-efficient evaluation of hypergeometric series // SIGSAM Bull., 2005. Vol. 39, no. 2. Pp. 41-52.
- Yakhontov S. V. FLINSPACE constructive real numbers and functions (in Russian). Saarbrücken, Germany: Lambert Academic Publishing, 2010. 167 pp.
- Gourdon X., Sebah P. Binary splitting method: <http://numbers.computation.free.fr/Constants/Algorithms/splitting.ps>
- Ko K.-I Complexity theory of real functions. Progress in Theoretical Computer Science. Boston, MA: Birkhäuser Boston, Inc., 1991. 310 pp.
Supplementary files
