Opened 4 years ago

Closed 4 years ago

Last modified 3 years ago

#26898 closed defect (fixed)

Hashes of some Algebraic Field elements hang indefinitely

Reported by: gh-BrentBaccala Owned by:
Priority: major Milestone: sage-8.6
Component: number fields Keywords: hash, algebraic field
Cc: Merged in:
Authors: Brent Baccala Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: fc0e2e3 (Commits, GitHub, GitLab) Commit: fc0e2e32fa6ac144a15e3673f6659bd686a023d8
Dependencies: Stopgaps:

Status badges

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

Change History (9)

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:

fc0e2e3Trac #26898: actually use 40 bits of extra precision (like the comments say)

comment:4 follow-up: Changed 4 years ago by mmezzarobba

Should the ticket be set to needs_review?

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

Replying to mmezzarobba:

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

Replying to gh-BrentBaccala:

Replying to mmezzarobba:

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