Contributing to GMP (fraction approximations)

[Adrien Prost-Boucle]

Hi,

This is an interesting discussion.
I see a general purpose of beginning a computaton with a coarse approximation and then going further into precision, as needed.

An approach could be to add a general-purpose API function that converts a float/mpf/mpfr into a fraction.
A simple algorithm with Farey pairs would fit.
User would provide a constraint in number of bits of some part of the fraction.

A similar variant would also take as input a pre-generated, more approximate fraction, in order to improve precision.
This would require to also provide the previous surrounding Farey pair fractions.
And to take care of the rounding direction of the previously-provided float, to avoid getting out of bounds (mpfr specific ?).
But it may be worth it.

Regards,
Adrien



On Wed, 2020-02-26 at 11:13 +0100, Marco Bodrato wrote:
> Ciao,
> 
> Il Lun, 24 Febbraio 2020 2:51 pm, Marc Glisse ha scritto:
> > On Mon, 24 Feb 2020, Marco Bodrato wrote:
> > > Of course, if you don't care to obtain sqrt(9/49) = 3/7 or anything
> > > different...
> > 
> > If you are going to approximate sqrt(2) with a rational, you probably
> > don't care that much about getting exactly 3/7 either.
> 
> True, but 3/7 is more efficient for the following computations :-)
> 
> > > Well, also mpz_sqrt is not exact :-)
> > 
> > I see it more like division: you can see integer division as inexact, or
> > as a different operation (division with remainder).
> 
> That's an interesting point of view.
> 
> > > But of course, with mpq, we can decide how to approximate.
> > 
> > By the way, maybe the function could return a bool (exact or not) or
> > {-1,0,+1} to say in which direction it approximated.
> 
> That's the easy part. But one may also want to let the caller decide the
> desired direction of approximation. Efficiency is much more tricky.
> 
> Ĝis,
> m
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss