search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.37k stars 469 forks source link

Conversion of already exactified algebraic numbers to number field elements is very slow #33811

Open mezzarobba opened 2 years ago

mezzarobba commented 2 years ago

Consider:

sage: P.<t> = QQ[]
sage: coefficients_as_integer_ratios = [
....:     (-2774600080567517563395913264491323241652779066919616441429094563840,
....:      4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333),
....:     (-24216324060414384566983400245979288839929814383090701293489050615808,
....:      4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333),
....:     (325579773864372490083706670433410006284520887405882567940047555526656,
....:      180143564412823751787837643000565238870031999674661705128541236331583133845246252269971),
....:     (-86736048492777879473586471630941922517134071457946320753641122078523392,
....:      4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333),
....:     (-2338058278498910195688689352766977573607428722429118859280880481590329344,
....:      4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333),
....:     (105830270645785996318880019945503938356315302592627229453391693256551317504,
....:      1381100660498315430373421929671000164670245330839073072652149478542137359480221267403111),
....:     (1110926147990548796149597141538460730252912439930561079348611699181798425600,
....:      4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333),
....:     (-89705438380888704653335165590083767769953879654958783855317882966200828559360,
....:      4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333),
....:     (1151092895747371986483047191334923516591005329489629755485810229546333821625856,
....:      1381100660498315430373421929671000164670245330839073072652149478542137359480221267403111),
....:     (24725641793859400310483886670136079788266826658111372723121573233077840328938576,
....:      4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333),
....:     (-31051495080139473677925068000403254349133134904365702868216464107777210775457136,
....:      153455628944257270041491325519000018296693925648785896961349942060237484386691251933679),
....:     (9431591461895130351865642769482226964622378075329823505708119342634182162193000560,
....:      4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333),
....:     (1721694880863483428337378731387732043714427651970488363462560317808769716807148992,
....:      153455628944257270041491325519000018296693925648785896961349942060237484386691251933679),
....:     (255327752077837584624694974814916395144764296822788813014081161094149724325120096,
....:      27080405107810106477910233915117650287651869232138687699061754481218379597651397400061),
....:     (238105337335596176836773151768694069523377650990453522899627157538495252117232992338,
....:      27080405107810106477910233915117650287651869232138687699061754481218379597651397400061),
....:     (1255826892296350234297164500548658984205287902407560187136301197703464130999349114638,
....:      14336685057075938723599535602121108975815695475838128781856222960645024492874269211797),
....:     (1, 1)]
sage: p = P(coefficients_as_integer_ratios)
sage: from sage.rings.qqbar import *
sage: F = NumberField(p, 'a', check=False)
sage: za = RIF(-RR(0.036151142425748496), -RR(0.036151142425748489))
sage: zb = RIF(-RR(0.011298617187916445), -RR(0.011298617187916443))
sage: r = ANRoot(p, CIF(za, zb))
sage: gen = AlgebraicGenerator(F, r)
sage: a = AlgebraicNumber(ANExtensionElement(gen, F.gen()))

We can check that internally, a is represented as a number field element, and a.exactify() has nothing to do:

sage: type(a._descr)
<class 'sage.rings.qqbar.ANExtensionElement'>
sage: a._descr
a where a^16 + 1255826892296350234297164500548658984205287902407560187136301197703464130999349114638/14336685057075938723599535602121108975815695475838128781856222960645024492874269211797*a^15 + 238105337335596176836773151768694069523377650990453522899627157538495252117232992338/27080405107810106477910233915117650287651869232138687699061754481218379597651397400061*a^14 + 255327752077837584624694974814916395144764296822788813014081161094149724325120096/27080405107810106477910233915117650287651869232138687699061754481218379597651397400061*a^13 + 1721694880863483428337378731387732043714427651970488363462560317808769716807148992/153455628944257270041491325519000018296693925648785896961349942060237484386691251933679*a^12 + 9431591461895130351865642769482226964622378075329823505708119342634182162193000560/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333*a^11 - 31051495080139473677925068000403254349133134904365702868216464107777210775457136/153455628944257270041491325519000018296693925648785896961349942060237484386691251933679*a^10 + 24725641793859400310483886670136079788266826658111372723121573233077840328938576/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333*a^9 + 1151092895747371986483047191334923516591005329489629755485810229546333821625856/1381100660498315430373421929671000164670245330839073072652149478542137359480221267403111*a^8 - 89705438380888704653335165590083767769953879654958783855317882966200828559360/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333*a^7 + 1110926147990548796149597141538460730252912439930561079348611699181798425600/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333*a^6 + 105830270645785996318880019945503938356315302592627229453391693256551317504/1381100660498315430373421929671000164670245330839073072652149478542137359480221267403111*a^5 - 2338058278498910195688689352766977573607428722429118859280880481590329344/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333*a^4 - 86736048492777879473586471630941922517134071457946320753641122078523392/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333*a^3 + 325579773864372490083706670433410006284520887405882567940047555526656/180143564412823751787837643000565238870031999674661705128541236331583133845246252269971*a^2 - 24216324060414384566983400245979288839929814383090701293489050615808/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333*a - 2774600080567517563395913264491323241652779066919616441429094563840/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333 = 0 and a in -0.03615114242574849? - 0.011298617187916444?*I
sage: a.exactify()

However, this does not finish in reasonable time:

sage: a.as_number_field_element()

My understanding is that number_field_elements_from_algebraic() essentially converts a from an ANExtensionElement to an ANRoot exact_generator. Then the minimal polynomial is evaluated on the ANRoot to check that the embedding being set up makes sense. (Is it necessary to perform this check at all, in this context?) The evaluation results in an expression tree that is exactify()ed to check that it is zero—which would have been obvious if the evaluation point has been kept in ANExtensionElement form.

Even then, exactifying an expression of the form pol(a) where pol ∈ ℚ[x] should be easy once a is exactified, and exactifying an ANRoot defined over ℚ (by an irreducible polynomial, in our case) should be easy... See #33810 about that part.

CC: @mwageringel @jplab @videlec @slel

Component: number fields

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

mezzarobba commented 2 years ago

Description changed:

--- 
+++ 
@@ -50,4 +50,7 @@

sage: a.as_number_field_element()

-My is that `number_field_elements_from_algebraic()` essentially converts `a` from an `ANExtensionElement` to an `ANRoot` `exact_generator`. Then the minimal polynomial is evaluated on the `ANRoot` to check that the embedding being set up makes sense. (Is it necessary to perform this check at all, in this context?) The evaluation results in an expression tree that is exactified to check that it is zero—which would have been obvious if the evaluation point has been kept in `ANExtensionElement` form.
+
+My understanding is that `number_field_elements_from_algebraic()` essentially converts `a` from an `ANExtensionElement` to an `ANRoot` `exact_generator`. Then the minimal polynomial is evaluated on the `ANRoot` to check that the embedding being set up makes sense. (Is it necessary to perform this check at all, in this context?) The evaluation results in an expression tree that is `exactify()`ed to check that it is zero—which would have been obvious if the evaluation point has been kept in `ANExtensionElement` form.
+
+Even then, exactifying an expression of the form pol(a) where pol ∈ ℚ[x] should be easy once a is exactified, and exactifying an `ANRoot` defined over ℚ (by an irreducible polynomial, in our case) should be easy... See #33810 about that part.
mezzarobba commented 2 years ago
comment:2

number_field_elements_from_algebraics() also seems to waste a lot of time trying to decide if the number(s) to be converted are real.

slel commented 2 years ago

Description changed:

--- 
+++ 
@@ -2,39 +2,48 @@

sage: P. = QQ[] -sage: pol = t^16 + 1255826892296350234297164500548658984205287902407560187136301197703464130999349114638/14336 -....: 685057075938723599535602121108975815695475838128781856222960645024492874269211797t^15 + 238105337335596 -....: 176836773151768694069523377650990453522899627157538495252117232992338/2708040510781010647791023391511765 -....: 0287651869232138687699061754481218379597651397400061t^14 + 25532775207783758462469497481491639514476429 -....: 6822788813014081161094149724325120096/270804051078101064779102339151176502876518692321386876990617544812 -....: 18379597651397400061t^13 + 1721694880863483428337378731387732043714427651970488363462560317808769716807 -....: 148992/153455628944257270041491325519000018296693925648785896961349942060237484386691251933679t^12 + 94 -....: 31591461895130351865642769482226964622378075329823505708119342634182162193000560/41433019814949462911202 -....: 65789013000494010735992517219217956448435626412078440663802209333t^11 - 3105149508013947367792506800040 -....: 3254349133134904365702868216464107777210775457136/153455628944257270041491325519000018296693925648785896 -....: 961349942060237484386691251933679t^10 + 247256417938594003104838866701360797882668266581113727231215732 -....: 33077840328938576/41433019814949462911202657890130004940107359925172192179564484356264120784406638022093 -....: 33t^9 + 1151092895747371986483047191334923516591005329489629755485810229546333821625856/138110066049831 -....: 5430373421929671000164670245330839073072652149478542137359480221267403111t^8 - 897054383808887046533351 -....: 65590083767769953879654958783855317882966200828559360/41433019814949462911202657890130004940107359925172 -....: 19217956448435626412078440663802209333t^7 + 11109261479905487961495971415384607302529124399305610793486 -....: 11699181798425600/41433019814949462911202657890130004940107359925172192179564484356264120784406638022093 -....: 33t^6 + 105830270645785996318880019945503938356315302592627229453391693256551317504/1381100660498315430 -....: 373421929671000164670245330839073072652149478542137359480221267403111t^5 - 2338058278498910195688689352 -....: 766977573607428722429118859280880481590329344/4143301981494946291120265789013000494010735992517219217956 -....: 448435626412078440663802209333t^4 - 8673604849277787947358647163094192251713407145794632075364112207852 -....: 3392/4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333t^3 + 3255 -....: 79773864372490083706670433410006284520887405882567940047555526656/18014356441282375178783764300056523887 -....: 0031999674661705128541236331583133845246252269971t^2 - 242163240604143845669834002459792888399298143830 -....: 90701293489050615808/41433019814949462911202657890130004940107359925172192179564484356264120784406638022 -....: 09333t - 2774600080567517563395913264491323241652779066919616441429094563840/41433019814949462911202657 -....: 89013000494010735992517219217956448435626412078440663802209333 +sage: coefficients_as_integer_ratios = [ +....: (-2774600080567517563395913264491323241652779066919616441429094563840, +....: 4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333), +....: (-24216324060414384566983400245979288839929814383090701293489050615808, +....: 4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333), +....: (325579773864372490083706670433410006284520887405882567940047555526656, +....: 180143564412823751787837643000565238870031999674661705128541236331583133845246252269971), +....: (-86736048492777879473586471630941922517134071457946320753641122078523392, +....: 4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333), +....: (-2338058278498910195688689352766977573607428722429118859280880481590329344, +....: 4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333), +....: (105830270645785996318880019945503938356315302592627229453391693256551317504, +....: 1381100660498315430373421929671000164670245330839073072652149478542137359480221267403111), +....: (1110926147990548796149597141538460730252912439930561079348611699181798425600, +....: 4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333), +....: (-89705438380888704653335165590083767769953879654958783855317882966200828559360, +....: 4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333), +....: (1151092895747371986483047191334923516591005329489629755485810229546333821625856, +....: 1381100660498315430373421929671000164670245330839073072652149478542137359480221267403111), +....: (24725641793859400310483886670136079788266826658111372723121573233077840328938576, +....: 4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333), +....: (-31051495080139473677925068000403254349133134904365702868216464107777210775457136, +....: 153455628944257270041491325519000018296693925648785896961349942060237484386691251933679), +....: (9431591461895130351865642769482226964622378075329823505708119342634182162193000560, +....: 4143301981494946291120265789013000494010735992517219217956448435626412078440663802209333), +....: (1721694880863483428337378731387732043714427651970488363462560317808769716807148992, +....: 153455628944257270041491325519000018296693925648785896961349942060237484386691251933679), +....: (255327752077837584624694974814916395144764296822788813014081161094149724325120096, +....: 27080405107810106477910233915117650287651869232138687699061754481218379597651397400061), +....: (238105337335596176836773151768694069523377650990453522899627157538495252117232992338, +....: 27080405107810106477910233915117650287651869232138687699061754481218379597651397400061), +....: (1255826892296350234297164500548658984205287902407560187136301197703464130999349114638, +....: 14336685057075938723599535602121108975815695475838128781856222960645024492874269211797), +....: (1, 1)] +sage: p = P(coefficients_as_integer_ratios) sage: from sage.rings.qqbar import -sage: nf = NumberField(pol, 'a', check=False) -....: rt = ANRoot(pol, CIF(RIF(-RR(0.036151142425748496), -RR(0.036151142425748489)), RIF(-RR(0.01129861718791 -....: 6445), -RR(0.011298617187916443)))) -....: gen = AlgebraicGenerator(nf, rt) -....: a = AlgebraicNumber(ANExtensionElement(gen, nf.gen())) +sage: F = NumberField(p, 'a', check=False) +sage: za = RIF(-RR(0.036151142425748496), -RR(0.036151142425748489)) +sage: zb = RIF(-RR(0.011298617187916445), -RR(0.011298617187916443)) +sage: r = ANRoot(p, CIF(za, zb)) +sage: gen = AlgebraicGenerator(F, r) +sage: a = AlgebraicNumber(ANExtensionElement(gen, F.gen()))

 We can check that internally, `a` is represented as a number field element, and `a.exactify()` has nothing to do:
user202729 commented 1 week ago

Somehow this is fast now.