On Mon, May 3, 2021 at 2:21 PM Ilia <ilia....@orange.fr
> On Monday, May 3, 2021 at 11:12:35 AM UTC+2 dim...@gmail.com
>> 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():
> ; 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
something like this (I think I saw it in
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.
> 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