#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 |
-------------------------------+-------------------------------------------
Changes (by pbruin):
* status: needs_review => needs_work
* reviewer: Francis Clarke => Francis Clarke, Peter Bruin
Comment:
The patch did not apply anymore due to the fact that the `pari()` method
was renamed to `_pari_()`. I fixed this, and then did the following
(inspired by the new doctest):
{{{
#!python
def test_native():
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 test_pari():
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 = bool(a._pari_().issquare())
}}}
I got the following timings:
{{{
sage: %timeit test_native()
1 loops, best of 3: 3.11 s per loop
sage: %timeit test_pari()
1 loops, best of 3: 2.98 s per loop
}}}
From the perspective of someone who does not want to reinvent the wheel,
this suggests that we should just call PARI instead of using a native Sage
implementation.
--
Ticket URL: <http://trac.sagemath.org/ticket/13596#comment:8>
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.
