#13596: Improvements to IntegerMod is_square
-------------------------------------+-------------------------------------
Reporter: roed | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.12
Component: basic arithmetic | Resolution:
Keywords: | Merged in:
Authors: David Roe, Peter | Reviewers: Francis Clarke, Peter
Bruin | Bruin
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #15193 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by pbruin):
Again some timings:
{{{
a = 176338465705
b = 161089773287
n = 217267613611
def test1():
for p,q,r in cartesian_product_iterator([[3,5],[11,13],[17,19]]):
for ep,eq,er in
cartesian_product_iterator([[0,1,2,3],[0,1,2,3],[0,1,2,3]]):
for e2 in [0,1,2,3,4]:
n = p^ep*q^eq*r^er*2^e2
for _ in range(2):
a = Zmod(n).random_element()
b = a.is_square()
def test2(bound):
for n in xrange(bound):
for a in xrange(n):
b = Mod(a, n).is_square()
# without patch
sage: %timeit -c -n 100000 -r 1 Zmod(n)(a).is_square()
100000 loops, best of 1: 11.5 us per loop
sage: %timeit -c -n 100000 -r 1 Zmod(n)(b).is_square()
100000 loops, best of 1: 9.64 us per loop
sage: %timeit -c -r 1 test1()
1 loops, best of 1: 1.27 s per loop
sage: %timeit -c -r 1 test2(1000)
1 loops, best of 1: 7.12 s per loop
# with patch
sage: %timeit -c -n 100000 -r 1 Zmod(n)(a).is_square()
100000 loops, best of 1: 12.1 us per loop
sage: %timeit -c -n 100000 -r 1 Zmod(n)(b).is_square()
100000 loops, best of 1: 6.52 us per loop
sage -t --long sage/rings/finite_rings/integer_mod.pyx
cpu time: 7.8 seconds
sage: %timeit -c -r 1 test1()
1 loops, best of 1: 1.28 s per loop
sage: %timeit -c -r 1 test2(1000)
1 loops, best of 1: 6.84 s per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/13596#comment:17>
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.
