Thumbnail
Access Restriction
Subscribed

Author Brent, Richard P.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1976
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Let $ƒ(\textit{x})$ be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let $\textit{M}(\textit{n})$ be the number of single-precision operations required to multiply $\textit{n}-bit$ integers. It is shown that $ƒ(\textit{x})$ can be evaluated, with relative error $\textit{&Ogr;}(2-\textit{n}),$ in $\textit{&Ogr;}(\textit{M}(\textit{n})log$ $(\textit{n}))$ operations as $\textit{n}$ → ∞, for any floating-point number $\textit{x}$ (with an $\textit{n}-bit$ fraction) in a suitable finite interval. From the Schönhage-Strassen bound on $\textit{M}(\textit{n}),$ it follows that an $\textit{n}-bit$ approximation to $ƒ(\textit{x})$ may be evaluated in $\textit{&Ogr;}(\textit{n}$ $log2(\textit{n})$ log $log(\textit{n}))$ operations. Special cases include the evaluation of constants such as π, $\textit{e},$ and $\textit{e}π.$ The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric mean iteration and ascending Landen transformations.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1976-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 23
Issue Number 2
Page Count 10
Starting Page 242
Ending Page 251


Open content in new tab

   Open content in new tab
Source: ACM Digital Library