In the present paper, an algorithm FLE is constructed for the fast evaluation of the real logarithmic function ln(1 + x) on interval [2 -5,1 — 2 -5) on Schonhage machine. An upper bound of the time and space complexity of this algorithm is given. The algorithm FLE is based on Taylor series expansion and is similar to the algorithm for the fast evaluation of the exponential function FEE. A modified binary splitting algorithm ModifBinSplit for hyper-geometric series is constructed to use in algorithm FLE. It is proved that the time and space complexity of algorithms ModifBinSplit and FLE are quasi-linear and linear respectively if they are implemented on Schonhage machine; therefore it is proved that these algorithms are in class Sch(FQLIN-TIME//LIN-SPACE). Multiple interval reduction is used to compute the logarithmic function on an arbitrary interval.
Download file
Counter downloads: 70
- Title Timeand space-efficient evaluation of the real logarithmic function on Schonhage machine
- Headline Timeand space-efficient evaluation of the real logarithmic function on Schonhage machine
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(20)
- Date:
- DOI
Keywords
логарифмическая функция, алгоритмические вещественные функции, квазилинейная временная сложность, линейная ёмкостная сложность, logarithmic function, algorithmic real functions, quasi-linear time complexity, linear space complexityAuthors
References
Muller J.-M. Elementary functions. Algorithms and implementation. Boston: Birkhauser, 1997. 204 p.
Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР. 1962. Т. 145. №2. С. 293-294.
Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. М.: Физмат-лит, 2003. Т. 2.
Косовская Т. М., Косовский Н. К. Принадлежность классу FP дважды полиномиальных паскалевидных функций над подпрограммами из FP // Компьютерные инструменты в образовании. 2010. №3. С. 3-7.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536c.
Карацуба Е. А. Быстрое вычисление дзета-функции Римана Z(s) для целых значений аргумента s // Проблемы передачи информации. 1995. Т. 31. No. 4. С. 69-80.
Карацуба Е. А. Быстрое вычисление дзета-функции Гурвица и L-рядов Дирихле // Проблемы передачи информации. 1998. Т. 34. №4. С. 342-353.
Карацуба Е. А. Быстрое вычисление Z(3) // Проблемы передачи информации. 1993. Т. 29. №1. С. 68-73.
Karatsuba C. А. Fast evaluation of Bessel functions // Integral Transforms and Special Functions. 1993. V. 1. No. 4. P. 269-276.
Haible B. and Papanikolaou T. Fast multiple-presicion evaluation of series of rational numbers // Proc. of the Third Intern. Symposium on Algorithmic Number Theory, Portland, Oregon, USA. June 21-25, 1998. P. 338-350.
Карацуба Е. А. Fast evaluation of hypergeometric function by FEE // Proc. 3rd CMFT conference on computational methods and function theory, Nicosia, Cyprus, October 13-17, 1997. Singapore: World Scientific, 1999. Ser. Approx. Decompos. V. 11. P. 303-314.
Карацуба Е. А. Быстрые вычисления трансцендентных функций // Проблемы передачи информации. 1991. Т. 27. Вып. 4. С. 76-99.
Schonhage A., Grotefeld A. F. W, and Vetter E. Fast algorithms. A multitape Turing machine implementation. Leipzig: Brockhaus AG, 1994. 298 p.
Ko K. Complexity theory of real functions. Boston: Birkhauser, 1991. 310 p.
Карацуба Е. А. Быстрое вычисление exp(x) // 17-я Всесоюз. школа по теории информации и её приложениям. Проблемы передачи информации. 1990. Т. 26. №3. С. 109.
Яхонтов С. В., Косовский Н. К., Косовская Т. М. Эффективные по времени и памяти алгоритмические приближения чисел и функций: учеб. пособие. СПб., 2012. 256с.
Яхонтов С. В. Эффективное по времени и по памяти вычисление экспоненциальной функции комплексного аргумента на машине Шёнхаге // Вестник С.-Петербург. унта. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2011. Вып. 4. С.97-110.
Яхонтов С. В. Вычисление гипергеометрических рядов с квазилинейной временной и линейной емкостной сложностью // Вестник Самарского государственного технического университета. Сер. Физико-математические науки. 2011. Вып. 2 (17). С. 239-249.
Timeand space-efficient evaluation of the real logarithmic function on Schonhage machine | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 2(20).
Download full-text version
Download fileCounter downloads: 192