Changeset 6448:1b6661884ccf

Timestamp:

09/20/07 16:01:22 (6 years ago)

Author:

Robert Bradshaw <robertwb@…>

Branch:

default

Message:

Fast range function for integers

Location:

sage

Files:

• misc/misc.py (modified) (3 diffs)
• rings/integer_ring.pyx (modified) (3 diffs)

sage/misc/misc.py

@@ -622 +622 @@
     
 #################################################################
-# Used for [1,2,..,n] notation. 
+# Ranges and [1,2,..,n] notation. 
 #################################################################
 
@@ -635 +635 @@
         return range(start, end, step)
     elif universe is ZZ:
-        return srange(start, end, step)
+        return ZZ.range(start, end, step)
     else:
         L = []
+        if (end-start)/step <= 0:
+            return L
         while start < end:
             L.append(start)
@@ -656 +658 @@
         return xsrange(start, end, step)
     else:
-        L = []
-        while start < end:
-            L.append(start)
-            start += step
-        return L
+        return generic_xurange(start, end, step)
         
 def generic_xurange(start, end, step):
+    if (end-start)/step <= 0:
+        return
     while start < end:
         yield start

sage/rings/integer_ring.pyx

@@ +1 @@
+
 r"""
 \protect{Ring $\Z$ of Integers}
@@ -62 +63 @@
 include "../ext/random.pxi"
 
+include "../ext/python_int.pxi"
+include "../ext/python_list.pxi"
+
 import sage.rings.infinity
 import sage.rings.rational
@@ -218 +222 @@
                 pass
         raise TypeError, msg
+        
+    def range(self, start, end=None, step=None):
+        """
+        Optimized range function for SAGE integer. 
+        
+        AUTHOR: 
+          -- Robert Bradshaw (2007-09-20)
+        
+        EXAMPLES: 
+            sage: ZZ.range(10)
+            [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+            sage: ZZ.range(-5,5)
+            [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4]
+            sage: ZZ.range(0,50,5)
+            [0, 5, 10, 15, 20, 25, 30, 35, 40, 45]
+            sage: ZZ.range(0,50,-5)
+            []
+            sage: ZZ.range(50,0,-5)
+            [50, 45, 40, 35, 30, 25, 20, 15, 10, 5]
+            sage: ZZ.range(50,0,5)
+            []
+            sage: ZZ.range(50,-1,-5)
+            [50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 0]
+            
+        It uses different code if the step doesn't fit in a long: 
+            sage: ZZ.range(0,2^83,2^80)
+            [0, 1208925819614629174706176, 2417851639229258349412352, 3626777458843887524118528, 4835703278458516698824704, 6044629098073145873530880, 7253554917687775048237056, 8462480737302404222943232]
+        """
+        if end is None:
+            end = start
+            start = PY_NEW(Integer) # 0
+        if step is None:
+            step = 1
+        if not PyInt_CheckExact(step):
+            if not PY_TYPE_CHECK(step, integer.Integer):
+                step = integer.Integer(step)
+            if mpz_fits_slong_p((<Integer>step).value):
+                step = int(step)
+        if not PY_TYPE_CHECK(start, integer.Integer):
+            start = integer.Integer(start)
+        if not PY_TYPE_CHECK(end, integer.Integer):
+            start = integer.Integer(end)
+        cdef integer.Integer a = <Integer>start
+        cdef integer.Integer b = <Integer>end
+        
+        cdef int step_sign
+        cdef long istep
+        cdef integer.Integer zstep, last
+        
+        L = []
+        if PyInt_CheckExact(step):
+            istep = PyInt_AS_LONG(step)
+            step_sign = istep
+        else:
+            zstep = <Integer>step
+            step_sign = mpz_sgn(zstep.value)
+            
+        _sig_on
+        while mpz_cmp(a.value, b.value)*step_sign < 0:
+            last = a
+            a = PY_NEW(Integer)
+            if PyInt_CheckExact(step): # count on branch prediction...
+                if istep > 0:
+                    mpz_add_ui(a.value, last.value, istep)
+                else:
+                    mpz_sub_ui(a.value, last.value, -istep)
+            else:
+                mpz_add(a.value, last.value, zstep.value)
+            PyList_Append(L, last)
+        _sig_off
+        return L
 
     def __iter__(self):