Re: [boost] [math toolkit] Formal Review today, April 11, through April 20

From: John Maddock (john_at_[hidden])
Date: 2007-04-25 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 ill-posed 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 ill-conditioned 
areas (the coefficients can give a theoretically good solution, but the 
resulting rational function may be un-computable 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 128-bit (35-digit) 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 128-bit 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.