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?
--
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+unsubscr...@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.
