sign is slow (if not wrong) for number field elements

[videlec]

sage: x = polygen(ZZ)
sage: K.<a> = NumberField(x^100 - 3, embedding=AA(3)**(1/100))
sage: %time sign(a)
CPU times: user 1.34 s, sys: 0 ns, total: 1.34 s
Wall time: 1.33 s
1
sage: b = continued_fraction(a).convergent(20) - a
sage: sign(b)
sgn(-1/1495877943276*(1/4)^(1/5)*(-(sqrt(5) - I*sqrt(-2*sqrt(5) + 10) + 1)*(-3^(1/4))^(1/5))^(1/5)*(373969485819*sqrt(5) - 373969485819*I*sqrt(-2*sqrt(5) + 10) + 373969485819) + 378100611523/373969485819)

With the branch applied

sage: %time sign(a)
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 4.65 ms
1
sage: b = continued_fraction(a).convergent(20) - a
sage: %time sign(b)
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 6.02 ms
-1

CC: @jdemeyer @pjbruin

Component: number fields

Keywords: days74

Author: Vincent Delecroix

Branch/Commit: 31e8874

Reviewer: Marc Mezzarobba

Issue created by migration from https://trac.sagemath.org/ticket/20756

[videlec]

Branch: u/vdelecroix/20756

[videlec]

New commits:

31e8874

Trac 20756: fix sign for algebraic numbers

[videlec]

Commit: 31e8874

[mezzarobba]

comment:3

Hi Vincent,

Positive review conditional on the patchbot. But note that using RealBallField instead of RealIntervalField would likely be faster. For example, with the b from the ticket's description, we have:

sage: %timeit RIF(b)
1000 loops, best of 3: 916 µs per loop
sage: %timeit RBF(b)
1000 loops, best of 3: 312 µs per loop

sage: %timeit(RealIntervalField(200)(b))
The slowest run took 23.70 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 1.29 ms per loop
sage: %timeit(RealBallField(200)(b))
The slowest run took 5.32 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 514 µs per loop

[videlec]

comment:4

Ho nice! I guess we should move all from intervals to balls... I would prefer doing it all at once.

[mezzarobba]

comment:5

Replying to @videlec:

Ho nice! I guess we should move all from intervals to balls...

Eventually yes. But to be honest, I don't really understand why balls are that much faster in this case, since the conversion from number field elements to balls is optimized in the quadratic case only at this point, and (I think) uses MPFI intervals internally otherwise.

I would prefer doing it all at once.

Your choice! Yet it could be less effort to do it in new code before trying to change existing code.

[videlec]

comment:6

Indeed, moving to balls need serious benchmarks. And doing it all at once make sense since we will go deeply into the two possible conversions, possibly improving them.

So this one stay in needs review as it is. Is that good for you (pathchbot is happy)?

[mezzarobba]

Reviewer: Marc Mezzarobba

[mezzarobba]

comment:7

Replying to @videlec:

So this one stay in needs review as it is. Is that good for you (pathchbot is happy)?

Yes, what I wrote about balls was just a side remark.

[vbraun]

Changed branch from u/vdelecroix/20756 to 31e8874