#16222: Faster exactification using numeric minpoly
-------------------------------------+-------------------------------------
Reporter: gagern | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: Martin von Gagern | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/gagern/ticket/16222 | 998534a33a502a86518f6c541f99cac1ffacdaa5
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by vdelecroix):
Not exactly related to this ticket: I just found out some maxima magic to
get the polynomial of symbolic expressions involving square root and such
(p. 1041 of the
[[http://maxima.sourceforge.net/docs/manual/maxima.pdf|maxima manual]]):
{{{
(%i1) load(to_poly_solve)$
(%i2) first(elim_allbut(first(to_poly(eq,[1,x])),[x]));
4 2
(%o2) [x - 24 x + 4]
(%i3) eq: x = sqrt(sqrt(3) + sqrt(5) + 1) + sqrt(7);
(%o3) x = sqrt(7) + sqrt(sqrt(5) + sqrt(3) + 1)
(%i3) first(elim_allbut(first(to_poly(eq, [1,x])), [x]));
16 14 12 10 8 6
(%o3) [x - 64 x + 1648 x - 23552 x + 213480 x - 1191424 x
4 2
+ 3340480 x - 3562496 x +
524176]
}}}
It is way much much faster than what we have in Sage for minpoly:
{{{
sage: maxima.load("to_poly_solve")
"/opt/sage_flatsurf/local/share/maxima/5.35.1/share/to_poly_solve/to_poly_solve.mac"
sage: maxima("eq: x = sqrt(sqrt(3) + sqrt(5) + 1) + sqrt(7);")
x=sqrt(7)+sqrt(sqrt(5)+sqrt(3)+1)
sage: maxima("first(elim_allbut(first(to_poly(eq, [1,x])), [x]));")
[x^16-64*x^14+1648*x^12-23552*x^10+213480*x^8-1191424*x^6+3340480*x^4-3562496*x^2+524176]
sage: %timeit maxima("first(elim_allbut(first(to_poly(eq, [1,x])),
[x]));")
10 loops, best of 3: 18 ms per loop
sage: a = sqrt(7) + sqrt(sqrt(5) + sqrt(3) + 1)
sage: %timeit a.minpoly()
1 loops, best of 3: 449 ms per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/16222#comment:16>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
