This article is cited in 2 papers

Computer Science

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

S. V. Yakhontov

Dept. of Informatics, St. Petersburg State University, Mathematics and Mechanics Faculty, St. Petersburg

Abstract: A simple for practical implementation algorithm with the time complexity ${\mathsf O}(M(n)\log(n)^2)$ and space complexity ${\mathsf 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.

Keywords: constructive real numbers, hypergeometric series, quasi-linear time, linear space complexity.

UDC: 519.677

MSC: Primary 03F60; Secondary 68Q17

Original article submitted 01/II/2011
revision submitted – 24/VIII/2011

DOI: 10.14498/vsgtu924

Bibliographic databases:

• 
• 
•