
Boost : 
From: John Maddock (john_at_[hidden])
Date: 20070425 12:28:21
John Phillips wrote:
>> • What is your evaluation of the implementation?
>
> Quite good, though I have a few nits to pick.
> Many of the special functions are implemented as rational
> approximations. I'm curious whether polynomial approximations were
> also tested. I know that in most cases it takes a higher degree
> polynomial approximation to reach similar accuracy, so the total
> operation count
> can benefit from rational approximations, however, not all operations
> are created equal. In most common modern architectures a divide takes
> about 10 times as long as a multiply or add. So, it may not be a
> savings
> to replace 5 multiply/adds with 1 divide. Other factors such as
> processor pipelining make this a difficult question to answer without
> timing tests, so testing is needed to find the best mix.
I admit that so far I've paid very little attention to speed: other than to
try and make sure it's not actually awful ;)
There's a lot of scope for optimising both the rational and polynomial
function evaluation, but that's a research project in it's own right and
rather platform specific.
For the approximations I always tried to use the least number of terms
possible, my experience is that polynomial approximation works wonders up to
a few digits, but beyond that you often get no more accurate no matter how
many terms you pile on: depends a lot on the function of course. However, I
believe almost all the approximations can be improved on, it really depends
how much time you're prepared to spend thrashing around trying to find the
darn things!
> I'm also curious about the source for the coefficients in these
> expansions. I've looked at a couple using the Maple provided routines
> for producing minimax approximations and gotten somewhat different
> results. Rational coefficients via minimax is a known area where
> though errors are common (the problem is usually illposed in a
> formal sense),
> those errors almost always cancel out. Thus I doubt this will cause
> any problem for the quality of the approximation, but I am curious.
> In general, I'm pleased to see the level of attention given to
> numeric issues and the reasonable solutions provided.
Right, there's good literature supporting the idea that coefficients can be
in error without necessarily adversely effecting the result. The important
thing is to test the approximation to make sure there are no illconditioned
areas (the coefficients can give a theoretically good solution, but the
resulting rational function may be uncomputable at fixed precision).
In the Bessel functions Xiaogang took his coeffiecients from Hart's,
"Computer Approximations" (the accuracy is limited to about 20 digits).
For the special functions that are mine, I devised the approximations myself
using my own Remez code (which actually seemed like a good idea at the
time!). My Remez code is stilla little hairy, but I've tested against a
few published minimax solutions for trivial functions like exp and got
excellent agreement, so I'm pretty sure it's giving good results. That's
allowed me to push the approximations to 128bit (35digit) precision, which
I believe is pretty much unique  I don't know of anyone else publishing
coefficients to that accuracy at this time. I suspect some of these
approximations can be improved upon, but as ever it's a case of how much
time and effort you're prepared to invest. I haven't had a chance to push
the Bessel function approximations to 128bit precision either :(
>> • What is your evaluation of the documentation?
>
> Again, my only issues are nits.
> The documentation is huge and thorough. It almost forms a framework
> for a couple of texts. There are some minor editing issues, but so
> far I
> have only found one relatively major one (in the PDF, at least). In
What was the issue? Thanks.
> the introduction you give a list of the included special functions
> that is
> very much shorter than the real list.
Will fix.
>> And finally, every review should answer this question:
>> • Do you think the library should be accepted as a Boost library?
>
> Yes. I do. The authors deserve high praise for producing one of the
> best facilities of this kind available. People spend a lot of money to
> license far worse software.
Thank you!
John.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk