#8972: Inversion and fraction fields for power series rings
-----------------------------------------------------+----------------------
Reporter: SimonKing | Owner:
Type: defect | Status:
needs_review
Priority: major | Milestone: sage-5.0
Component: algebra | Resolution:
Keywords: power series ring, fraction field | Work issues:
Report Upstream: N/A | Reviewers: Robert
Bradshaw
Authors: Simon King | Merged in:
Dependencies: | Stopgaps:
-----------------------------------------------------+----------------------
Changes (by SimonKing):
* status: needs_work => needs_review
Old description:
> This ticket is about at least three bugs related with inversion of
> elements of power series rings.
>
> Here is the first:
> {{{
> sage: R.<x> = ZZ[[]]
> sage: (1/x).parent()
> Laurent Series Ring in x over Integer Ring
> sage: (x/x).parent()
> Power Series Ring in x over Integer Ring
> }}}
> ''Both'' parents are wrong. Usually, the parent of ``a/b`` is the
> fraction field of the parent of ``a,b``, even if ``a==b``. And neither
> above parent is a field.
>
> Next bug:
> {{{
> sage: (1/(2*x)).parent()
> ERROR: An unexpected error occurred while tokenizing input
> The following traceback may be corrupted or invalid
> The error message is: ('EOF in multi-line statement', (919, 0))
>
> ---------------------------------------------------------------------------
> TypeError Traceback (most recent call
> last)
> ... very long traceback
> TypeError: no conversion of this rational to integer
> }}}
>
> And the third:
> {{{
> sage: F = FractionField(R)
> sage: 1/x in F
> False
> }}}
New description:
This ticket is about at least three bugs related with inversion of
elements of power series rings.
Here is the first:
{{{
sage: R.<x> = ZZ[[]]
sage: (1/x).parent()
Laurent Series Ring in x over Integer Ring
sage: (x/x).parent()
Power Series Ring in x over Integer Ring
}}}
''Both'' parents are wrong. Usually, the parent of ``a/b`` is the fraction
field of the parent of ``a,b``, even if ``a==b``. And neither above parent
is a field.
Next bug:
{{{
sage: (1/(2*x)).parent()
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (919, 0))
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
... very long traceback
TypeError: no conversion of this rational to integer
}}}
And the third:
{{{
sage: F = FractionField(R)
sage: 1/x in F
False
}}}
__Apply__:
* [attachment:trac-8972_fraction_of_power_series_combined.patch]
--
Comment:
I have rebased the patch. The test suite needs to be run, but the patch
should now apply to sage-5.0.beta10. Here is some supporting evidence:
'''__First section: The bugs to be fixed__'''
''sage-5.0.beta10-gcc without the patch''
{{{
sage: R.<x> = ZZ[[]]
sage: (1/x).parent() # bug
Laurent Series Ring in x over Integer Ring
sage: (x/x).parent() # bug
Power Series Ring in x over Integer Ring
sage: (1/(2*x)).parent() # bug
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer
sage: F = FractionField(R)
sage: 1/x in F # bug
False
sage: F # I think a Laurent series ring would be better
Fraction Field of Power Series Ring in x over Integer Ring
sage: F(x)
x
sage: ~F(x) # was a problem with an early form of my patches.
1/x
}}}
''sage-5.0.beta10-gcc with the patch''
{{{
age: R.<x> = ZZ[[]]
sage: (1/x).parent() # bug fixed
Laurent Series Ring in x over Rational Field
sage: (x/x).parent() # bug fixed
Laurent Series Ring in x over Rational Field
sage: (1/(2*x)).parent() # bug fixed
Laurent Series Ring in x over Rational Field
sage: F = FractionField(R)
sage: 1/x in F # bug fixed
True
sage: F # I think that's much better!
Laurent Series Ring in x over Rational Field
sage: F(x)
x
sage: ~F(x) # new bug avoided
x^-1
}}}
'''__Second section: Timings__'''
Here I am collecting the examples that were studied in the comments above.
''sage-5.0.beta10-gcc without the patch''
{{{
sage: R.<x> = ZZ[[]]
sage: timeit('a=1/(1+x)')
625 loops, best of 3: 445 µs per loop
sage: timeit('a=1/x')
625 loops, best of 3: 283 µs per loop
sage: timeit('a=(1+x)/x')
625 loops, best of 3: 290 µs per loop
sage: timeit('a=(1+x)/(1-x)')
625 loops, best of 3: 450 µ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: 104 µs per loop
sage: timeit('y*z')
625 loops, best of 3: 76.2 µs per loop
sage: timeit('y-z')
625 loops, best of 3: 103 µs per loop
sage: timeit('y/z') # bug
Traceback (most recent call last):
...
ArithmeticError: division not defined
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: 810 µs per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 829 µs per loop
sage: timeit('q = (p^4).sqrt()')
625 loops, best of 3: 890 µs per loop
sage: PZ = ZZ[['t']]
sage: timeit('q = (PZ(p)^2).sqrt()') # bug
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (2017, 0))
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer
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()')
125 loops, best of 3: 1.07 ms per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 1.12 ms per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 1.12 ms per loop
}}}
''sage-5.0.beta10-gcc with the patch''
{{{
sage: R.<x> = ZZ[[]]
sage: timeit('a=1/(1+x)')
625 loops, best of 3: 506 µs per loop
sage: timeit('a=1/x')
625 loops, best of 3: 153 µs per loop
sage: timeit('a=(1+x)/x')
625 loops, best of 3: 160 µs per loop
sage: timeit('a=(1+x)/(1-x)')
625 loops, best of 3: 516 µ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: 37.8 µs per loop
sage: timeit('y*z')
625 loops, best of 3: 26.9 µs per loop
sage: timeit('y-z')
625 loops, best of 3: 20.6 µs per loop
sage: timeit('y/z') # bug fixed
625 loops, best of 3: 277 µs per loop
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: 847 µs per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 872 µs per loop
sage: timeit('q = (p^4).sqrt()')
625 loops, best of 3: 932 µs per loop
sage: PZ = ZZ[['t']]
sage: timeit('q = (PZ(p)^2).sqrt()') # bug fixed
125 loops, best of 3: 1.46 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.11 ms per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 1.17 ms per loop
sage: timeit('q = (p^2).sqrt()')
625 loops, best of 3: 1.17 ms per loop
}}}
I think, given that various bugs are fixed, and I think the timings tend
to be better (not in all examples, but it seems to me that the loss is
less than the gain), I guess it is "needs review", modulo doc test suite.
Apply trac-8972_fraction_of_power_series_combined.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8972#comment:46>
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.
