Contributing to GMP

[Marc Glisse]

On Mon, 24 Feb 2020, Marco Bodrato wrote:

> Ciao,
>
> Il Mar, 18 Febbraio 2020 8:54 pm, Anders Andersson ha scritto:
>> On Tue, Feb 18, 2020 at 1:09 PM Michele Guerini Rocco
>
>>> Anyway, I had to compute the natural logarithm of a natural number to
>>> arbitrary precision, so I wrote a `mpq_log_ui` function to do that,
>>> something which GMP doesn't provide.
>
>> Everything else dealing with rational numbers works with *exact*
>> numbers, and it seems to me that a log_ui will rarely be exact.
>
> I agree, a log_ui function does not belong to the current mpq_t interface.
>
> But maybe it would be interesting to write some mpq_ functions giving
> inexact results... If it is possible to return a fraction that is a good
> result as a fraction. I mean a result that can be interesting for someone
> working with rationals, more interesting than an approximation obtained
> with the floating-point paradigm and converted back to a fraction...
>
> E.g. the attached code computes the square root of a fraction. It returns
> either the exact result, or a result with the denominator limited by a
> given number of bits.
>
> For A=1068966896/340262731, it returns R=2887206440/1628931799.
> Where we have 1628931799 < 2^32, and |A-R^2| < 2^-63.
>
> The code is simple. It computes the continued fraction for the square root
> of a fraction, term by term, and does not exploit the periodicity nor any
> other trick to obtain balanced multiplications... I mean, it's not fast.
>
> Might inexact functions on rationals, like this one, be useful to someone?

In CGAL, we use

template <typename NT>
NT approximate_sqrt(const NT& nt, CGAL::Field_tag)
{
   return NT(sqrt(CGAL::to_double(nt)));
}

That is, for types without sqrt, we convert to double, compute sqrt, and 
convert back. I am not super familiar with the places where this is used, 
but I expect it could use your function instead, if that was fast enough. 
Seeing as it could use MPFR for better precision and doesn't, I am not 
sure though. I think speed may be important there, or precision just 
doesn't matter that much.

> If made faster, of course.
>
> Anyway, extending the rational interface in a coherent way, to add also
> inexact functions, seems difficult.

At least I would give it a name that more clearly reflects its approximate 
nature, like mpq_approximate_sqrt.

> Some example functions may belong to the demo directory :-)
>
> Ĝis,
> m

-- 
Marc Glisse