58
$\begingroup$

I would like to know how are logarithms 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?

  • 2
    Implementation dependent.2011-09-01
  • 5
    For the uninitiated: `fyl2x()` computes a binary (base-2) logarithm.2011-09-01
  • 2
    This is almost identical to the question I asked some time ago: http://math.stackexchange.com/questions/14066/calculator-algorithms2011-09-01
  • 10
    It’s easy. To get the algorithm, just let let a dyslexic write “logarithm”.2011-09-02
  • 2
    @KonradRudolph Wow, I never noticed they were anagrams of eachother!2014-08-18
  • 2
    @KonradRudolph LOL. Of course, there is the one about why the dyslexic, agnostic, insomniac lay awake all night last night ....2014-10-06
  • 0
    [How does C compute sin() and other math functions?](https://stackoverflow.com/q/2284860/995714), [What algorithms do FPUs use to compute transcendental functions?](https://stackoverflow.com/q/13877303/995714)2018-08-14

3 Answers 3

33

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

  • 6
    [This book](http://perso.ens-lyon.fr/jean-michel.muller/SecondEdition.html) should also be of interest.2011-09-01
  • 1
    Thank you. I searched on Knuth's Art of computer programming, where he suggested another method.2011-09-01
  • 5
    ...and I might as well: *[Matters Computational](http://www.jjj.de/fxt/fxtbook.pdf)* has a nice section on elementary function computations, including the logarithm.2011-09-01
  • 1
    Both of your links are dead btw.2014-08-18
  • 1
    @Cruncher: Thanks! I will try to find alternatives...2014-08-19
  • 1
    @Aryabhata: The links in your post are no longer active. Regarding your statement "this pdf you can find by a google search of the title," what title are you referring to? I would like to search for whatever that is.2014-11-15
  • 1
    @stackoverflowuser2010: Yes, they aren't (see earlier comments). I haven't found the time to find new links, sorry :-(. The title of the question: "What algorithm is used by computers to calculate logarithms?". It worked when the question was posted, _three_ years ago...2014-11-17
  • 2
    @Aryabhata: If I google "What algorithm is used by computers to calculate logarithms", then the first answer shown is this StackExchange webpage, and the first answer is yours with the broken links. That is not very useful.2014-11-17
  • 1
    @stackoverflowuser2010: You are absolutely correct, and I agree completely. Unfortunately, the pdfs that I linked to earlier were very useful, and I have no way to replicate that information here. I haven't found any better links (still looking, though). Please remember that this answer is three years old, and link rot is expected over time.2014-11-18
  • 1
    @stackoverflowuser2010: I have updated the links for the two pdfs. Hopefully they won't get stale again.2014-11-18
  • 1
    @Aryabhata: Thank you for the updated links. I'm looking forward to reading the material.2014-11-21
  • 0
    @Aryabhata: unfortunately they're behind a paywall.. Perhaps it would make sense to quote some relevant parts here?2018-08-09
  • 0
    @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.2018-08-09
18

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.

  • 1
    In [QuickDraw GX](http://en.wikipedia.org/wiki/QuickDraw_GX), I used the CORDIC algorithm to compute trigonometric and inverse trigonometric functions as well as logarithms and exponentials on processors without FPUs.2011-09-01
  • 1
    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...2011-09-01
  • 1
    @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.2011-09-01
  • 1
    Right, one really has to do testing if you're implementing from the bottom up. At least the OP now knows there's a lot to pick from.2011-09-01
  • 4
    [A 1971 paper by J. S. Walther](http://www.jacques-laporte.org/Welther-Unified%20Algorithm.pdf) (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.2011-09-01
  • 0
    @oosterwal: cool. This explains why I saw the CORDIC algorithm on HP calculators.2011-09-01
  • 0
    @robjohn The main interest of Pade-Hermite approximant (computed for example from a continued fraction expansion) is that the convergence is much faster than Taylor series on the whole complex plane (not just the unit disk).2014-06-04
  • 0
    J.S. Walther link was broken. Here is one that works (05/2016): http://ece-research.unm.edu/pollard/classes/walther.pdf2016-05-25
12

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.

  • 2
    [Hastings's book](http://www.amazon.com/dp/0691079145) is an oldie-but-goodie. If the OP doesn't need that much accuracy, the approximations given there might be adequate.2011-09-01
  • 0
    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.2017-07-04