Opened 8 years ago

Closed 8 years ago

#15243 closed enhancement (fixed)

Change algorithm for K.uniformizer(P)

Reported by: jdemeyer Owned by:
Priority: minor Milestone: sage-5.13
Component: number fields Keywords:
Cc: Merged in: sage-5.13.beta0
Authors: Jeroen Demeyer Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14476, #15124 Stopgaps:

Status badges

Description

As shown by #14476, it is annoying that the following depends on the hardware:

sage: K.<t> = NumberField(x^4 - x^3 - 3*x^2 - x + 1)
sage: [K.uniformizer(P) for P,e in factor(K.ideal(5))]

Moreover, the algorithm for K.uniformizer() seems inefficient: instead of calling idealappr(), we can simply use the second component of the pari_prime() structure. Experiments show that this yields equal results for 32-bit and 64-bit machines (but there is no guarantee).

Attachments (1)

15243_uniformizer.patch (5.5 KB) - added by jdemeyer 8 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 8 years ago by jdemeyer

  • Summary changed from Change algoritm for K.uniformizer(P) to Change algorithm for K.uniformizer(P)

comment:2 Changed 8 years ago by jdemeyer

  • Dependencies set to #14476

Changed 8 years ago by jdemeyer

comment:3 Changed 8 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Status changed from new to needs_review

comment:4 Changed 8 years ago by cremona

Could you explain the first two hunks of your patch?

comment:5 Changed 8 years ago by jdemeyer

The change to sage/libs/pari/decl.pxi is to remove a duplicate definition of stackdummy() (and is technically unrelated to this patch). The change to sage/libs/pari/gen.pyx is to use a version of idealappr() with an extra flag, see

gp> ?idealappr
idealappr(nf,x,{flag=0}): x being a fractional ideal, gives an element b such that v_p(b)=v_p(x) for all prime ideals p dividing x, and v_p(b)>=0 for all other p. If 
(optional) flag is non-null x must be a prime ideal factorization with possibly zero exponents.

comment:6 Changed 8 years ago by cremona

Thanks. Patch looks good, testing now on 64-bit...32 will take longer....

comment:7 Changed 8 years ago by cremona

..getting some 32-bit errors in number_field.py, full report when it finishes.

comment:8 Changed 8 years ago by cremona

On 32-bit:

sage -t --long devel/sage/sage/rings/number_field/number_field.py  # 2 doctests failed
sage -t --long devel/sage/sage/schemes/elliptic_curves/ell_number_field.py  # 3 doctests failed
sage -t --long devel/sage/sage/rings/number_field/number_field_ideal.py  # 1 doctest failed
sage -t --long devel/sage/sage/rings/residue_field.pyx  # 1 doctest failed
sage -t --long devel/sage/sage/schemes/elliptic_curves/ell_local_data.py  # 1 doctest failed

I will give further details later but will not have access to the 32-bit machine again until the evening.

comment:9 follow-up: Changed 8 years ago by jdemeyer

Strange, all tests pass for me on 32-bit. Are you sure you don't have any other patches applied (apart from #14476 and #15243)?

comment:10 in reply to: ↑ 9 Changed 8 years ago by cremona

Replying to jdemeyer:

Strange, all tests pass for me on 32-bit. Are you sure you don't have any other patches applied (apart from #14476 and #15243)?

I am pretty confident in that but will check. The machine is at home though, and I no longer have a 32-bit desktop in my office, so cannot do it before this evening.

It's certainly getting harder to test 32-bit builds these days!

comment:11 Changed 8 years ago by cremona

To confirm: this was sage-5.12.beta4 and the only patches applied are

trac_14476_bugs_in_local_data.patch
trac_14476_trac_links.patch
15243_uniformizer.patch

Here are some details:

**********************************************************************
File "devel/sage/sage/rings/number_field/number_field.py", line 5205, in sage.rings.number_field.number_field.NumberField_generic.uniformizer
Failed example:
    K.ideal(pi).factor()
Expected:
    (Fractional ideal (2, a + 1))^-1 * (Fractional ideal (3, a + 1))
Got:
    (Fractional ideal (2, a + 1)) * (Fractional ideal (3, a + 1))
**********************************************************************
**********************************************************************
File "devel/sage/sage/schemes/elliptic_curves/ell_local_data.py", line 671, in sage.schemes.elliptic_curves.ell_local_data.EllipticCurveLocalData._tate
Failed example:
    E.conductor() # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 479, in _run
        self.execute(example, compiled, test.globs)
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 838, in execute
        exec compiled in globs
      File "<doctest sage.schemes.elliptic_curves.ell_local_data.EllipticCurveLocalData._tate[11]>", line 1, in <module>
        E.conductor() # indirect doctest
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py", line 1321, in conductor
        for d in self.local_data()],\
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py", line 777, in local_data
        return [self._get_local_data(pr, proof) for pr in primes]
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py", line 836, in _get_local_data
        self._local_data[P, proof, algorithm] = EllipticCurveLocalData(self, P, proof, algorithm)
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_local_data.py", line 270, in __init__
        self._Emin, ch, self._val_disc, self._fp, self._KS, self._cp, self._split = self._tate(proof)
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_local_data.py", line 1035, in _tate
        pi_neg = K.uniformizer(P, 'negative')
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 5249, in uniformizer
        return ~self(nf.idealappr(F, 1))
      File "gen.pyx", line 10605, in sage.libs.pari.gen._pari_trap (sage/libs/pari/gen.c:56583)
    PariError:  (5)
**********************************************************************

and similar.

comment:12 follow-up: Changed 8 years ago by jdemeyer

I don't know what to say, it works for me...

Just to be sure, can you remove all patches, re-download and apply them and do ./sage -b and test again?

comment:13 in reply to: ↑ 12 ; follow-up: Changed 8 years ago by cremona

Replying to jdemeyer:

I don't know what to say, it works for me...

Just to be sure, can you remove all patches, re-download and apply them and do ./sage -b and test again?

OK, will do

Version 0, edited 8 years ago by cremona (next)

comment:14 in reply to: ↑ 13 Changed 8 years ago by jdemeyer

Replying to cremona:

could this be because I am using 5.12.beta4 and not beta5 or later?

Yes, indeed. Or just apply #15124.

comment:15 Changed 8 years ago by jdemeyer

  • Dependencies changed from #14476 to #14476, #15124

comment:16 Changed 8 years ago by cremona

  • Reviewers set to John Cremona
  • Status changed from needs_review to positive_review

With the extra dependency satisfied all is well, and all tests pass on a 32-bit machine too. Positive review!

comment:17 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.13.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.