Calculation of hypergeometric series with quasi-linear time and linear space complexity

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

  1. Schönhage A., Grotefeld A. F. W, Vetter E. Fast algorithms. A multitape Turing machine implementation. Mannheim, Germany: BI-Wissenschaftsverlag, 1994. 298 pp.
  2. 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.
  3. Cheng H., Gergel B., Kim E., Zima E. Space-efficient evaluation of hypergeometric series // SIGSAM Bull., 2005. Vol. 39, no. 2. Pp. 41-52.
  4. Yakhontov S. V. FLINSPACE constructive real numbers and functions (in Russian). Saarbrücken, Germany: Lambert Academic Publishing, 2010. 167 pp.
  5. Gourdon X., Sebah P. Binary splitting method: <http://numbers.computation.free.fr/Constants/Algorithms/splitting.ps>
  6. Ko K.-I Complexity theory of real functions. Progress in Theoretical Computer Science. Boston, MA: Birkhäuser Boston, Inc., 1991. 310 pp.

Statistics

Views

Abstract - 17

PDF (Russian) - 0

Cited-By


Refbacks

  • There are currently no refbacks.

Copyright (c) 2011 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies