Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikl. Diskr. Mat., 2013, Number 2(20), Pages 101–114 (Mi pdm414)  

Computational Methods in Discrete Mathematics

Time- and space-efficient evaluation of the real logarithmic function on Schonhage machine

S. V. Yakhontov

Saint-Petersburg State University, Saint-Petersburg, Russia

Abstract: 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 hypergeometric 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.

Keywords: logarithmic function, algorithmic real functions, quasi-linear time complexity, linear space complexity.

Full text: PDF file (632 kB)
References: PDF file   HTML file
UDC: 510.25+510.52+519.688

Citation: S. V. Yakhontov, “Time- and space-efficient evaluation of the real logarithmic function on Schonhage machine”, Prikl. Diskr. Mat., 2013, no. 2(20), 101–114

Citation in format AMSBIB
\Bibitem{Yak13}
\by S.~V.~Yakhontov
\paper Time- and space-efficient evaluation of the real logarithmic function on Schonhage machine
\jour Prikl. Diskr. Mat.
\yr 2013
\issue 2(20)
\pages 101--114
\mathnet{http://mi.mathnet.ru/pdm414}


Linking options:
  • http://mi.mathnet.ru/eng/pdm414
  • http://mi.mathnet.ru/eng/pdm/y2013/i2/p101

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Number of views:
    This page:313
    Full text:124
    References:36
    First page:1

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021