Opened 5 years ago

Closed 5 years ago

#17026 closed enhancement (fixed)

Compare PARI objects using cmp_universal() instead of strcmp()

Reported by: pbruin Owned by:
Priority: minor Milestone: sage-6.4
Component: interfaces Keywords: pari comparison
Cc: jdemeyer Merged in:
Authors: Peter Bruin Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: 85804fc (Commits) Commit: 85804fc472017342a03c4f0ca45062060184e119
Dependencies: #16127 Stopgaps:

Description (last modified by pbruin)

After the separate implementations of __cmp__() and __richcmp__() for PARI objects in #16127, it is a small step to replace the string comparison in __cmp__() by the built-in PARI function cmp_universal(). This is faster, mathematically no more or less meaningful, and (unlike string comparison) gives a total ordering on the set of PARI objects up to the "indistinguishability" relation (gidentical()).

An example of two elements that used to be indistinguishable to cmp():

sage: a = pari("0*ffgen(ffinit(29, 10, 't))"); a
0
sage: b = pari(0); b
0
sage: cmp(a, b)
1

Change History (11)

comment:1 Changed 5 years ago by pbruin

  • Description modified (diff)

comment:2 Changed 5 years ago by pbruin

  • Branch set to u/pbruin/17026-cmp_universal
  • Commit set to a6159f520bdc0985e9ae05829dfee58e9397e947
  • Keywords pari comparison added
  • Status changed from new to needs_review

comment:3 Changed 5 years ago by pbruin

There is only one slightly strange thing in all of this, namely the following:

  • src/sage/rings/number_field/splitting_field.py

    a b class SplittingData: 
    8787    delta = self.dm.__cmp__(other.dm)
    8888    if delta:
    8989        return delta
    90  return self.pol.__cmp__(other.pol)
     90 return cmp(str(self.pol), str(other.pol))
    9191
    9292    def poldegree(self):
    9393        """

I had to resort to string comparison because there is one doctest (in sage/schemes/elliptic_curves/ell_number_field.py) that times out otherwise:

sage: E = EllipticCurve('27a1')
sage: K.<b> = E.division_field(7); K  # long time (8s on sage.math, 2014)

I wonder if we are just lucky that this terminates in reasonable time with the current sorting of polynomials, or if there is some PARI bug that potentially causes a very long time or infinite loop in the splitting field computation.

comment:4 Changed 5 years ago by jdemeyer

  • Branch changed from u/pbruin/17026-cmp_universal to u/jdemeyer/ticket/17026
  • Created changed from 09/22/14 14:19:12 to 09/22/14 14:19:12
  • Modified changed from 09/22/14 15:33:16 to 09/22/14 15:33:16

comment:5 Changed 5 years ago by jdemeyer

  • Commit changed from a6159f520bdc0985e9ae05829dfee58e9397e947 to 5613d3539ac1030bf45033b38113a1750d842f46

Amended commit message.


New commits:

5613d35Trac #17026: use cmp_universal() instead of gcmp_string()

comment:6 Changed 5 years ago by git

  • Commit changed from 5613d3539ac1030bf45033b38113a1750d842f46 to 85804fc472017342a03c4f0ca45062060184e119

Branch pushed to git repo; I updated commit sha1. New commits:

85804fcImprove sorting in splitting_field

comment:7 follow-up: Changed 5 years ago by pbruin

In key(), shouldn't self.poldegree() be self.pol.poldegree()?

Thanks for adding the warning about cmp(); I had planned to do that, but forgot.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 5 years ago by jdemeyer

Replying to pbruin:

In key(), shouldn't self.poldegree() be self.pol.poldegree()?

Doesn't matter, self.poldegree() is defined to be self.pol.poldegree().

comment:9 in reply to: ↑ 8 Changed 5 years ago by pbruin

Replying to jdemeyer:

Replying to pbruin:

In key(), shouldn't self.poldegree() be self.pol.poldegree()?

Doesn't matter, self.poldegree() is defined to be self.pol.poldegree().

I see, that had escaped me.

comment:10 Changed 5 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to positive_review

comment:11 Changed 5 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/17026 to 85804fc472017342a03c4f0ca45062060184e119
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.