# Ticket #6059(closed defect: fixed)

Opened 4 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 John Cremona Gonzalo Tornaria 4.0.rc0

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

## Change History

### comment:1 Changed 4 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 4 years ago by tornaria

Fix speed regression in hilbert_symbol (revised)

### comment:2 Changed 4 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 4 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 4 years ago by mabshoff

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

Merged in Sage 4.0.rc0.

Cheers,

Michael

### comment:5 Changed 4 years ago by davidloeffler

• Reviewers set to John Cremona
• Merged in set to 4.0.rc0
• Authors set to Gonzalo Tornaria
Note: See TracTickets for help on using tickets.