#8972: Inversion and fraction fields for power series rings
-----------------------------------------------+----------------------------
Reporter: SimonKing | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.6.2
Component: algebra | Resolution:
Keywords: power series ring, fraction field | Author: Simon King
Upstream: N/A | Reviewer: Robert Bradshaw
Merged: | Work_issues:
-----------------------------------------------+----------------------------
Changes (by SimonKing):
* status: needs_work => needs_review
Comment:
I managed to fix the remaining issues, and all tests pass (unless a last
minute change that I just did was a bad idea). Hence, this ticket needs
review again.
Since the computation time was a point of critique, let me give you some
timings:
Without the patch:
{{{
# Basic arithmetic
sage: R.<x> = ZZ[[]]
sage: timeit('a=1/(1+x)')
625 loops, best of 3: 803 µs per loop
sage: timeit('a=1/x')
625 loops, best of 3: 279 µs per loop
sage: timeit('a=(1+x)/x')
625 loops, best of 3: 285 µs per loop
sage: timeit('a=1/(1+x)')
625 loops, best of 3: 801 µs per loop
sage: y = (3*x+2)/(1+x)
sage: y=y/x
sage: z = (x+x^2+1)/(1+x^4+2*x^3+4*x)
sage: z=y/x
sage: timeit('y+z')
625 loops, best of 3: 167 µs per loop
sage: timeit('y*z')
625 loops, best of 3: 100 µs per loop
sage: timeit('y-z')
625 loops, best of 3: 166 µs per loop
# square roots
sage: P.<t> = QQ[[]]
sage: p = 9 - 33*t - 13*t^2 - 155*t^3 - 429*t^4 - 137*t^5 + 170*t^6 +
81*t^7 - 132*t^8 + 179*t^9 + O(t^10)
sage: p.sqrt()
3 - 11/2*t - 173/24*t^2 - 5623/144*t^3 - 174815/1152*t^4 -
8187925/20736*t^5 - 12112939/9216*t^6 - 7942852751/1492992*t^7 -
1570233970141/71663616*t^8 - 12900142229635/143327232*t^9 + O(t^10)
sage: timeit('q = p.sqrt()')
625 loops, best of 3: 767 µs per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 791 µs per loop
sage: timeit('q = (p^4).sqrt()')
625 loops, best of 3: 828 µs per loop
sage: PZ = ZZ[['t']]
sage: timeit('q = (PZ(p)^2).sqrt()')
<BOOM>
sage: p = 9 - 33*t - 13*t^2 - 155*t^3 - 429*t^4 - 137*t^5 + 170*t^6 +
81*t^7 - 132*t^8 + 179*t^9
sage: timeit('q = p.sqrt()')
625 loops, best of 3: 1 ms per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 1.04 ms per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 1.04 ms per loop
}}}
With the patch:
{{{
# Basic arithmetic
sage: R.<x> = ZZ[[]]
sage: timeit('a=1/(1+x)')
625 loops, best of 3: 897 µs per loop
sage: timeit('a=1/x')
625 loops, best of 3: 173 µs per loop
sage: timeit('a=(1+x)/x')
625 loops, best of 3: 179 µs per loop
sage: timeit('a=1/(1+x)')
625 loops, best of 3: 911 µs per loop
sage: timeit('a=(1+x)/(1-x)')
625 loops, best of 3: 900 µs per loop
sage: y = (3*x+2)/(1+x)
sage: y=y/x
sage: z = (x+x^2+1)/(1+x^4+2*x^3+4*x)
sage: z=y/x
sage: timeit('y+z')
625 loops, best of 3: 38.4 µs per loop
sage: timeit('y*z')
625 loops, best of 3: 23.6 µs per loop
sage: timeit('y-z')
625 loops, best of 3: 23.6 µs per loop
sage: timeit('y/z')
625 loops, best of 3: 309 µs per loop
# square roots
sage: P.<t> = QQ[[]]
sage: p = 9 - 33*t - 13*t^2 - 155*t^3 - 429*t^4 - 137*t^5 + 170*t^6 +
81*t^7 - 132*t^8 + 179*t^9 + O(t^10)
sage: p.sqrt()
3 - 11/2*t - 173/24*t^2 - 5623/144*t^3 - 174815/1152*t^4 -
8187925/20736*t^5 - 12112939/9216*t^6 - 7942852751/1492992*t^7 -
1570233970141/71663616*t^8 - 12900142229635/143327232*t^9 + O(t^10)
sage: timeit('q = p.sqrt()')
625 loops, best of 3: 938 µs per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 962 µs per loop
sage: timeit('q = (p^4).sqrt()')
625 loops, best of 3: 1 ms per loop
sage: PZ = ZZ[['t']]
sage: timeit('q = (PZ(p)^2).sqrt()')
125 loops, best of 3: 2.39 ms per loop
sage: p = 9 - 33*t - 13*t^2 - 155*t^3 - 429*t^4 - 137*t^5 + 170*t^6 +
81*t^7 - 132*t^8 + 179*t^9
sage: timeit('q = p.sqrt()')
625 loops, best of 3: 1.22 ms per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 1.26 ms per loop
}}}
So, in some cases the patch brings a big speedup (such as 38.4 µs versus
167 µs), in other cases it brings a mild slowdown (such as 962 µs versus
791 µs)
Obvious question to the referee: Should I try to squeeze even more µs out
of it, or can it stay as it is (assuming that the long tests pass, as I
will try now).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8972#comment:40>
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.
