needless quadratic time code in number_field.py

[culler]

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.

Component: number fields

Author: Frédéric Chapoton

Branch/Commit: 43d2b98

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/22681

[fchapoton]

Branch: u/chapoton/22681

[fchapoton]

Commit: fa361f6

[fchapoton]

Author: Frédéric Chapoton

[fchapoton]

New commits:

fa361f6

trac 22681 cleanup

[videlec]

comment:2

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

[sagetrac-git]

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

34e7003

trac 22681 one more enhancement

[sagetrac-git]

Changed commit from fa361f6 to 34e7003

[sagetrac-git]

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

3c95d38

trac 22681 fix

[sagetrac-git]

Changed commit from 34e7003 to 3c95d38

[fchapoton]

comment:5

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

[videlec]

comment:6

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]
**********************************************************************

[sagetrac-git]

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

19b94b7

trac 22681 fixing one doctest

[sagetrac-git]

Changed commit from 3c95d38 to 19b94b7

[fchapoton]

comment:8

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

[videlec]

comment:9

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

[sagetrac-git]

Changed commit from 19b94b7 to 43d2b98

[sagetrac-git]

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

d9a388c	Merge branch 'u/chapoton/22681' in 8.0.b0
43d2b98	trac 22681 better doctest

[fchapoton]

comment:11

I made a better doctest

[videlec]

comment:12

good!

[videlec]

Reviewer: Vincent Delecroix

[vbraun]

Changed branch from u/chapoton/22681 to 43d2b98