Re: Rational approximation link

From: helmut.zeisel_at_[hidden]
Date: 2001-10-24 03:43:03

--- In boost_at_y..., brianjparker_at_h... wrote:
> --- In boost_at_y..., helmut.zeisel_at_a... wrote:

> > 
> > 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.

OK.
There is, however, the problem that I am not
completely sure at the moment
whether in the preliminary documentation
my statement about the maximal error is true :-(

I do not understand the theory behind the algorithm completely
and the link that should contain the theory

http://www.cut-the-knot.com/blue/Farey.html

is down until Nov 1.

If someone knows a different place where
the algorithm is explained, please let me know.

I hope, however, that these issues can be clarified.

> 
> 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);

For my personal taste your suggested names are a bit too long;
they are, however, definitely better than my version which
gives indeed too few information.

With respect to the return type I prefer
rational<Int> because of the resource-acquisition-is-initialization
principle, i.e. I want to be able to write

rational<int> approx_pi = 
rational_approximation_farey(3.1415926535,100);

instead of 

rational<int> approx_pi; 
rational_approximation_farey(approx_pi, 3.1415926535,100);

If you think that there might be
some performance impact because of the possible copy
of the return value,
I would say that 

a) the computation inside takes essential more CPU time

and 

b) the copy could be optimized away by the return value optimization.

OTOH, for the second interface some way to completely
specify the return type is needed,
so my suggestion would be:

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

and (function overload, no "2" needed)

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

I do not know, however, whether these
two different interfaces might be too confusing to the user.

> > 
> > 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?

Yes.

Helmut