В данной работе строится FP//LINSPACE алгоритмический аналог вещественной функции Римана для алгоритмических вещественных чисел
,
, с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга в модели Ко-Фридмана алгоритмических чисел и функций. Для построения алгоритмического аналога функции Римана
предлагается алгоритм расчета двоично-рациональных приближений данной функции для вещественных
,
, с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга. Данный алгоритм строится на основе разложения в числовой ряд, который сходится для вещественных
,
, при этом показывается и используется в данном алгоритме линейная сходимость числового ряда. Предложенный алгоритм вычисления вещественной функции Римана
включает использование алгоритмов вычисления вещественной функции
и гипергеометрических рядов с полиномиальным временем и линейной памятью. Предложенный алгоритм (модифицированный некоторым образом для работы с комплексными числами) может использоваться для вычисления комплексной функции Римана
для
,
(то есть также для
), с использованием полиномиального времени и линейной памяти по
, где
– точность вычислений. Модифицированный алгоритм также будет использовать полиномиальное время и линейную память по
и экспоненциальное время и экспоненциальную память по
.





В данной работе рассматриваются алгоритмические (вычислимые) вещественные числа и функции, которые представляются функциями Коши, вычислимыми на машине Тьюринга [1] (такая модель алгоритмических чисел и функций называется моделью Ко-Фридмана).
Основные результаты по теории алгоритмических чисел и функций и их вычислительной сложности находятся, например, в [1]; основные результаты по теории вычислительной сложности на машине Тьюринга находятся, например, в [2].
Известно, что вещественная функция Римана [3] является полиномиально вычислимой по времени для натуральных
[4, 5]; алгоритмы из [4, 5] требуют не менее чем
ячеек памяти для вычисления приближенных значений функции
с точностью
. Также имеется алгоритм вычисления гипергеометрических рядов с произвольной точностью с квази-линейным временем и линейной памятью [6], который применим к вычислению значения
. Временная и емкостная вычислительная сложность алгоритмов из [4, 5, 6] рассматривается в контексте битовой сложности; на машине Тьюринга алгоритмы из [4, 5] являются полиномиальными по времени и квази-линейными по памяти, а алгоритм из [6] является полиномиальным по вроемени и линейным по памяти.
В данной работе показывается, что вещественная функция Римана является полиномиально вычислимой по времени и линейно вычислимой по памяти (с помощью одного и того же алгоритма) на машине Тьюринга для вещественных
,
, в модели Ко-Фридмана. Для доказательства данного результата строится алгоритм вычисления вещественной функции Римана
с полиномиальным временем и линейной памятью на машине Тьюринга. Данный алгоритм основан на разложении функции Римана
в числовой ряд [7, 8] для комплексных
,
; в данном алгоритме используются алгоритмы из [9, 10, 11] вычисления вещественной функции
и гипергеометрических рядов с полиномиальным временем и линейной памятью. Для построения алгоритма вычисления функции Римана
используются алгоритм вычисления числовых рядов из [12] и прямой и обратный анализ ошибок округления в численных алгоритмах [9, 10, 11, 13].
Частично результат, изложенный в данной работе, представлялся на научной конференции «Научная дискуссия: вопросы математики, физики, химии, биологии» [14].
1.1 алгоритмические числа и функции
Функции Коши в модели Ко-Фридмана [1] – это функции, двоично-рационально сходящиеся к вещественным числам. Фукнция (здесь
– множество двоично-рациональных чисел) двоично-рационально сходится к вещественному числу
, если
для всех
; с помощью
обозначается множество всех функций, двоично-рационально сходящихся к числу
.
Definition 1. [1] Вещественное число называется
алгоритмическим вещественным число, если
содержит функцию
, вычислимую на машине Тьюринга.
Definition 2. [1] Вещественная функция , заданная на отрезке
, называется
алгоритмической вещественнойфункцией на отрезке
, если существует машина Тьюринга
с оракульной функцией такая, что для всех
и для всех
функция
, вычисляемая машиной
с оракульной функцией
, принадлежит
.
1.2 Вычислительная сложность алгоритмических функций
Definition 3. [1] Фукнция называется
вычислимой по времени вещественной функцией на отрезке
, если для всех алгоритмических вещественных чисел
функция
(
берется из определения
алгоритмических вещественных функций) является
вычислимой по времени.
Definition 4. [1] Функция называется
вычислимой по памяти вещественной функцией на отрезкеl
, если для всех алгоритмических вещественных чисел
функция
(
берется из определения
алгоритмических вещественных функций) является
вычислимой по памяти.
Входными данными функций и
является запись
(повторение данного символа
раз) в случае, когда функции вычисляются с точностью
.
С помощью FP//LINSPACE обозначается класс строковых функций, вычислимых за полиномиальное время и линейную память (с помощью одного и того же алгоритма) на машине Тьюринга. Полиномиально вычислимые по времени и линейно вычислимые по памяти алгоритмические вещественные числа и функции называются FP//LINSPACE алгоритмическими вещественными функциями. Множество FP//LINSPACE алгоритмических вещественных функций на отрезке обозначается с помощью FP//LINSPACE
.
1.3 Вычисление приближений вещественных функций
В данной работе используются следующие результаты из [9, 10, 11].
Для умножения и
с точностью
, где
и
– вещественные числа такие, что
и
для некоторого натурального числа
, достаточно вычислять
и
с точностью
для
, где
– линейная функция натуральных аргументов.
Для вычисления величины, обратной к с точностью
, где
– вещественное число такое, что
для некоторого натурального числа
, достаточно вычислять
с точностью
для
, где
– линейная функция натуральных аргументов.
Для вычисления функции с точностью
, где вещественные
и вещественное число
, достаточно вычислять
и
с точностью
для
, где
– линейная функция натуральных аргументов.
Можно показать, что для вычисления функции с точностью
, где вещественные
и вещественное
, достаточно вычислять
с точностью
для
, где
– линейная функция натуральных аргументов.
2 FP//LINSPACE вычисление функции
Рассмотрим числовой ряд [7, 8] фунции Римана , сходящийся для всех комплексных чисел
(исключая
для целых
):
(1)
Пусть
и
запишем ряд (1) следующим образом:
(2)
Пусть – натруальное число,
; пусть
и
– натуральное число такое, что
. Будем вычислять
по формуле (2) с точностью
для таких
, где
– натуральное число.
2.1 Вычисление
Так как
(3)
выполняютя соотношения
Следовательно
,
где – некторая константа (следует из соотношений, изложенных в параграфе 2.2.3).
Это означает, что для вычисления по формуле (2) с точностью
достаточно вычислять величины
и
с точностью
, где
(
– константа, зависящая от
).
Далее, для вычисления величины с точностью
воспользуемся алогитмом из [9, 10, 11] вычисления функции
с точностью
; при этом достаточно вычислять величину
до точности
для
, где
– линейная функция натуральных аргументов (
– некоторое натуральное число).
2.2 Вычисление
Будем вычислять функцию следующим образом:
1) вычисляем с точностью
;
2) вычисляем с точностью
;
3) вычисляем
,
где и
– приближенные значения величин
and
соответственно с точностью
; пусть
– точность вычисления величины
;
4) вычисляем
пусть – точность вычисления величины
.
Для вычисления величины с точностью
воспользуемся алгоритмом из [9, 10, 11] вычисления функции
с точностью
; для этого достаточно вычислять величину
с точностью
для
, где
– это линейная функция натуральных аргументов (
– натуральное число).
Следовательно, для вычисления величины с точностью
с помощью суммирования ряда величину
достаточно вычислять с точностью
, где
.
2.2.1 Вычисление
Запишем величину следующим образом:
Будем вычислять в цикле по
, на каждом шаге вычисляя
(при этом ), где
– приближенное значение величины
с точностью
,
– приближенное значение величины
с точностью
;
для всех натуральны
. Будем вычислять
с точностью
, отбрасывая все биты после точки, начиная с
-го бита.
Используя метод математической индукции по , покажем, что
для каждого
, если брать
.
База индукции: ; в этом случае, величина
, равнаяo
, вычисляется с точностью
. Индукционный рпереход: пусть
для
. В этом случае
(здесь используется оценка ). Следовательно, выполняется оценка
в частности, . Это означает, что достаточно брать
и
для вычисления
с точностью
. И, далее, для вычисления
с точностью
достаточно брать
где
– линейная функция натурального аргумента, так как
.
2.2.2 Вычисление
Будем вычислять в цикле по
. Так как
где и
, выполняется соотношение
Далее, из
следует
Следовательно, если взять и вычислять
и
с точностью
, то точность вычисления
будет
.

Найдем точность вычисления of используя следующие соотношения:
где
и
Так как
выполняется соотношение
Оценим сверху величину
Пусть – нечетное натуральное число и
; пусть
Так как , выполняются равенства
Следовательно,
и
из чего получаем
и
(те же самые соотношения выполняются в случае, когда – четное). Следовательно
Как результат, если взять , то
Это означает, что достаточно взять и
для вычисления
с точностью
.
3 Основной результат
Как результат, получаем, что для вычисления с точностью
для
достаточно выполнить следующие шаги:
1) вычислить с точностью
для
где
– линейная функция натуральных аргументов, и
2) использовать умножений двоично-рациональных чисел длины
, где
– линейная функция натуральных аргументов.
Следовательно выполняется следующая теорема.
Теорема 1. Вещественная функция Римана принадлежит классу FP//LINSPACE
для любого интервала
, где
,
,
и
– натуральное число,
.
Также выполняется следующая теорема (учитывая параграф 1.3).
Теорема 2. Вещественная функция Римана является экспоненциально вычислимой по времени и экспоненциально вычислимой по памяти по
для любого отрезка
, где
,
,
и
– натуральное число,
.
Рецензенты:
Косовский Н.К., д.ф.-м.н., профессор, зав. кафедрой информатики, математико-механический факультет, Санкт-Петербургский государственный университет (Министерство образования и науки Российской Федерации), г. Санкт-Петербург.
Ермаков С.М., д.ф.-м.н., профессор, зав. кафедрой статистического моделирования, математико-механический факультет, Санкт-Петербургский государственный университет (Министерство образования и науки Российской Федерации), г. Санкт-Петербург.
Библиографическая ссылка
Яхонтов С.В. ЭФФЕКТИВНОЕ ПО ВРЕМЕНИ И ПАМЯТИ ВЫЧИСЛЕНИЕ ДЗЕТА-ФУНКЦИИ РИМАНА В МОДЕЛИ КО-ФРИДМАНА // Современные проблемы науки и образования. – 2014. – № 6. ;URL: https://science-education.ru/ru/article/view?id=16788 (дата обращения: 19.02.2025).