Opened 5 years ago

Closed 5 years ago

#22681 closed defect (fixed)

needless quadratic time code in number_field.py

Reported by: culler Owned by:
Priority: major Milestone: sage-8.0
Component: number fields Keywords:
Cc: Merged in:
Authors: Frédéric Chapoton Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 43d2b98 (Commits, GitHub, GitLab) Commit: 43d2b982329fdd43c1ada3238c15b55eceabb06c
Dependencies: Stopgaps:

Status badges

Description

sage/src/sage/rings/number_field contains the following loop:

   7292             if both_maps and K.degree() == self.degree():
   7293                 g = K['x'](self.polynomial())
   7294                 v = g.roots()
   7295                 a = from_K(K.gen())
   7296                 for i in range(len(v)):
   7297                     r = g.roots()[i][0]
   7298                     to_K = self.hom([r])    # check=False here ??
   7299                     if to_K(a) == K.gen():
   7300                         break

Line 7297 should read r = v[i][0] .

This actually leads to a huge speed-up.

Change History (13)

comment:1 Changed 5 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to u/chapoton/22681
  • Commit set to fa361f6259f795e255ee423c97ca0d362a2ff0e4
  • Status changed from new to needs_review

New commits:

fa361f6trac 22681 cleanup

comment:2 Changed 5 years ago by vdelecroix

Salut Frédéric,

If you don't care about multiplicity you can use

for root in g.roots(multiplicity=False):
    ...

(which would be cleaner than calling root[0])

comment:3 Changed 5 years ago by git

  • Commit changed from fa361f6259f795e255ee423c97ca0d362a2ff0e4 to 34e700366657ea14f2bbbb4890de00ffeaa859f4

Branch pushed to git repo; I updated commit sha1. New commits:

34e7003trac 22681 one more enhancement

comment:4 Changed 5 years ago by git

  • Commit changed from 34e700366657ea14f2bbbb4890de00ffeaa859f4 to 3c95d38d95a091ce866bbbb6952731b7efc9057f

Branch pushed to git repo; I updated commit sha1. New commits:

3c95d38trac 22681 fix

comment:5 Changed 5 years ago by chapoton

Salut. Merci pour la suggestion. C'est fait.

comment:6 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work
sage -t --long rings/number_field/number_field_rel.py
**********************************************************************
File "rings/number_field/number_field_rel.py", line 1771, in sage.rings.number_field.number_field_rel.NumberField_relative.roots_of_unity
Failed example:
    K.roots_of_unity()[:5]
Expected:
    [b*a + b, b^2*a, -b^3, a + 1, b*a]
Got:
    [b*a, -b^2*a - b^2, b^3, -a, b*a + b]
**********************************************************************

comment:7 Changed 5 years ago by git

  • Commit changed from 3c95d38d95a091ce866bbbb6952731b7efc9057f to 19b94b7d5db6f80b905f7991cbaab792e273901f

Branch pushed to git repo; I updated commit sha1. New commits:

19b94b7trac 22681 fixing one doctest

comment:8 Changed 5 years ago by chapoton

ok, j'ai changé le test, après avoir vérifié que c'etait simplement un ordre different.

comment:9 Changed 5 years ago by vdelecroix

The order is also different with this new version...

sage -t --long src/sage/rings/number_field/number_field_rel.py
**********************************************************************
File "src/sage/rings/number_field/number_field_rel.py", line 1771, in sage.rings.number_field.number_field_rel.NumberField_relative.roots_of_unity
Failed example:
    K.roots_of_unity()[:5]
Expected:
    [b*a, -b^2*a - b^2, b^3, -a, b*a + b]
Got:
    [-b^3*a - b^3, -b^2*a, b, a + 1, -b^3*a]
**********************************************************************

You can for example replace with

sage: r = K.roots_of_unity()
sage: len(r)
24
sage: a*b in r and b^2*(a-1) in r
True

(however it would be interesting to investigate why it is different each time now...)

comment:10 Changed 5 years ago by git

  • Commit changed from 19b94b7d5db6f80b905f7991cbaab792e273901f to 43d2b982329fdd43c1ada3238c15b55eceabb06c

Branch pushed to git repo; I updated commit sha1. New commits:

d9a388cMerge branch 'u/chapoton/22681' in 8.0.b0
43d2b98trac 22681 better doctest

comment:11 Changed 5 years ago by chapoton

  • Status changed from needs_work to needs_review

I made a better doctest

comment:12 Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

good!

comment:13 Changed 5 years ago by vbraun

  • Branch changed from u/chapoton/22681 to 43d2b982329fdd43c1ada3238c15b55eceabb06c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.