#5627: [with patch, needs review] Trivial typo in quadratic_nonresidue
-----------------------------+----------------------------------------------
Reporter: kcrisman | Owner: justin
Type: defect | Status: new
Priority: trivial | Milestone: sage-3.4.1
Component: quadratic forms | Keywords:
-----------------------------+----------------------------------------------
Comment(by mvngu):
Here's a trivial observation on performance. Look at the line
{{{
247 for r in range(2,p):
}}}
With the patch as is, on sage.math I get the following timings:
{{{
# BEFORE
sage: p = 179424673
sage: time quadratic_nonresidue(p)
CPU times: user 9.07 s, sys: 4.37 s, total: 13.44 s
Wall time: 13.44 s
5
sage: timeit("quadratic_nonresidue(p)")
5 loops, best of 3: 19.3 s per loop
}}}
Now if I change the said line to
{{{
247 for r in xrange(2,p):
}}}
I get some performance improvement:
{{{
# AFTER
sage: p = 179424673
sage: time quadratic_nonresidue(p)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
5
sage: timeit("quadratic_nonresidue(p)")
625 loops, best of 3: 36.6 µs per loop
}}}
However, in both cases whether we use {{{range()}}} or {{{xrange()}}}, if
p is say 88462514817229869523, then I get the following error for
{{{range()}}}:
{{{
sage: p = 88462514817229869523
sage: quadratic_nonresidue(p)
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
/home/mvngu/.sage/temp/sage.math.washington.edu/14179/_home_mvngu__sage_init_sage_0.py
in <module>()
/scratch/mvngu/sage-3.4.1.alpha0-sage.math-
only-x86_64-Linux/local/lib/python2.5/site-
packages/sage/quadratic_forms/extras.pyc in quadratic_nonresidue(p)
245 ## Find the smallest non-residue mod p
246 try:
--> 247 for r in range(2,p):
248 if legendre_symbol(r, p) == -1:
249 return r
TypeError: range() integer end argument expected, got
sage.rings.integer.Integer.
}}}
And for {{{xrange()}}}, I get a similar error, but this time it's an
{{{OverflowError}}}:
{{{
sage: p = 88462514817229869523
sage: quadratic_nonresidue(p)
---------------------------------------------------------------------------
OverflowError Traceback (most recent call
last)
/home/mvngu/.sage/temp/sage.math.washington.edu/14262/_home_mvngu__sage_init_sage_0.py
in <module>()
/scratch/mvngu/sage-3.4.1.alpha0-sage.math-
only-x86_64-Linux/local/lib/python2.5/site-
packages/sage/quadratic_forms/extras.pyc in quadratic_nonresidue(p)
245 ## Find the smallest non-residue mod p
246 try:
--> 247 for r in xrange(2,p):
248 if legendre_symbol(r, p) == -1:
249 return r
OverflowError: long int too large to convert to int
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5627#comment:2>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
