The sign() method in QQbar overlooks some (presumably) easy shortcuts

[Ilia]

Hello everyone,

(This is my first post on sage-devel. I hope I will not break any unwritten rules, please be forgiving if I do!)

When I run the following code:

x1 = AA(2^(1/100))
x2 = AA(2^(1/100))
x1 == x2

Sage quickly and correctly replies "True". Also,

1/(x1-x2)

quickly raises a ZeroDivisionError. So far, so good. But now try running

sign(x1-x2)

Sage does not seem to terminate in any reasonable time.

After looking at the code, it turns out that both the _richcmp_ method called by "x1 == x2", and the __bool__() method (which checks nonzeroness) called by "1/(x1-x2)", include a check that makes them realize that x1 and x2 are equal, hence obtain the result. For __bool__(), this is quite clever as it involves extracting the _left and _right parts from an ANBinaryExpr representing a sum or difference.

But inexplicably, the sign() method does not include a similar check, and (as traceback shows) tries instead to exactify x1-x2 which takes forever. Wouldn't it be an improvement if it did? In fact, I think it would make sense for the sign() method to call __bool__() first. This way, if it returns False (as in this case), we have the result immediately; and if it returns True, we can simply repeatedly add _more_precision() until we can resolve the number from zero (with the guarantee that this will eventually terminate). Do you see any reason not to do this?

Also, I wonder why exactification even takes so long in this case. Traceback shows that Sage tries to take a union of the two fields, which it defers to PARI, which then stalls. But even admitting that Sage fails to immediately see equality of the elements themselves, presumably it should at least detect equality of the fields they generate; and it should not take long to unify a field (even a complicated one) with itself, should it?

My configuration: SageMath version 9.1, running on Ubuntu 18.04.3 LTS (64-bit).

Best
--
Ilia

[Travis Scrimshaw]

Hi Ilia,

   It would be possible to improve the QQbar element sign() method to check the case when they have the same minimum polynomials. See https://trac.sagemath.org/ticket/31767 for a proposal.

Best,

Travis

[Ilia]

Thanks for the quick fix! I still have a question about the proposed patch:

Suppose we have two algebraic numbers x and y whose minimal polynomials are distinct, but whose values are very close together, e.g. x = AA(1+2*2^(-1000))^(1/2); y = AA(1+3*2^(-1000))^(1/3). This guarantees that x and y are distinct, but does not tell the sign of x-y yet. With the proposed patch, sign(x-y) will try to exactify x-y, which will be very long. Is there any reason not simply add _more_precision() to both until the intervals separate (as I suggested above)?

Best

--

Ilia

[Dima Pasechnik]

On Mon, May 3, 2021 at 9:46 AM Ilia <ilia....@orange.fr> wrote:
>
> Thanks for the quick fix! I still have a question about the proposed patch:
>
> Suppose we have two algebraic numbers x and y whose minimal polynomials are distinct, but whose values are very close together, e.g. x = AA(1+2*2^(-1000))^(1/2); y = AA(1+3*2^(-1000))^(1/3). This guarantees that x and y are distinct, but does not tell the sign of x-y yet. With the proposed patch, sign(x-y) will try to exactify x-y, which will be very long. Is there any reason not simply add _more_precision() to both until the intervals separate (as I suggested above)?

How does one know where to stop? Or you'd want to let it run out of memory?

practically speaking, these computations should be done with a much
more efficient RBF:

sage: x = AA(1+2*2^(-1000))^(1/2); y = AA(1+3*2^(-1000))^(1/3)

sage: R=RealBallField(10000)
sage: R(y)>R(x)
False
sage: R(y)<R(x)
True

note that if precision is insufficient, both tests will return False

sage: R=RealBallField(1000)

sage: R(y)>R(x)
False
sage: R(y)<R(x)
False

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/95976c4e-67e9-4011-a188-962c66fa75efn%40googlegroups.com.

[Ilia]

On Monday, May 3, 2021 at 11:12:35 AM UTC+2 dim...@gmail.com wrote:

 How does one know where to stop? Or you'd want to let it run out of memory?

So we are discussing two different ways of checking the sign of d = x-y: option A is the (finite but unbounded-length) loop

while not d._value.contains_zero():

    d._more_precision()

; option B is simply d.exactify(). Now the right question to ask is: which of these two options is *more* likely to run out of memory?

I suspect that in practice, the answer is in fact option B.

Some more quantitative estimates: option A requires roughly -log(d) bits of memory; while option B requires at least as much memory as is needed to store the minimal polynomial of d - let us call this number size(minpoly(d)).

I am like 90% sure (I can probably produce the proof if you ask) that we have the lower bound size(minpoly(d)) >= O(-log(d)/deg(d)). So it *might* be smaller than -log(d), but at most by a factor of deg(d). But on the other hand, you can very easily have a huge minimal polynomial for a reasonable-sized algebraic number. And I suspect that the latter situation is much more likely in practice.

An additional advantage of option A is that it allows one to cache the result of the computation and re-use it for further comparisons - whereas having the minimal polynomial of x-y does not help you in any way if you later want to compare x and z. Think e.g. of a situation where you want to sort a list of algebraic numbers. (As a reminder, all comparisons of say x and y fall back on calling sign(x-y) whenever the easy checks fail.)

 

practically speaking, these computations should be done with a much
more efficient RBF:

This is an interesting suggestion. But the current implementation of QQbar does all approximate computations with RIF, not RBF. So are you suggesting to completely switch the implementation of QQbar from RIF to RBF? Or maybe to convert from RIF to RBF only for the computation of the sign?

[Dima Pasechnik]

On Mon, May 3, 2021 at 2:21 PM Ilia <ilia....@orange.fr> wrote:
>
> On Monday, May 3, 2021 at 11:12:35 AM UTC+2 dim...@gmail.com wrote:
>>
>> How does one know where to stop? Or you'd want to let it run out of memory?
>
>
> So we are discussing two different ways of checking the sign of d = x-y: option A is the (finite but unbounded-length) loop
>
> while not d._value.contains_zero():
> d._more_precision()
>
> ; option B is simply d.exactify(). Now the right question to ask is: which of these two options is *more* likely to run out of memory?
>
> I suspect that in practice, the answer is in fact option B.

I certainly agree with this.

But the option A looks sub-optimal, as well. Because it seems to be
equivalent to refining the intervals I_x and I_y, where
the roots, x in I_x of its minimal polynomial m_x(t), resp. the root
y in I_y of m_y(t), are located, until I_x and I_y do not overlap.

And this is suboptimal, as one only need to refine (say) I_y until
m_y(t) is monotonic there - indeed, you can then check sign(m_y(x))
and sign((d/dt m_y(t))(x)), and this info then tells you whether y>x
or y<x. And checking signs like this is cheap, this is doing "Sturm
query" (cf. e.g. https://core.ac.uk/download/pdf/21173251.pdf) or
something like this (I think I saw it in
https://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted3.pdf).

Perhaps one can do even better, one might need to check literature on
the use of Thom encoding in real algebraic geometry computations, e.g.
https://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted3.pdf.

>
> Some more quantitative estimates: option A requires roughly -log(d) bits of memory; while option B requires at least as much memory as is needed to store the minimal polynomial of d - let us call this number size(minpoly(d)).
>
> I am like 90% sure (I can probably produce the proof if you ask) that we have the lower bound size(minpoly(d)) >= O(-log(d)/deg(d)). So it *might* be smaller than -log(d), but at most by a factor of deg(d). But on the other hand, you can very easily have a huge minimal polynomial for a reasonable-sized algebraic number. And I suspect that the latter situation is much more likely in practice.
>
> An additional advantage of option A is that it allows one to cache the result of the computation and re-use it for further comparisons - whereas having the minimal polynomial of x-y does not help you in any way if you later want to compare x and z. Think e.g. of a situation where you want to sort a list of algebraic numbers. (As a reminder, all comparisons of say x and y fall back on calling sign(x-y) whenever the easy checks fail.)
>
>>
>> practically speaking, these computations should be done with a much
>> more efficient RBF:
>
>
> This is an interesting suggestion. But the current implementation of QQbar does all approximate computations with RIF, not RBF. So are you suggesting to completely switch the implementation of QQbar from RIF to RBF? Or maybe to convert from RIF to RBF only for the computation of the sign?
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/f9dc9a3d-32d9-4d2f-9cc8-09c4c43d4b4fn%40googlegroups.com.