Opened 4 years ago

Closed 4 years ago

# Hashes of some Algebraic Field elements hang indefinitely

Reported by: Owned by: gh-BrentBaccala major sage-8.6 number fields hash, algebraic field Brent Baccala Marc Mezzarobba N/A fc0e2e3 fc0e2e32fa6ac144a15e3673f6659bd686a023d8

### Description

The following code hangs on both Sage 7.5.1 and Sage 8.4:

```R.<a> = QQ[]
NF.<b> = NumberField(4*a^7 + 27)
for hom in NF.embeddings(QQbar):
print hash(hom(b))
```

### comment:1 Changed 4 years ago by gh-BrentBaccala

Here's another test case that I constructed after drilling down through the code:

```from sage.rings.qqbar import AlgebraicGenerator, ANRoot

R.<y> = QQ[]
gen = y^14 - 6*y^7 + 18
NF.<a> = NumberField(gen)

root1 = ANRoot(gen, CIF(NF.embeddings(QQbar)[0](a)))
root2 = ANRoot(gen, CIF(NF.embeddings(QQbar)[1](a)))

ag1 = AlgebraicGenerator(NF, root1)
ag2 = AlgebraicGenerator(NF, root2)

ag1.union(ag2)

```

Changing `gen` around produces different answers. `gen = y^2+18` produces the answer I'd expect from `union`: a number field defined by y2 + 18. `gen = y^3+18` produces a number field defined by a sixth degree polynomial; `gen = y^7 + 18` produces a number field defined by a 42nd degree polynomial.

I guess the 14th degree polynomial leads to a calculation that takes excessively long, but I think it should be a very simple calculation if the two `AlgebraicGenerator`'s are from the same number field - it should just return that field, right?

### comment:2 Changed 4 years ago by gh-BrentBaccala

Now that I've thought about it more, the number field might not be a splitting field, so it's more complicated than returning the same field.

### comment:3 Changed 4 years ago by gh-BrentBaccala

• Authors set to Brent Baccala
• Branch set to public/26898
• Commit set to fc0e2e32fa6ac144a15e3673f6659bd686a023d8

I found some comments in the code suggesting that when approximations to algebraic numbers are computed, an attempt is made to use 40 extra bits of precision, but it doesn't seem like that every actually got done.

I made the obvious change to actually compute 40 extra bits, and it seems to have solved my problem.

New commits:

 ​fc0e2e3 `Trac #26898: actually use 40 bits of extra precision (like the comments say)`

### comment:4 follow-up: ↓ 5 Changed 4 years ago by mmezzarobba

Should the ticket be set to needs_review?

### comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 4 years ago by gh-BrentBaccala

Should the ticket be set to needs_review?

Yes, but I'm waiting for it to clear patchbot.

### comment:6 in reply to: ↑ 5 Changed 4 years ago by mmezzarobba

• Status changed from new to needs_review

Should the ticket be set to needs_review?

Yes, but I'm waiting for it to clear patchbot.

Unless you have your own patchbot with a special configuration, it (probably) won't even run the tests until the ticket needs_review.

But I've done it locally and all is well.

### comment:7 Changed 4 years ago by mmezzarobba

• Reviewers set to Marc Mezzarobba
• Status changed from needs_review to positive_review

### comment:8 Changed 4 years ago by vbraun

• Branch changed from public/26898 to fc0e2e32fa6ac144a15e3673f6659bd686a023d8
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:9 Changed 4 years ago by embray

• Milestone changed from sage-8.5 to sage-8.6

This tickets were closed as fixed after the Sage 8.5 release.

Note: See TracTickets for help on using tickets.