HomeIssuesFP//LINSPACE evaluation of real Lambert W-function Wo

FP//LINSPACE evaluation of real Lambert W-function Wo | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 3 (25).

In the paper, we construct FP//LINSPACE algorithmic analog of real Lambert W-function W 0(x) on segment [-(re) -1, (re) -1] of FP//LINSPACE algorithmic real numbers, where r is a rational number, r > 4/3 (any such rational number is suitable). To construct algorithmic analog of real Lambert W-function W 0(x), we consider algorithm WLE for the evaluation of dyadic rational approximations of the function on segment [-(re) -1, (re) -1] on Turing machine using polynomial time and linear space. Algorithm WLE is based on the Taylor series expansion of the function; it is shown that the Taylor series of real Lambert W-function W 0(x) on segment [-(re) -1, (re) -1] converges linearly. This fact is used in the algorithm.
Download file
Counter downloads: 71
  • Title FP//LINSPACE evaluation of real Lambert W-function Wo
  • Headline FP//LINSPACE evaluation of real Lambert W-function Wo
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3 (25)
  • Date:
  • DOI
Keywords
вещественная W-функция Ламберта W 0, алгоритмические вещественные функции, машина Тьюринга, полиномиальная временная сложность, линейная емкостная сложность, real Lambert W-function W 0, algorithmic real functions, Turing machine, polynomial time complexity, linear space complexity
Authors
References
Haible B. and Papanikolaou T. Fast multiprecision evaluation of series of rational numbers // Proc. Third Intern. Symposium on Algorithmic Number Theory, Portland, Orgeon, USA, June 21-25, 1998. P. 338-350.
Карацуба Е. А. Быстрые вычисления трансцендентных функций // Проблемы передачи информации. 1991. Т. 27. Вып. 4. С. 76-99.
DuD. and Ko K. Theory of Computational Complexity. N.Y.: John Wiley & Sons, 2000. 491 p.
Brent R. P. Fast multiple-precision evaluation of elementary functions // J. ACM. 1976. V. 23. No. 2. P. 242-251.
Ko K. Complexity Theory of Real Functions. Boston: Birkhauser, 1991. 310 p.
Яхонтов С. В., Косовский Н. К., Косовская Т. М. Эффективные по времени и памяти алгоритмические приближения чисел и функций. Учеб. пособие. СПб.: Изд-во СПбГУ, 2012. 256с.
Дубинов А. Е., Дубинова И. Д., Сайков С. К. W-функция Ламберта и ее применение в математических задачах физики. Саров: Изд-во ФГУП «РФЯЦ-ВНИИЭФ», 2006. 160 с.
Mezzarobba M. A note on the space complexity of fast D-finite function evaluation // Computer Algebra in Scientific Comput. 2012. V. 7442. P. 212-223.
Старицын М. А., Яхонтов С. В. Эффективное по времени и памяти вычисление W-функции Ламберта // Четвертая Всерос. науч. конф. по проблемам информатики СПИСОК-14. СПб., 2014 (в печати).
Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. Т. 2. М.: Физ-матлит, 2003. 680 с.
FP//LINSPACE evaluation of real Lambert W-function Wo | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 3 (25).
FP//LINSPACE evaluation of real Lambert W-function Wo | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 3 (25).
Download full-text version
Counter downloads: 167