Эффективное по времени и памяти вычисление дзета-функции Римана в модели Ко-Фридмана

В данной работе строится FP//LINSPACE алгоритмический аналог вещественной функции Римана для алгоритмических вещественных чисел , , с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга в модели Ко-Фридмана алгоритмических чисел и функций. Для построения алгоритмического аналога функции Римана предлагается алгоритм расчета двоично-рациональных приближений данной функции для вещественных , , с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга. Данный алгоритм строится на основе разложения в числовой ряд, который сходится для вещественных , , при этом показывается и используется в данном алгоритме линейная сходимость числового ряда. Предложенный алгоритм вычисления вещественной функции Римана включает использование алгоритмов вычисления вещественной функции и гипергеометрических рядов с полиномиальным временем и линейной памятью. Предложенный алгоритм (модифицированный некоторым образом для работы с комплексными числами) может использоваться для вычисления комплексной функции Римана для , (то есть также для ), с использованием полиномиального времени и линейной памяти по , где – точность вычислений. Модифицированный алгоритм также будет использовать полиномиальное время и линейную память по и экспоненциальное время и экспоненциальную память по .
In the present paper we construct FP//LINSPACE algorithmic analog of real Riemann function for FP//LINSPACE algorithmic real numbers , , with polynomial time and linear space on Turing machines in Ko-Friedman model of algorithmic numbers and functions. To construct algorithmic analog of real Riemann function , we consider an algorithm for the evaluation of dyadic rational approximations of the function for FP//LINSPACE algorithmic real numbers on Turing machine using polynomial time and linear space. The Algorithm is based on a series expansion which converges for real , it is shown and used in the algorithm that the series of the function converges linearly. The proposed algorithm of the evaluation of real Riemann function uses algorithms for the evaluation of real function and the evaluation of hypergeometric series using polynomial time and linear space. The algorithm from the present paper modified in some way to work with the complex numbers can be used to evaluate complex Riemann function for , (so, also for ), in polynomial time and linear space in wherein is a precision of computations. The modified algorithm will use polynomial time and linear space in and exponential time and exponential space in .