#20693: Sage crashes when inverting/dividing large number field elements
-------------------------------------+-------------------------------------
Reporter: ehlen | Owner:
Type: defect | Status: needs_review
Priority: critical | Milestone: sage-7.3
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: Stephan Ehlen | Reviewers: Peter Bruin
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/pbruin/20693-sage_crashes_when_computing_newforms|
eb3da684a613c81294dec6eff22972152950790f
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Stephan Ehlen', 'oldvalue': u'Stephan Ehlen, Peter
Bruin'}):
* reviewer: => Peter Bruin
* author: Stephan Ehlen, Peter Bruin => Stephan Ehlen
Comment:
Replying to [comment:45 ehlen]:
> @pbruin I can remove the doctest.
> What I really miss in sage is some more unit tests that would check many
many cases and maybe even some random cases to work that should be
separate from the doctests but this should be discussed elsewhere.
Yes, it might make sense to have a place for tests that are too long to
write down or take too much time to run. I agree that this is not the
place to discuss this further.
> If you agree that simplifying {{{_div_()}}} makes sense, I could push
both changes at any time.
> (I made some randomized tests and I don't see a performance advantage of
the currently duplicated code versus the suggested simplification.)
I included your commit in my branch and added a reviewer commit
(typographical fixes and using `x.__invert__` by the shorter and faster
`~x`, which does not require a method name lookup). I did not try any
timings myself, but can imagine that this simplification makes no
practical difference (the running time is probably dominated by the
extended GCD computation).
> Also, did you check very carefully that removing those additional
multiplications that used to be done in {{{_invert_c()}}} do not cause any
trouble anywhere?
Here is a proof that the simplified code is correct. Suppose our number
field ''K'', is '''Q'''[''X'']/(''f'') where we may assume without loss of
generality that ''f'' is in '''Z'''[''X'']. We want to invert ''x'' =
(''g'' mod ''f'')/''d'' in ''K'', where ''g'' is in '''Z'''[''X''] and is
coprime to ''f'', and where ''d'' is in '''Z''' and non-zero. We call
`XGCD(e, h, t, g, f)`; then ''e'' is the resultant of ''g'' and ''f'' (a
non-zero integer) and ''h'', ''t'' are in '''Z'''[''X''] satisfying ''e''
= ''hg + tf''. Modulo ''f'', this becomes (''h'' mod ''f'')(''g'' mod
''f'') = ''e'' in ''K'', and hence 1/''x'' = ''d''/(''g'' mod ''f'') =
((''h'' mod ''f'')''d'')/''e''. The right-hand is precisely what is
computed by the simplified version of the code. I assume that the
previous version resulted in an equivalent, but less often reduced,
fraction.
> I wonder how someone could even come up with this.... could it really be
that there was really no reason at all for this??? (This is exactly why I
think there should be (even) more (complex) testing in sage.)
Yes, this could very well be; it is surprising how often one runs into
code that is much more complicated than necessary...
It now seems to makes more sense to me to be the reviewer instead of an
author. I am now running doctests. Maybe it is still good if someone
else takes a look at this; these number field operations are after all
essential and heavily used...
--
Ticket URL: <http://trac.sagemath.org/ticket/20693#comment:48>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
