#9882: slow random_element() for integer mod ring
-------------------------------+-------------------
Reporter: dmharvey | Owner: tbd
Type: defect | Status: new
Priority: major | Milestone:
Component: performance | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
-------------------------------+-------------------
Comment (by mmezzarobba):
Other option (no time to clean it up):
{{{
diff --git a/src/sage/rings/finite_rings/integer_mod.pxd
b/src/sage/rings/finite_rings/integer_mod.pxd
index 8067647..358c902 100644
--- a/src/sage/rings/finite_rings/integer_mod.pxd
+++ b/src/sage/rings/finite_rings/integer_mod.pxd
@@ -17,6 +17,7 @@ cdef class IntegerMod_abstract(FiniteRingElement):
cdef _new_c_from_long(self, long value)
cdef void set_from_mpz(self, mpz_t value)
cdef void set_from_long(self, long value)
+ cdef void _randomize(self)
cdef bint is_square_c(self) except -2
cpdef bint is_one(self)
cpdef bint is_unit(self)
diff --git a/src/sage/rings/finite_rings/integer_mod.pyx
b/src/sage/rings/finite_rings/integer_mod.pyx
index a5d3209..bfb121a 100644
--- a/src/sage/rings/finite_rings/integer_mod.pyx
+++ b/src/sage/rings/finite_rings/integer_mod.pyx
@@ -1,3 +1,4 @@
+# cython: profile=True
r"""
Elements of `\ZZ/n\ZZ`
@@ -69,6 +70,8 @@ TESTS::
include "sage/ext/interrupt.pxi" # ctrl-c interrupt block support
include "sage/ext/stdsage.pxi"
+include "sage/ext/gmp.pxi"
+include "sage/ext/random.pxi"
from cpython.int cimport *
from cpython.list cimport *
@@ -185,6 +188,13 @@ def IntegerMod(parent, value):
else:
return IntegerMod_gmp(parent, value)
+def random_IntegerMod(parent):
+ # TODO: implement and use element_class instead?
+ cdef IntegerMod_abstract zero = parent.zero_element()
+ cdef IntegerMod_abstract tmp = zero._new_c_from_long(0)
+ tmp._randomize()
+ return tmp
+
def is_IntegerMod(x):
"""
Return ``True`` if and only if x is an integer modulo
@@ -322,6 +332,9 @@ cdef class IntegerMod_abstract(FiniteRingElement):
cdef void set_from_long(self, long value):
raise NotImplementedError, "Must be defined in child class."
+ cdef void _randomize(self):
+ pass # FIXME
+
def __abs__(self):
"""
Raise an error message, since ``abs(x)`` makes no sense
@@ -1706,6 +1719,9 @@ cdef class IntegerMod_gmp(IntegerMod_abstract):
if value < 0 or mpz_cmp_si(self.__modulus.sageInteger.value,
value) >= 0:
mpz_mod(self.value, self.value,
self.__modulus.sageInteger.value)
+ cdef void _randomize(self):
+ mpz_urandomm(self.value, current_randstate().gmp_state,
self.__modulus.sageInteger.value)
+
cdef mpz_t* get_value(IntegerMod_gmp self):
return &self.value
diff --git a/src/sage/rings/finite_rings/integer_mod_ring.py
b/src/sage/rings/finite_rings/integer_mod_ring.py
index 3ed643b..c11db8a 100644
--- a/src/sage/rings/finite_rings/integer_mod_ring.py
+++ b/src/sage/rings/finite_rings/integer_mod_ring.py
@@ -1224,10 +1224,10 @@ class
IntegerModRing_generic(quotient_ring.QuotientRing_generic):
sage: R.random_element()
2
"""
- if not (bound is None):
+ if bound is None:
+ return integer_mod.random_IntegerMod(self)
+ else:
return commutative_ring.CommutativeRing.random_element(self,
bound)
- a = random.randint(0,self.order()-1)
- return self(a)
#######################################################
# Suppose for interfaces
}}}
{{{
sage: %timeit R.random_element()
1000000 loops, best of 3: 609 ns per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/9882#comment:5>
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/d/optout.
