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.

Keywords

• constructive real numbers
• hypergeometric series
• quasi-linear time
• linear space complexity