#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):
Here are some timings (on Linux x86_64):
{{{
a = 176338465705
b = 161089773287
n = 217267613611
issquare(Mod(a, n)) resp. Zmod(n)(a).is_square()
pari 2.5.4: 367 us
pari 2.6.1: 396 us
sage 5.11.rc0: 8.74 us
sage + #13596: 25 us
issquare(Mod(b, n)) resp. Zmod(n)(b).is_square()
pari 2.5.4: 1.18 us
pari 2.6.1: 155 us
sage 5.11.rc0: 15.2 us
sage + #13596: 10.6 us
kronecker(a, n) resp. a.jacobi(n)
pari 2.5.4: 0.960 us
pari 2.6.1: 0.961 us
sage 5.11.rc0: 0.693 us
kronecker(b, n) resp. b.jacobi(n)
pari 2.5.4: 0.970 us
pari 2.6.1: 0.981 us
sage 5.11.rc0: 0.709 us
factorint(n) resp. n.factor()
pari 2.5.4: 360 us
pari 2.6.1: 330 us
sage 5.11.rc0: 157 us
}}}
Note:
- almost all the time for `issquare` in PARI is spent on factoring `n`
(see above);
- there is a dramatic slowdown between PARI 2.5.4 and 2.6.1 for
`issquare(Mod(b, n))`, which should be reported to the PARI developers;
- Kronecker symbols and factoring are faster in Sage than in PARI for this
value of ''n''; this is because Sage uses the right pre-invented wheel
(GMP resp. Flint).
- this patch slows down the Sage function by a factor of 3 for ''a'' mod
''n'', but speeds it up by 30% for ''b'' mod ''n''.
--
Ticket URL: <http://trac.sagemath.org/ticket/13596#comment:13>
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.
