Geodesic
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/}
}
TY  - JOUR
AU  - S. V. Yakhontov
TI  - Time- and space-efficient evaluation of the real logarithmic function on Schonhage machine
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 101
EP  - 114
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_2_a10/
LA  - ru
ID  - PDM_2013_2_a10
ER  - 
%0 Journal Article
%A S. V. Yakhontov
%T Time- and space-efficient evaluation of the real logarithmic function on Schonhage machine
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 101-114
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_2_a10/
%G ru
%F 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/

[1] Yakhontov S. V., “Vychislenie gipergeometricheskikh ryadov s kvazilineinoi vremennoi i lineinoi emkostnoi slozhnostyu”, Vestnik Samarskogo gosudarstvennogo tekhnicheskogo universiteta. Ser. Fiziko-matematicheskie nauki, 2011, no. 3(17), 149–156

[2] Yakhontov S. V., “Effektivnoe po vremeni i po pamyati vychislenie eksponentsialnoi funktsii kompleksnogo argumenta na mashine Shënkhage”, Vestnik S.-Peterburg. un-ta. Ser. 10. Prikladnaya matematika. Informatika. Protsessy upravleniya, 2011, no. 4, 97–110

[3] Yakhontov S. V., Kosovskii N. K., Kosovskaya T. M., Effektivnye po vremeni i pamyati algoritmicheskie priblizheniya chisel i funktsii, Ucheb. posobie, SPb., 2012, 256 pp.

[4] Schonhage A., Grotefeld A. F. W, Vetter E., Fast algorithms. A multitape Turing machine implementation, Brockhaus AG, Leipzig, 1994, 298 pp.

[5] Ko K., Complexity theory of real functions, Birkhauser, Boston, 1991, 310 pp. | MR

[6] “17-ya Vsesoyuz. shkola po teorii informatsii i eë prilozheniyam”, Karatsuba E. A. "Bystroe vychislenie $\exp(x)$", Problemy peredachi informatsii, 26:3 (1990), 109

[7] Karatsuba E. A., “Bystrye vychisleniya transtsendentnykh funktsii”, Problemy peredachi informatsii, 27:4 (1991), 76–99 | MR | Zbl

[8] Karatsuba E. A., “Fast evaluation of hypergeometric function by FEE”, Proc. 3rd CMFT conference on computational methods and function theory (Nicosia, Cyprus, October 13–17, 1997), Ser. Approx. Decompos., 11, World Scientific, Singapore, 1999, 303–314 | MR | Zbl

[9] Haible B., 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), 338–350 | MR | Zbl

[10] Karatsuba E. A., “Bystroe vychislenie $\zeta(3)$”, Problemy peredachi informatsii, 29:1 (1993), 68–73 | MR | Zbl

[11] Karatsuba C. A., “Fast evaluation of Bessel functions”, Integral Transforms and Special Functions, 1:4 (1993), 269–276 | DOI | MR | Zbl

[12] Karatsuba E. A., “Bystroe vychislenie dzeta-funktsii Rimana $\zeta(s)$ dlya tselykh znachenii argumenta $s$”, Problemy peredachi informatsii, 31:4 (1995), 69–80 | MR | Zbl

[13] Karatsuba E. A., “Bystroe vychislenie dzeta-funktsii Gurvitsa i $L$-ryadov Dirikhle”, Problemy peredachi informatsii, 34:4 (1998), 62–75 | MR | Zbl

[14] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979, 536 pp. | MR

[15] Kosovskaya T. M., Kosovskii N. K., “Prinadlezhnost klassu $FP$ dvazhdy polinomialnykh paskalevidnykh funktsii nad podprogrammami iz $FP$”, Kompyuternye instrumenty v obrazovanii, 2010, no. 3, 3–7

[16] Fikhtengolts G. M., Kurs differentsialnogo i integralnogo ischisleniya, v. 2, Fizmatlit, M., 2003

[17] Karatsuba A. A., Ofman Yu. P., “Umnozhenie mnogoznachnykh chisel na avtomatakh”, Doklady AN SSSR, 145:2 (1962), 293–294

[18] Muller J.-M., Elementary functions. Algorithms and implementation, Birkhauser, Boston, 1997, 204 pp. | MR | Zbl