#13596: Improvements to IntegerMod is_square
-------------------------------+-------------------------------------------
Reporter: roed | Owner: AlexGhitza
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.12
Component: basic | Resolution:
arithmetic | Merged in:
Keywords: | Reviewers: Francis Clarke, Peter Bruin
Authors: David Roe | Work issues:
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: #12415 |
-------------------------------+-------------------------------------------
Comment (by pbruin):
Replying to [comment:10 fwclarke]:
> Replying to [comment:8 pbruin]:
>
> The following case makes me think that the examples in the doctest are
rather too small to rely on for timing information.
> It certainly looks as though PARI checks the Jacobi symbol first, but
even without the patch the current code wins. Perhaps it is worth
reinventing this wheel.
What is behind this is that Sage caches the factorisation of ''n'' in
`Zmod(n)`, while PARI has to factor `n` every time. With your values of
`a` and `n`, the PARI version used by Sage on my system needs 367 us for
`issquare(Mod(a, n))`, while `factor(n)` takes 360 us. This means that
98% of the cost of `issquare()` in this case is spent on factoring `n`.
So for a single call, PARI is probably slightly faster, while the Sage
implementation is faster for multiple calls within one `Zmod(n)` thanks to
the cached factorisation.
--
Ticket URL: <http://trac.sagemath.org/ticket/13596#comment:12>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
