#13596: Improvements to IntegerMod is_square
-------------------------------+-------------------------------------------
Reporter: roed | Owner: AlexGhitza
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-pending
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 fwclarke):
Replying to [comment:8 pbruin]:
> I got the following timings:
The following case makes me think that the examples in the doctest are
rather too small to rely on for timing information.
{{{
sage: print version()
Sage Version 5.10, Release Date: 2013-06-17
sage: a, b, n = 176338465705, 161089773287, 217267613611
sage: n.factor()
341983 * 635317
sage: jacobi_symbol(a, n), jacobi_symbol(b, n)
(1, -1)
sage: %timeit Zmod(n)(a).is_square()
100000 loops, best of 3: 10.2 us per loop
sage: %timeit Zmod(n)(a)._pari_().issquare()
1000 loops, best of 3: 215 us per loop
sage: %timeit Zmod(n)(b).is_square()
100000 loops, best of 3: 8.83 us per loop
sage: %timeit Zmod(n)(b)._pari_().issquare()
100000 loops, best of 3: 14.8 us per loop
}}}
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/13596#comment:10>
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.
