Opened 12 years ago

Closed 12 years ago

Last modified 5 years ago

#6059 closed defect (fixed)

[with patch; with positive review] speed regresion in hilbert_symbol after #5834

Reported by: tornaria Owned by: tornaria
Priority: major Milestone: sage-4.0
Component: number theory Keywords: regression
Cc: cremona Merged in: 4.0.rc0
Authors: Gonzalo Tornaría Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The following hilbert symbol computation

sage: a=(next_prime(10**22)*next_prime(10**23))
sage: time hilbert_symbol(a,-1,2)
CPU times: user 0.62 s, sys: 0.06 s, total: 0.68 s
Wall time: 0.68 s
1

used to be almost instant before the patch in #5834 (in 4.0.alpha0).

The patch extends hilbert_symbol to work with rationals, by using the squarefree_part() function. However, that function needs to factor. Fortunately, we don't need the actual squarefree part to compute the hilbert symbol, rather we could use numerator()*denominator() to achieve the same result; the hilbert symbol can thus be computed without factoring.

Attachments (1)

trac_6059.patch (783 bytes) - added by tornaria 12 years ago.
Fix speed regression in hilbert_symbol (revised)

Download all attachments as: .zip

Change History (7)

comment:1 Changed 12 years ago by tornaria

  • Cc cremona added
  • Summary changed from speed regresion in hilbert_symbol after #5834 to [with patch; needs review] speed regresion in hilbert_symbol after #5834

Since this fixes a speed regression, and the patch is really simple, I think it's good if it can make it into 4.0.

Changed 12 years ago by tornaria

Fix speed regression in hilbert_symbol (revised)

comment:2 Changed 12 years ago by tornaria

I screwed it up the first version, because I was trying to avoid overhead. The original code, good for integers only (before #5834) was:

a = ZZ(a)

My first version was

a = ZZ(a.numerator() * a.denominator())

which breaks when a is a (python) int. The new version is

a = QQ(a).numerator() * QQ(a).denominator()

which should be safe for all purposes (my first version was in between).

Indeed, I'm a bit concerned about overhead. Compare the trivial

sage: timeit("hilbert_symbol(1,1,-1)")
625 loops, best of 3: 10.3 µs per loop

using the original code (only good for integers) vs.

sage: timeit("hilbert_symbol(1,1,-1)")
625 loops, best of 3: 19.1 µs per loop

with the new code (good for rationals).

And check out the speed of the actual computation:

sage: a = ZZ.random_element(10^50)
sage: b = ZZ.random_element(10^50)
sage: p = next_prime(ZZ.random_element(10^50))
sage: timeit("pari(a).hilbert(b,p)")
625 loops, best of 3: 3.13 µs per loop

Is there a standard/suggested way of writing the preamble of a function (where parameters are checked, coerced, etc) to minimize overhead in a fast path? (I guess this is what one buys with a dynamic language... and moving this to cython could help if really necessary).

comment:3 Changed 12 years ago by cremona

  • Summary changed from [with patch; needs review] speed regresion in hilbert_symbol after #5834 to [with patch; with positive review] speed regresion in hilbert_symbol after #5834

Looks good to me. Sorry about the regression which was my fault. I needed an integer in the same square class as a (and b) and did the obvious thing without thinking about the conseqences regarding factorization.

Would it be better to check for integrality, since if a and b are integral then using ZZ(a), ZZ(b) would save the conversion to rational and back? i.e. do something like try: a=ZZ(a); b=ZZ(b) first.

comment:4 Changed 12 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 4.0.rc0.

Cheers,

Michael

comment:5 Changed 12 years ago by davidloeffler

  • Authors set to Gonzalo Tornaria
  • Merged in set to 4.0.rc0
  • Reviewers set to John Cremona

comment:6 Changed 5 years ago by chapoton

  • Authors changed from Gonzalo Tornaria to Gonzalo Tornaría
  • Report Upstream set to N/A
Note: See TracTickets for help on using tickets.