Opened 10 years ago

Closed 5 months ago

#11543 closed defect (invalid)

Hashing algebraic numbers takes far too long

Reported by: rbeezer Owned by: AlexGhitza
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Hashing algebraic numbers can take a very long time. I've traced this to line 2421 of sage/rings/qqbar.py which can be re-created by the following code. 

sage: A=matrix(QQ, 4, 4, [1, 2, -2, 2, 1, 0, -1, -1, 0, -1, 1, 1, -1, 2, 1/2, 0])
sage: e = A.eigenvalues()[3]
sage: K = (A-e).kernel()
sage: P = K.basis_matrix()
sage: x = P.list()[3]

sage: from sage.rings.qqbar import ANExtensionElement, AlgebraicGenerator, ANRoot, AAPoly
sage: QQbar_I_nf = QuadraticField(-1, 'I', embedding=CC.gen())
sage: QQbar_I_generator = AlgebraicGenerator(QQbar_I_nf, ANRoot(AAPoly.gen()**2 + 1, CIF(0, 1)))
sage: QQbar_hash_offset = AlgebraicNumber(ANExtensionElement(QQbar_I_generator, ~ZZ(123456789) + QQbar_I_nf.gen()/ZZ(987654321)))

sage: time h = hash((x + QQbar_hash_offset).interval_exact(CIF))

Time: CPU 58.31 s, Wall: 58.48 s

Change History (7)

comment:1 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 5 months ago by gh-mjungmath

I cannot reproduce that behavior with Sage 9.2 (Windows): 

CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.14 ms

Seems to be solved.

comment:6 Changed 5 months ago by gh-DaveWitteMorris

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Priority changed from major to minor
  • Status changed from new to needs_review

I agree. I see no problem with 9.2 on CoCalc or 9.3b6 on MacOS 10.15.7. Let's close this old ticket as "works for me".

comment:7 Changed 5 months ago by vdelecroix

  • Resolution set to invalid
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.