Feature request: nearby_rational

[heiderich]

I would welcome a function like nearby_rational in Sage (see page 24 in http://doc.sagemath.org/pdf/en/reference/rings_numerical/rings_numerical.pdf). I think it could take elements of type Nemo.arb as input (plus something like max_denominator or max_error) and output elements of type Nemo.fmpq. Does this make sense?

[wbhart]

I think it makes sense. Perhaps @fredrik-johansson has a suggestion?

[thofma]

I have hacked something together in Hecke using the continued fraction functionality from flint, but it is quite fragile. Would love to have something fast and more robust in Nemo.

[fredrik-johansson]

Yes, it makes sense. The logical interface would be to return the simplest rational contained inside the given arb_t.

The easiest way to implement this would be via a function that returns the simplest rational in [a,b] for two fmpq a, b. With an arb_t input, it's then just a matter of doing an exact conversion to an fmpq pair.

I would not mind putting a robust implementation of this feature in Arb itself.

There does need to be some kind of bound for both the numerator and denominator when going from an arb_t since the exponents could be large.

[thofma]

@tthsqe12

[tthsqe12]

@fredrik-johansson (and @thofma to see if you agree on the algorithm) It seems to me you have to do the following. Let x be the closed rational ball from which we would like to select "the rational with smallest denominator". If x contains an integer, then it is clear what to do, so assume from now on that x does not contain an integer. The claim that there is only one such rational and it can be computed as follows. Compute the continued fraction of the ball x as

x = [q1 1; 1 0] * [q2 1; 1 0] * ... * [qn 1; 1 0] (xn)

where n >= 1 and xn is a finite ball satisfying 1<xn and containing some integer (2x2 integer matrices have the usual action on the reals). Such an expansion exists and is unique (with the usual assumption that q2,...,qn are all >=1) and means that [q1, ..., qn] is the common prefix of all continued fractions of elements of x. Then, the rational with smallest denominator in x is

[q1 1; 1 0] * [q2 1; 1 0] * ... * [qn 1; 1 0] (i)

where i is the smallest integer in xn.

[thofma]

I am not an expert but this looks fine to me.

[tthsqe12]

@thofma I think we are near to closing this issue. Since fredrik seems to be MIA for a robust implementation in arb, you will have to do one last step yourself. very rough psuedo code:

simplest_inside(arb_t x):
    fmpz_t a, b, d, e
    fmpq_t r
    arb_get_interval_fmpz_2exp(a, b, e, x)
    e = -e
    do something special if e does not fit in a ulong
    d = 2^e
    _fmpq_simplest_between(numref(r), denref(r), a, d, b, d)
   return r

[thofma]

OK, so the things are merged in flint?

[tthsqe12]

@thofma could we get an update on where your stuff is/what it is called and possibly close this?

[thofma]

Will do.