78
$\begingroup$

I would like to know how logarithms are calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that logarithms are calculated directly from the hardware.

So the question is: what algorithm is used by computers to calculate logarithms?

$\endgroup$
7
  • 2
    $\begingroup$ Implementation dependent. $\endgroup$
    – Quixotic
    Sep 1, 2011 at 16:25
  • 9
    $\begingroup$ For the uninitiated: fyl2x() computes a binary (base-2) logarithm. $\endgroup$
    – J. M. ain't a mathematician
    Sep 1, 2011 at 16:27
  • 2
    $\begingroup$ This is almost identical to the question I asked some time ago: math.stackexchange.com/questions/14066/calculator-algorithms $\endgroup$
    – John Smith
    Sep 1, 2011 at 23:40
  • 13
    $\begingroup$ It’s easy. To get the algorithm, just let let a dyslexic write “logarithm”. $\endgroup$
    – Konrad Rudolph
    Sep 2, 2011 at 12:49
  • 2
    $\begingroup$ @KonradRudolph Wow, I never noticed they were anagrams of eachother! $\endgroup$
    – Cruncher
    Aug 18, 2014 at 13:28

3 Answers 3

Reset to default
38
$\begingroup$

It really depends on the CPU.

For intel IA64, apparently they use Taylor series combined with a table.

More info can be found here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.5177

and here: http://www.computer.org/csdl/proceedings/arith/1999/0116/00/01160004.pdf

$\endgroup$
5
  • 7
    $\begingroup$ This book should also be of interest. $\endgroup$
    – J. M. ain't a mathematician
    Sep 1, 2011 at 16:26
  • 1
    $\begingroup$ Thank you. I searched on Knuth's Art of computer programming, where he suggested another method. $\endgroup$
    – zar
    Sep 1, 2011 at 16:36
  • 5
    $\begingroup$ ...and I might as well: Matters Computational has a nice section on elementary function computations, including the logarithm. $\endgroup$
    – J. M. ain't a mathematician
    Sep 1, 2011 at 18:09
  • $\begingroup$ @Aryabhata: unfortunately they're behind a paywall.. Perhaps it would make sense to quote some relevant parts here? $\endgroup$
    – naught101
    Aug 9, 2018 at 8:12
  • $\begingroup$ @naught101: The citeseer link seems to work (perhaps it is my work network which has access though). I can't access the second link too. $\endgroup$
    – Aryabhata
    Aug 9, 2018 at 21:07
23
$\begingroup$

All methods I have seen reduce first by dividing by the power of $2$ in the exponent and adding that exponent times $\ln(2)$ to the result. From there, the two most common methods I have seen are Taylor series for $\ln(1+x)$ and a variant of the CORDIC algorithm.

J. M. also brings up Padé approximants which I have seen used in some calculator implementations.

$\endgroup$
8
  • 1
    $\begingroup$ In QuickDraw GX, I used the CORDIC algorithm to compute trigonometric and inverse trigonometric functions as well as logarithms and exponentials on processors without FPUs. $\endgroup$
    – robjohn ♦
    Sep 1, 2011 at 18:07
  • 1
    $\begingroup$ I've seen at least one system use a Padé approximant instead of a Maclaurin series, but yes, I believe almost all implementations exploit $\log(ab)=\log\,a+\log\,b$ for range reduction... $\endgroup$
    – J. M. ain't a mathematician
    Sep 1, 2011 at 18:08
  • 2
    $\begingroup$ @J. M.: Padé approximations can be better than Maclaurin series for certain functions. However, usually, the number of terms in the numerator and denominator are about the same as the number of terms in an equivalent Maclaurin series. Then there is an extra division, which can be expensive on some processors. I generally avoided them, but it is definitely worth mentioning them. Thanks. $\endgroup$
    – robjohn ♦
    Sep 1, 2011 at 18:14
  • 5
    $\begingroup$ A 1971 paper by J. S. Walther (PDF) describes a unified CORDIC algorithm that can be used for multiplication, division, sin, cos, tan, arctan, sinh, cosh, tanh, arctanh, ln, exp and square root. $\endgroup$
    – oosterwal
    Sep 1, 2011 at 20:11
  • 2
    $\begingroup$ J.S. Walther link was broken. Here is one that works (05/2016): ece-research.unm.edu/pollard/classes/walther.pdf $\endgroup$
    – Paul Chernoch
    May 25, 2016 at 19:51
15
$\begingroup$

Read the docs and the source of the cephes library for instance. Try also these books:

See also https://stackoverflow.com/questions/2169641/where-to-find-algorithms-for-standard-math-functions.

$\endgroup$
2
  • 2
    $\begingroup$ Hastings's book is an oldie-but-goodie. If the OP doesn't need that much accuracy, the approximations given there might be adequate. $\endgroup$
    – J. M. ain't a mathematician
    Sep 1, 2011 at 18:32
  • $\begingroup$ I found a flaw in Hastings' polynomial approximation for Log. It has a discontinuity at the endpoint of the interval. If you are doing something that involves numerical differentiation, BAD NEWS. Before Hastings' 1955 book, there was a 1953 RAND report. He had been working on this problem since about 1948, maybe longer. $\endgroup$
    – richard1941
    Jul 4, 2017 at 8:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.