Re: Rational approximation link

From: brianjparker_at_[hidden]
Date: 2001-10-23 22:07:16

--- In boost_at_y..., helmut.zeisel_at_a... wrote:
> --- In boost_at_y..., brianjparker_at_h... wrote:
> > --- In boost_at_y..., Daryle Walker <darylew_at_m...> wrote:
> 
> I uploaded a first version of the rational approximation:
> 
> 
http://groups.yahoo.com/group/boost/files/big_int/farey_20011022.zip 
 
I have only had a quick look through the documentation and 
implementation for now and give my initial comments below- I will 
test it more fully at a later date.

> The prototype is 
> 
> template<class Int, class Float> 
> boost::rational<Int> farey(const Float& v, const Int& lim);
> 
> > > 
> > > Maybe we should have both.
> > 
> > Yes, that is my conclusion as well. 
> 
> This would be no problem for me - I would appreciate
> to have different options.
> 
> > It may be possible to overload 
> > the function based on the error term type- double or float for 
> > relative error and integer for max. denominator, although this 
may 
> be 
> > too fragile and separate function names may be better.
> 
> Do not try to be too clever.
> Since there are different options for rational approximation,
> it will be difficult to find a single interface
> for all of them.
> 
> I chose the name "farey" to point out
> that it is just one algorithm
> and not the only solution for rational approximation.
> 
> > An advantage of the relative error approach is that a default 
small 
> > value close to the epsilon of the floating point representation 
> could 
> > be specified, so that the error argument could be ignored in many 
> > cases.
> 
> If you just want to control the relative error,
> there is a simple rule how to specify the max. denominator.
> You can find it in my preliminary documentation.

Yes, good point. It may still be a good idea to provide both 
interfaces as a convenience.

> Observe that the return type is rational<Int>,
> so we need one way to secify the integer type to be used.
> Specifying it by the type of the second parameter
> is IMHO the most convenient solution.

It may be better to pass in the rational as a non-const reference, 
also I think the name should be more suggestive of its purpose, 
perhaps something like (better names could be found)-

template<class Int, class Float> 
void rational_approximation_farey(boost::rational<Int>& r, const 
Float& v, const Int& lim);

template<class Int, class Float> 
void rational_approximation_farey2(boost::rational<Int>& r, const 
Float& v, double error);

>  
> > Also, as was pointed out in a previous posting, the Netlib code 
> needs 
> > to have two defines updated for IEEE754 floating point- I will 
look 
> > into this in the future.
> > 
> 
> IMHO updating for IEEE754 is not enough -
> the algorithm should also work for some future
> high precision floating point type.

You mean a user-defined extended floating point type?

> A better solution would be to choose these
> values from std::numeric_limits.

Agreed.

> I fear, however, that this will not be possible
> without deeper understanding of the algorithm used there,
> and this (thanks to the gotos) will not be possible
> without a look into the book referenced there.
> 
> Helmut

Your code looks like it would be a useful addition to Boost, IMO.

,Brian Parker.