#10255: improve karatsuba multiplication of univariate polynomials
--------------------------------+-------------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.6.1
Component: basic arithmetic | Keywords: karatsuba, multiplication,
polynomial
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by lftabera):
All doctest passes and I am trying to make doctest independent of future
changes of the default threshold. But I get the following difference that
puzzles me.
{{{
sage -t -long -force_lib "devel/sage/sage/rings/qqbar.py"
**********************************************************************
File "/home/rosamari/sage/devel/sage/sage/rings/qqbar.py", line 373:
sage: sage_input(one, verify=True)
Expected:
# Verified
R.<x> = QQbar[]
v1 = AA(2)
v2 = QQbar(sqrt(v1))
v3 = QQbar(3)
v4 = sqrt(v3)
v5 = v2*v4
v6 = (1 - v2)*(1 - v4) - 1 - v5
v7 = QQbar(sqrt(v1))
v8 = sqrt(v3)
si1 = v7*v8
cp = AA.common_polynomial(x^2 + ((1 - v7)*(1 + v8) - 1 + si1)*x - si1)
v9 = QQbar.polynomial_root(cp, RIF(-RR(1.7320508075688774),
-RR(1.7320508075688772)))
v10 = 1 - v9
v11 = v6 + (v10 - 1)
v12 = -1 - v4 - QQbar.polynomial_root(cp, RIF(-RR(1.7320508075688774),
-RR(1.7320508075688772)))
v13 = 1 + v12
v14 = v10*(v6 + v5) - (v6 - v5*v9)
si2 = v5*v9
AA.polynomial_root(AA.common_polynomial(x^4 + (v11 + (v13 - 1))*x^3 +
(v14 + (v13*v11 - v11))*x^2 + (v13*(v14 - si2) - (v14 - si2*v12))*x -
si2*v12), RIF(RR(0.99999999999999989), RR(1.0000000000000002)))
Got:
# Verified
R.<x> = QQbar[]
v1 = QQbar(3)
v2 = sqrt(v1)
v3 = AA(2)
v4 = QQbar(sqrt(v3))
v5 = sqrt(v1)
si1 = v4*v5
cp = AA.common_polynomial(x^2 + ((1 - v4)*(1 + v5) - 1 + si1)*x - si1)
v6 = -1 - v2 - QQbar.polynomial_root(cp, RIF(-RR(1.7320508075688774),
-RR(1.7320508075688772)))
v7 = QQbar.polynomial_root(cp, RIF(-RR(1.7320508075688774),
-RR(1.7320508075688772)))
v8 = QQbar(sqrt(v3))
v9 = v8*v2
v10 = (1 - v8)*(1 - v2) - 1 - v9
v11 = -v7 + v10
v12 = v6*v11
si2 = v7*v9
v13 = (1 - v7)*(v10 + v9) - v10 + si2
si3 = v6*si2
AA.polynomial_root(AA.common_polynomial(x^4 + ((1 + v6)*(1 + v11) - 1
- v12)*x^3 + (v12 + v13)*x^2 + ((1 + v6)*(v13 - si2) - v13 + si3)*x -
si3), RIF(RR(0.99999999999999989), RR(1.0000000000000002)))
**********************************************************************
1 items had failures:
1 of 152 in __main__.example_0
***Test Failed*** 1 failures.
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:4>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
