Отправить статью по E-mail Вычисление гипергеометрических рядов с квазилинейной временной и линейной ёмкостной сложностью
- Авторы: Яхонтов С.В.1
-
Учреждения:
- Санкт-Петербургский государственный университет, математико-механический факультет
- Выпуск: Том 5, № 3 (2011)
- Страницы: 149-156
- Раздел: Статьи
- Статья получена: 18.02.2020
- Статья опубликована: 15.09.2011
- URL: https://journals.eco-vector.com/1991-8615/article/view/20986
- ID: 20986
Цитировать
Полный текст
Аннотация
Проводится построение простого для практической реализации алгоритма со сложностью O(M(n)log(n)2) по времени и O(n) по памяти для вычисления гипергеометрических рядов с рациональными коэффициентами на машине Шёнхаге, где M(n) - сложность умножения целых чисел. Показывается, что данный алгоритм пригоден в практической информатике для построения конструктивных аналогов часто используемых констант математического анализа.
Об авторах
Сергей Викторович Яхонтов
Санкт-Петербургский государственный университет, математико-механический факультет
Email: sergey_home_mail@inbox.ru
(к.ф.-м.н.), доцент, каф. информатики; Санкт-Петербургский государственный университет, математико-механический факультет
Список литературы
- Schönhage A., Grotefeld A. F. W, Vetter E. Fast algorithms. A multitape Turing machine implementation. Mannheim, Germany: BI-Wissenschaftsverlag, 1994. 298 pp.
- 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.
- Cheng H., Gergel B., Kim E., Zima E. Space-efficient evaluation of hypergeometric series // SIGSAM Bull., 2005. Vol. 39, no. 2. Pp. 41-52.
- Yakhontov S. V. FLINSPACE constructive real numbers and functions (in Russian). Saarbrücken, Germany: Lambert Academic Publishing, 2010. 167 pp.
- Gourdon X., Sebah P. Binary splitting method: <http://numbers.computation.free.fr/Constants/Algorithms/splitting.ps>
- Ko K.-I Complexity theory of real functions. Progress in Theoretical Computer Science. Boston, MA: Birkhäuser Boston, Inc., 1991. 310 pp.
Дополнительные файлы
