#10480: fast PowerSeries_poly multiplication
-----------------------------------+----------------------------------------
Reporter: pernici | Owner: malb
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.6.2
Component: commutative algebra | Keywords: power series
Author: mario pernici | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------------+----------------------------------------
Comment(by lftabera):
Mario,
This part on your patch
{{{
zeros = [0] * e
t0 = do_mul_trunc(b,d,h)
t1a = do_mul_trunc(a,d,h-e)
t1b = do_mul_trunc(b,c,h-e)
t1 = zeros + _karatsuba_sum(t1a,t1b)
t2 = zeros + zeros + do_mul_trunc(a,c,h-2*e)
return _karatsuba_sum(t0,_karatsuba_sum(t1,t2))
}}}
Is inefficient, 2/3 of the operations in this part is adding a ring
element with python zero. This was included in original do_karatsuba and
was the reason to rewrite it in #10255.
I get the following numbers with the patches:
{{{
sage: R.<a,b> = QQ[]
sage: K.<t> = PowerSeriesRing(R)
sage: time p1 = (1 + a*t + b*t^2 + O(t^50))^-40
}}}
No patch: 8.92[[BR]]
multiplication2: 0.66[[BR]]
alternative: 0.45
{{{
sage: K.<x>=PowerSeriesRing(QQ[I])
sage: p1 = K.random_element(800)
sage: p2 = K.random_element(800)
}}}
No patch: 1.59[[BR]]
#10255: 0.24 [[BR]]
multiplication2: 1.57 [[BR]]
alternative2: 0.19
{{{
sage: R.<a,b> = QQ[]
sage: K.<t> = PowerSeriesRing(R)
sage: p1 = QQ[a,b][t].random_element(800) + O(t^800)
sage: p2 = QQ[a,b][t].random_element(800) + O(t^800)
}}}
No patch: 5.75 [[BR]]
#10255: 5.25 [[BR]]
multiplication2: 4.62 [[BR]]
alternative2: 2.41
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10480#comment:7>
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.
