Opened 12 years ago

Closed 12 years ago

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

Reported by: Owned by: tornaria tornaria major sage-4.0 number theory regression cremona 4.0.rc0 Gonzalo Tornaría John Cremona N/A

### 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.

### comment:1 Changed 12 years ago by tornaria

• 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).

```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.