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:  sage8.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: 
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 speedup.
Change History (13)
comment:1 Changed 5 years ago by
 Branch set to u/chapoton/22681
 Commit set to fa361f6259f795e255ee423c97ca0d362a2ff0e4
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
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
 Commit changed from fa361f6259f795e255ee423c97ca0d362a2ff0e4 to 34e700366657ea14f2bbbb4890de00ffeaa859f4
Branch pushed to git repo; I updated commit sha1. New commits:
34e7003  trac 22681 one more enhancement

comment:4 Changed 5 years ago by
 Commit changed from 34e700366657ea14f2bbbb4890de00ffeaa859f4 to 3c95d38d95a091ce866bbbb6952731b7efc9057f
Branch pushed to git repo; I updated commit sha1. New commits:
3c95d38  trac 22681 fix

comment:5 Changed 5 years ago by
Salut. Merci pour la suggestion. C'est fait.
comment:6 Changed 5 years ago by
 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
 Commit changed from 3c95d38d95a091ce866bbbb6952731b7efc9057f to 19b94b7d5db6f80b905f7991cbaab792e273901f
Branch pushed to git repo; I updated commit sha1. New commits:
19b94b7  trac 22681 fixing one doctest

comment:8 Changed 5 years ago by
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
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*(a1) in r True
(however it would be interesting to investigate why it is different each time now...)
comment:10 Changed 5 years ago by
 Commit changed from 19b94b7d5db6f80b905f7991cbaab792e273901f to 43d2b982329fdd43c1ada3238c15b55eceabb06c
comment:11 Changed 5 years ago by
 Status changed from needs_work to needs_review
I made a better doctest
comment:12 Changed 5 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
good!
comment:13 Changed 5 years ago by
 Branch changed from u/chapoton/22681 to 43d2b982329fdd43c1ada3238c15b55eceabb06c
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac 22681 cleanup