optimize valuation(2) using trailing_zero_bits

[user202729]

Problem Description

as in the title.

Proposed Solution

Maybe this will work

diff --git a/src/sage/rings/integer.pxd b/src/sage/rings/integer.pxd
index c113d562835..641103473d1 100644
--- a/src/sage/rings/integer.pxd
+++ b/src/sage/rings/integer.pxd
@@ -1,4 +1,4 @@
-from sage.libs.gmp.types cimport __mpz_struct, mpz_t, mpz_ptr
+from sage.libs.gmp.types cimport __mpz_struct, mpz_t, mpz_ptr, mp_bitcnt_t
 from sage.libs.gmp.mpz cimport mpz_set
 
 from sage.structure.element cimport EuclideanDomainElement, RingElement
@@ -22,6 +22,7 @@ cdef class Integer(EuclideanDomainElement):
     cdef _and(Integer self, Integer other)
     cdef _or(Integer self, Integer other)
     cdef _xor(Integer self, Integer other)
+    cpdef mp_bitcnt_t trailing_zero_bits(self)
 
     cpdef size_t _exact_log_log2_iter(self, Integer m) noexcept
     cpdef size_t _exact_log_mpfi_log(self, m) noexcept
diff --git a/src/sage/rings/integer.pyx b/src/sage/rings/integer.pyx
index 88411985660..70e3e07ca66 100644
--- a/src/sage/rings/integer.pyx
+++ b/src/sage/rings/integer.pyx
@@ -1343,7 +1344,7 @@ cdef class Integer(sage.structure.element.EuclideanDomainElement):
         """
         return self.bit_length()
 
-    def trailing_zero_bits(self):
+    cpdef mp_bitcnt_t trailing_zero_bits(self):
         """
         Return the number of trailing zero bits in ``self``, i.e.
         the exponent of the largest power of 2 dividing ``self``.
@@ -1360,10 +1361,15 @@ cdef class Integer(sage.structure.element.EuclideanDomainElement):
             5
             sage: 0.trailing_zero_bits()
             0
+
+        TESTS::
+
+            sage: type(0.trailing_zero_bits())
+            int
         """
         if mpz_sgn(self.value) == 0:
-            return int(0)
-        return int(mpz_scan1(self.value, 0))
+            return 0
+        return mpz_scan1(self.value, 0)
 
     def digits(self, base=10, digits=None, padto=0):
         r"""
@@ -4235,8 +4241,11 @@ cdef class Integer(sage.structure.element.EuclideanDomainElement):
         """
         if mpz_sgn(self.value) == 0:
             return sage.rings.infinity.infinity
-        if mpz_cmp_ui(p.value, 2) < 0:
+        cmp2 = mpz_cmp_ui(p.value, 2)
+        if cmp2 < 0:
             raise ValueError("You can only compute the valuation with respect to a integer larger than 1.")
+        if cmp2 == 0:
+            return smallInteger(self.trailing_zero_bits())
 
         cdef Integer v = PY_NEW(Integer)
         cdef mpz_t u

most of the work left is in benchmarking and inspecting whether the generated assembly is as expected i.e. doesn't use Python API where unnecessary.

possible benchmark code

%%cython --view-annotate
from sage.rings.integer cimport Integer, smallInteger
from sage.libs.gmp.mpz cimport mpz_scan1
cpdef int valuation2(Integer a):
	return mpz_scan1(a.value, 0)
cpdef int valuation2b(Integer a):
	return a.trailing_zero_bits()
##

a = 3**50000*2**100000
b = 2
%timeit -n50000 a.valuation(b)
%timeit -n50000 a.trailing_zero_bits()

%timeit -n50000 valuation2(a)
%timeit -n50000 valuation2b(a)

Alternatives Considered

Additional Information

No response

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.