Where to find algorithms for standard math functio

Question

I'm looking to submit a patch to the D programming language standard library that will allow much of std.math to be evaluated at compile time using the compile-time function evaluation facilities of the language. Compile-time function evaluation has several limitations, the most important ones being:

1. You can't use assembly language.
2. You can't call C code or code for which the source is otherwise unavailable.

Several std.math functions violate these and compile-time versions need to be written. Where can I get information on good algorithms for computing things such as logarithms, exponents, powers, and trig functions? I prefer just high level descriptions of algorithms to actual code, for two reasons:

1. To avoid legal ambiguity and the need to make my code look "different enough" from the source to make sure I own the copyright.

2. I want simple, portable algorithms. I don't care about micro-optimization as long as they're at least asymptotically efficient.

Edit: D's compile time function evaluation model allows floating point results computed at compile time to differ from those computed at runtime anyhow, so I don't care if my compile-time algorithms don't give exactly the same result as the runtime version as long as they aren't less accurate to a practically significant extent.

Answer 1

Jean-Michel Muller's book is an excellent recommendation, as is Hart.

Is it actually necessary for you to own the copyright? It's usually a bad idea to get into the business of writing math library functions if you can avoid it (and I say that as someone who does so professionally). I don't know whether or not D can take in BSD-licenced code, but there are several good open-source implementations that may prove helpful. You may want to look at Sun's FDLIBM, for example. Stephen Moshier's Cephes would also be a possibility, though its licensing situation is a little bit odd, but I believe that he's been willing to let people redistribute his code under other licenses in the past.

On a side-note, unless you're supporting arbitrary-precision floating-point (I don't think that D does), there isn't usually a notion of "asymptotic efficiency" for libm functions.

Answer 2

several sources, including:

Abramowitz and Stegun, "Handbook of Mathematical Functions" (available online!)

Hart, "Computer Approximations" (out of print but good)

also see the several other SO questions about trigonometry, including "How do Trigonometric Functions Work?" and "Trigonometric Functions on Embedded Systems".