Time- and space-efficient evaluation of the real logarithmic function on Schonhage machine
Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 101-114
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{PDM_2013_2_a10,
author = {S. V. Yakhontov},
title = {Time- and space-efficient evaluation of the real logarithmic function on {Schonhage} machine},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {101--114},
publisher = {mathdoc},
number = {2},
year = {2013},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDM_2013_2_a10/}
}
S. V. Yakhontov. Time- and space-efficient evaluation of the real logarithmic function on Schonhage machine. Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 101-114. http://geodesic.mathdoc.fr/item/PDM_2013_2_a10/