#2943: [with patch, not ready for review] bug with power series and/or p-adics
---------------------------------------------+------------------------------
Reporter: jen | Owner: was
Type: defect | Status: new
Priority: critical | Milestone: sage-3.4.1
Component: number theory | Resolution:
Keywords: power series, p-adic extensions |
---------------------------------------------+------------------------------
Comment (by kedlaya):
Replying to [comment:18 dmharvey]:
> Replying to [comment:17 kedlaya]:
> > I think multiplication here uses z._mul_karatsuba, so maybe dmharvey
needs to look at this again. Karatsuba may cause problems when working
over an inexact coefficient ring.
>
> I don't know who wrote the karatsuba code. I think it was there long
before I started working on sage. Sure, I agree karatsuba should give
inaccurate answers over an inexact coefficient ring, but it shouldn't give
*wrong* answers. I guess the easiest solution is just to disable or remove
karatsuba altogether, or first check whether the coefficient ring is
exact.
>
> david
Fair enough, but the behavior of `__invert__` (in
sage/sage/rings/power_series_ring_element.pyx; I believe you wrote this)
seems to depend on Karatsuba giving better answers than this. Here's what
happens when I go through `__invert__` by hand:
{{{
sage: sage: y = 1 - (t + O(t^2))*s + O(s^5)
sage: C.<t> = PowerSeriesRing(Integers())
sage: D.<s> = PowerSeriesRing(C)
sage: y = 1 - (t + O(t^2))*s + O(s^5)
sage: sage.misc.misc.newton_method_sizes(5)
[1, 2, 3, 5]
sage: A = y.truncate()
sage: current = A.parent()(1)
sage: current
1
sage: z = current.square() * A.truncate(1)
sage: current = 2*current - z.truncate(1)
sage: current
1
sage: z = current.square() * A.truncate(2)
sage: current = 2*current - z.truncate(2)
sage: current
(t + O(t^2))*s + 1
sage: z = current.square() * A.truncate(3)
sage: current = 2*current - z.truncate(3)
sage: current
(t^2 + O(t^3))*s^2 + (t + O(t^2))*s + 1
sage: z = current.square() * A.truncate(5)
sage: z.list()
[1, t + O(t^2), O(t^2), O(t^3), O(t^4), -t^5 + O(t^6)]
sage: current = 2*current - z.truncate(5)
sage: current
(2*t^2 + O(t^3))*s^2 + (t + O(t^2))*s + 1
}}}
My previous example is the `last current.square()` in this sequence, which
gives an answer with too little precision. This would be consistent, if
undesirable, except for the fact that here:
{{{
sage: z.list()
[1, t + O(t^2), O(t^2), O(t^3), O(t^4), -t^5 + O(t^6)]
sage: z.truncate(5).list()
[1, t + O(t^2)]
}}}
I lose the extra `O(t^*)` terms at the end. This causes current not to get
properly degraded in its `s^2` and higher coefficients, hence the wrong
answer.
So now as I see it, there are actually two different issues.
1. Karatsuba doesn't give best possible answers over inexact rings. This
could be fixed by explicitly calling `_mul_generic` instead of implicitly
calling `_mul_karatsuba`, but that is a performance tradeoff.
2. Looking into `truncate` (in
sage.rings.polynomial.polynomial_element.Polynomial_generic_dense), one
sees that the extra terms are tested for being zero by being evaluated in
a Boolean context and then negated. This gives the same effect as
`is_zero` or comparison with 0, namely something like `O(t^4) == 0`
returns `True`. This may be the desired effect in certain contexts, but I
think we can't use it in `__invert__` even if we fix the Karatsuba thing,
since in some cases the '''correct''' behavior will involve having an
`O(t^n)` term at the end. For example, let's uninvert the example from
earlier:
{{{
sage: yy
1 + (t + O(t^2))*s + (t^2 + O(t^3))*s^2 + (t^3 + O(t^4))*s^3 + (t^4 +
O(t^5))*s^4 + O(s^5)
sage: 1/yy
1 + (-t + O(t^2))*s + O(s^5)
sage: (1/yy).list()
[1, -t + O(t^2)]
}}}
This is wrong because the 'zero' terms are actually inexact zeroes to
certain precisions, which will lead to errors elsewhere if you try to use
them.
This is a systemic problem with using the generic polynomial module with
an inexact ring: it has a habit of truncating leading zeroes after
virtually every arithmetic operation. This systemic problem needs a
systemic solution: there needs to be a way to check whether an element of
an inexact ring is an exact zero or not, so that `truncate` can preserve
inexact leading zeroes, i.e., a method called `is_exact_zero` or
something.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/2943#comment:20>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
