Issue of divmod, floordiv and mod operations with floor_division for some types

[mizar]

Steps To Reproduce

• https://colab.research.google.com/gist/mizar/07c293cb2a1ee4e896669335b99a6408/sagemath-divmod-issue.ipynb
• example code: https://sagecell.sagemath.org/?z=eJyFTstuwjAQvEfKPyzqZddZFBsaDiD_CsghQbUUb4rjQCTEv5eoVNzonEbz0jTtCU5d38fDMAYUhsDgGGqGyWrawgccXXeEh3m4eavv-5sszf23gug8FFATlBAoz-CB65fvWpCF1VscOBBj4pHY2cZfQt-gm7Unr2cedlNhUZQshcpypYZCVNoJ13-NoKQY2T33Y5vGKDDlWZ59Ry8JX-9XSm0-2fCaNdEbu6pKY_4JDeeY0GiaUz8nkVQq&lang=sage&interacts=eJyLjgUAARUAuQ==
• example code 2: https://sagecell.sagemath.org/?z=eJydkeEKwiAUhf8P9g6xXwqycrbHCKKeQNgqYe6ak8C3TyIzdFvST-895-N6jpAKtNmA6jU3oMlkpbJlURZKi9Gg6mzl0VbYv72uvgwAuhMP9DLUJ24EjHxArG0JpQwTislHLKFb0f0BbzLhTYA7XOYZP5T5TJat3Gcr2wXldNcG0d37I6E-fu0P3NzWGnTsrWMnjYV5hjluJMzje2ew0WbZkybqN2mCfjOT2FdWT8oe7qw=&lang=sage&interacts=eJyLjgUAARUAuQ==

Expected Behavior

• operator.floordiv(a,b) == floor(a/b) (operator.floordiv same as // operator)
• operator.mod(a,b) == a - floor(a/b)*b (operator.mod same as % operator)
• divmod(a,b) == (operator.floordiv(a,b), operator.mod(a,b))

example code:

def floor_sum(n, m, a, b, x=0): # calc sum_{i=0}^{n-1} floor((ai + b) / m)
    while n!=0:(s,m),(t,u),a=divmod(a,m),divmod(b,m),m;x+=(n*n-n)//2*s+n*t;n,b=divmod(m*n+u,a)
    return x

print(floor_sum(2**64,1,3,0))
print(floor_sum(2**64,1,355/113,0))
print(floor_sum(2**64,1,sqrt(10),0))

example code for Sympy:

def floor_sum(n, m, a, b, x=0): # calc sum_{i=0}^{n-1} floor((ai + b) / m)
    while n!=0:(s,m),(t,u),a=divmod(a,m),divmod(b,m),m;x+=(n*n-n)//2*s+n*t;n,b=divmod(m*n+u,a)
    return x

import sympy
print(floor_sum(2**64,1,3,0))
print(floor_sum(2**64,1,sympy.Rational(355,113),0))
print(floor_sum(2**64,1,sympy.sqrt(10),0))

output:

510423550381407695167391795037087989760
534514337420058205844616620158652010894
538033663531651603400662643251823957383

example code 2:

import operator,sympy

print("SymPy")
print(operator.floordiv(sympy.Rational(355,113),1),operator.mod(sympy.Rational(355,113),1))
print(operator.floordiv(sympy.Rational(355,113),2),operator.mod(sympy.Rational(355,113),2))
print(divmod(sympy.Rational(355,113),1))
print(divmod(sympy.Rational(355,113),2))
print(divmod(sympy.Rational(355,113),3))
print(divmod(sympy.Rational(355,113),4))
print(divmod(sympy.Rational(355,113),5))
print(divmod(sympy.sqrt(10),1))

print("SageMath")
print(operator.floordiv(355/113,1),operator.mod(355/113,1))
print(operator.floordiv(355/113,2),operator.mod(355/113,2))
print(divmod(355/113,1))
print(divmod(355/113,2))
print(divmod(355/113,3))
print(divmod(355/113,4))
print(divmod(355/113,5))
print(divmod(sqrt(10),1))

output:

SymPy
3 16/113
1 129/113
(3, 16/113)
(1, 129/113)
(1, 16/113)
(0, 355/113)
(0, 355/113)
(3, -3 + sqrt(10))
SageMath
...(same output)...

Actual Behavior

• sometimes operator.floordiv(a,b) != floor(a/b) (operator.floordiv same as // operator)
• sometimes operator.mod(a,b) != a - floor(a/b)*b (operator.mod same as % operator)
• sometimes divmod(a,b) != (operator.floordiv(a,b), operator.mod(a,b))
• sometimes not implemented

example code:

def floor_sum(n, m, a, b, x=0): # calc sum_{i=0}^{n-1} floor((ai + b) / m)
    while n!=0:(s,m),(t,u),a=divmod(a,m),divmod(b,m),m;x+=(n*n-n)//2*s+n*t;n,b=divmod(m*n+u,a)
    return x

print(floor_sum(2**64,1,3,0))
print(floor_sum(2**64,1,355/113,0))
print(floor_sum(2**64,1,sqrt(10),0))

output:

510423550381407695167391795037087989760
60400120128466577261474695746055412121600/113
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
File /home/sc_serv/sage/src/sage/structure/element.pyx:1871, in sage.structure.element.Element._floordiv_()
   1870 try:
-> 1871     python_op = (<object>self)._floordiv_
   1872 except AttributeError:

File /home/sc_serv/sage/src/sage/structure/element.pyx:489, in sage.structure.element.Element.__getattr__()
    488 """
--> 489 return self.getattr_from_category(name)
    490 

File /home/sc_serv/sage/src/sage/structure/element.pyx:502, in sage.structure.element.Element.getattr_from_category()
    501     cls = P._abstract_element_class
--> 502 return getattr_from_other_class(self, cls, name)
    503 

File /home/sc_serv/sage/src/sage/cpython/getattr.pyx:362, in sage.cpython.getattr.getattr_from_other_class()
    361     dummy_error_message.name = name
--> 362     raise AttributeError(dummy_error_message)
    363 attribute = <object>attr

AttributeError: 'sage.symbolic.ring.SymbolicRing' object has no attribute '_SageObject__custom_name'

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
Cell In [1], line 7
      5 print(floor_sum(Integer(2)**Integer(64),Integer(1),Integer(3),Integer(0)))
      6 print(floor_sum(Integer(2)**Integer(64),Integer(1),Integer(355)/Integer(113),Integer(0)))
----> 7 print(floor_sum(Integer(2)**Integer(64),Integer(1),sqrt(Integer(10)),Integer(0)))

Cell In [1], line 2, in floor_sum(n, m, a, b, x)
      1 def floor_sum(n, m, a, b, x=Integer(0)): # calc sum_{i=0}^{n-1} floor((ai + b) / m)
----> 2     while n!=Integer(0):(s,m),(t,u),a=divmod(a,m),divmod(b,m),m;x+=(n*n-n)//Integer(2)*s+n*t;n,b=divmod(m*n+u,a)
      3     return x

File /home/sc_serv/sage/src/sage/structure/element.pyx:2822, in sage.structure.element.RingElement.__divmod__()
   2820     except (AttributeError, NotImplementedError):
   2821         pass
-> 2822     return (self // other, self % other)
   2823 
   2824 def __invert__(self):

File /home/sc_serv/sage/src/sage/structure/element.pyx:1840, in sage.structure.element.Element.__floordiv__()
   1838     return (<Element>left)._floordiv_(right)
   1839 if BOTH_ARE_ELEMENT(cl):
-> 1840     return coercion_model.bin_op(left, right, floordiv)
   1841 
   1842 try:

File /home/sc_serv/sage/src/sage/structure/coerce.pyx:1232, in sage.structure.coerce.CoercionModel.bin_op()
   1230     self._record_exception()
   1231 else:
-> 1232     return PyObject_CallObject(op, xy)
   1233 
   1234 if op is mul:

File /home/sc_serv/sage/src/sage/structure/element.pyx:1838, in sage.structure.element.Element.__floordiv__()
   1836 cdef int cl = classify_elements(left, right)
   1837 if HAVE_SAME_PARENT(cl):
-> 1838     return (<Element>left)._floordiv_(right)
   1839 if BOTH_ARE_ELEMENT(cl):
   1840     return coercion_model.bin_op(left, right, floordiv)

File /home/sc_serv/sage/src/sage/structure/element.pyx:1873, in sage.structure.element.Element._floordiv_()
   1871     python_op = (<object>self)._floordiv_
   1872 except AttributeError:
-> 1873     raise bin_op_exception('//', self, other)
   1874 else:
   1875     return python_op(other)

TypeError: unsupported operand parent(s) for //: 'Symbolic Ring' and 'Symbolic Ring'

example code 2:

import operator,sympy

print("SymPy")
print(operator.floordiv(sympy.Rational(355,113),1),operator.mod(sympy.Rational(355,113),1))
print(operator.floordiv(sympy.Rational(355,113),2),operator.mod(sympy.Rational(355,113),2))
print(divmod(sympy.Rational(355,113),1))
print(divmod(sympy.Rational(355,113),2))
print(divmod(sympy.Rational(355,113),3))
print(divmod(sympy.Rational(355,113),4))
print(divmod(sympy.Rational(355,113),5))
print(divmod(sympy.sqrt(10),1))

print("SageMath")
print(operator.floordiv(355/113,1),operator.mod(355/113,1))
print(operator.floordiv(355/113,2),operator.mod(355/113,2))
print(divmod(355/113,1))
print(divmod(355/113,2))
print(divmod(355/113,3))
print(divmod(355/113,4))
print(divmod(355/113,5))
print(divmod(sqrt(10),1))

output:

SymPy
3 16/113
1 129/113
(3, 16/113)
(1, 129/113)
(1, 16/113)
(0, 355/113)
(0, 355/113)
(3, -3 + sqrt(10))
SageMath
355/113 0
355/226 1
(355/113, 0)
(355/226, 0)
(355/339, 0)
(355/452, 0)
(71/113, 0)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
File /home/sc_serv/sage/src/sage/structure/element.pyx:1871, in sage.structure.element.Element._floordiv_()
   1870 try:
-> 1871     python_op = (<object>self)._floordiv_
   1872 except AttributeError:

File /home/sc_serv/sage/src/sage/structure/element.pyx:489, in sage.structure.element.Element.__getattr__()
    488 """
--> 489 return self.getattr_from_category(name)
    490 

File /home/sc_serv/sage/src/sage/structure/element.pyx:502, in sage.structure.element.Element.getattr_from_category()
    501     cls = P._abstract_element_class
--> 502 return getattr_from_other_class(self, cls, name)
    503 

File /home/sc_serv/sage/src/sage/cpython/getattr.pyx:362, in sage.cpython.getattr.getattr_from_other_class()
    361     dummy_error_message.name = name
--> 362     raise AttributeError(dummy_error_message)
    363 attribute = <object>attr

AttributeError: 'sage.symbolic.ring.SymbolicRing' object has no attribute '_SageObject__custom_name'

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
Cell In [1], line 21
     19 print(divmod(Integer(355)/Integer(113),Integer(4)))
     20 print(divmod(Integer(355)/Integer(113),Integer(5)))
---> 21 print(divmod(sqrt(Integer(10)),Integer(1)))

File /home/sc_serv/sage/src/sage/structure/element.pyx:2822, in sage.structure.element.RingElement.__divmod__()
   2820     except (AttributeError, NotImplementedError):
   2821         pass
-> 2822     return (self // other, self % other)
   2823 
   2824 def __invert__(self):

File /home/sc_serv/sage/src/sage/structure/element.pyx:1840, in sage.structure.element.Element.__floordiv__()
   1838     return (<Element>left)._floordiv_(right)
   1839 if BOTH_ARE_ELEMENT(cl):
-> 1840     return coercion_model.bin_op(left, right, floordiv)
   1841 
   1842 try:

File /home/sc_serv/sage/src/sage/structure/coerce.pyx:1232, in sage.structure.coerce.CoercionModel.bin_op()
   1230     self._record_exception()
   1231 else:
-> 1232     return PyObject_CallObject(op, xy)
   1233 
   1234 if op is mul:

File /home/sc_serv/sage/src/sage/structure/element.pyx:1838, in sage.structure.element.Element.__floordiv__()
   1836 cdef int cl = classify_elements(left, right)
   1837 if HAVE_SAME_PARENT(cl):
-> 1838     return (<Element>left)._floordiv_(right)
   1839 if BOTH_ARE_ELEMENT(cl):
   1840     return coercion_model.bin_op(left, right, floordiv)

File /home/sc_serv/sage/src/sage/structure/element.pyx:1873, in sage.structure.element.Element._floordiv_()
   1871     python_op = (<object>self)._floordiv_
   1872 except AttributeError:
-> 1873     raise bin_op_exception('//', self, other)
   1874 else:
   1875     return python_op(other)

TypeError: unsupported operand parent(s) for //: 'Symbolic Ring' and 'Symbolic Ring'

Additional Information

• make divmod() work for more rings #33704
• https://docs.python.org/3/library/operator.html
• https://docs.python.org/3/library/functions.html#divmod
• https://docs.sympy.org/latest/modules/polys/domainsref.html#sympy.polys.domains.domain.Domain.div

• sage/src/sage/structure/element.pyx

  Lines 1774 to 1872 in 79c047c

  	def __floordiv__(left, right):
  	"""
  	Top-level floor division operator for :class:`Element` invoking
  	the coercion model.
  	See :ref:`element_arithmetic`.
  	EXAMPLES::
  	sage: 7 // 3
  	2
  	sage: 7 // int(3)
  	2
  	sage: int(7) // 3
  	2
  	::
  	sage: from sage.structure.element import Element
  	sage: class MyElement(Element):
  	....: def _floordiv_(self, other):
  	....: return 42
  	sage: e = MyElement(Parent())
  	sage: e // e
  	42
  	TESTS::
  	sage: e = Element(Parent())
  	sage: e // e
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand parent(s) for //: '<sage.structure.parent.Parent object at ...>' and '<sage.structure.parent.Parent object at ...>'
  	sage: 1 // e
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand parent(s) for //: 'Integer Ring' and '<sage.structure.parent.Parent object at ...>'
  	sage: e // 1
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand parent(s) for //: '<sage.structure.parent.Parent object at ...>' and 'Integer Ring'
  	sage: int(1) // e
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand type(s) for //: 'int' and 'sage.structure.element.Element'
  	sage: e // int(1)
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand type(s) for //: 'sage.structure.element.Element' and 'int'
  	sage: None // e
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand type(s) for //: 'NoneType' and 'sage.structure.element.Element'
  	sage: e // None
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand type(s) for //: 'sage.structure.element.Element' and 'NoneType'
  	"""
  	# See __add__ for comments
  	cdef int cl = classify_elements(left, right)
  	if HAVE_SAME_PARENT(cl):
  	return (<Element>left)._floordiv_(right)
  	if BOTH_ARE_ELEMENT(cl):
  	return coercion_model.bin_op(left, right, floordiv)
  	try:
  	return coercion_model.bin_op(left, right, floordiv)
  	except TypeError:
  	return NotImplemented
  	cdef _floordiv_(self, other):
  	"""
  	Virtual floor division method for elements with identical parents.
  	This default Cython implementation of ``_floordiv_`` calls the
  	Python method ``self._floordiv_`` if it exists. This method may be
  	defined in the ``ElementMethods`` of the category of the parent.
  	If the method is not found, a :class:`TypeError` is raised
  	indicating that the operation is not supported.
  	See :ref:`element_arithmetic`.
  	EXAMPLES:
  	This method is not visible from Python::
  	sage: from sage.structure.element import Element
  	sage: e = Element(Parent())
  	sage: e._floordiv_(e)
  	Traceback (most recent call last):
  	...
  	AttributeError: 'sage.structure.element.Element' object has no attribute '_floordiv_'...
  	"""
  	try:
  	python_op = (<object>self)._floordiv_
  	except AttributeError:
  	raise bin_op_exception('//', self, other)
  	else:
  	return python_op(other)

• sage/src/sage/structure/element.pyx

  Lines 1874 to 1972 in 79c047c

  	def __mod__(left, right):
  	"""
  	Top-level modulo operator for :class:`Element` invoking
  	the coercion model.
  	See :ref:`element_arithmetic`.
  	EXAMPLES::
  	sage: 7 % 3
  	1
  	sage: 7 % int(3)
  	1
  	sage: int(7) % 3
  	1
  	::
  	sage: from sage.structure.element import Element
  	sage: class MyElement(Element):
  	....: def _mod_(self, other):
  	....: return 42
  	sage: e = MyElement(Parent())
  	sage: e % e
  	42
  	TESTS::
  	sage: e = Element(Parent())
  	sage: e % e
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand parent(s) for %: '<sage.structure.parent.Parent object at ...>' and '<sage.structure.parent.Parent object at ...>'
  	sage: 1 % e
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand parent(s) for %: 'Integer Ring' and '<sage.structure.parent.Parent object at ...>'
  	sage: e % 1
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand parent(s) for %: '<sage.structure.parent.Parent object at ...>' and 'Integer Ring'
  	sage: int(1) % e
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand type(s) for %: 'int' and 'sage.structure.element.Element'
  	sage: e % int(1)
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand type(s) for %: 'sage.structure.element.Element' and 'int'
  	sage: None % e
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand type(s) for %: 'NoneType' and 'sage.structure.element.Element'
  	sage: e % None
  	Traceback (most recent call last):
  	...
  	TypeError: unsupported operand type(s) for %: 'sage.structure.element.Element' and 'NoneType'
  	"""
  	# See __add__ for comments
  	cdef int cl = classify_elements(left, right)
  	if HAVE_SAME_PARENT(cl):
  	return (<Element>left)._mod_(right)
  	if BOTH_ARE_ELEMENT(cl):
  	return coercion_model.bin_op(left, right, mod)
  	try:
  	return coercion_model.bin_op(left, right, mod)
  	except TypeError:
  	return NotImplemented
  	cdef _mod_(self, other):
  	"""
  	Virtual modulo method for elements with identical parents.
  	This default Cython implementation of ``_mod_`` calls the
  	Python method ``self._mod_`` if it exists. This method may be
  	defined in the ``ElementMethods`` of the category of the parent.
  	If the method is not found, a :class:`TypeError` is raised
  	indicating that the operation is not supported.
  	See :ref:`element_arithmetic`.
  	EXAMPLES:
  	This method is not visible from Python::
  	sage: from sage.structure.element import Element
  	sage: e = Element(Parent())
  	sage: e._mod_(e)
  	Traceback (most recent call last):
  	...
  	AttributeError: 'sage.structure.element.Element' object has no attribute '_mod_'...
  	"""
  	try:
  	python_op = (<object>self)._mod_
  	except AttributeError:
  	raise bin_op_exception('%', self, other)
  	else:
  	return python_op(other)

• sage/src/sage/structure/element.pyx

  Lines 2773 to 2837 in 79c047c

  	def __divmod__(self, other):
  	"""
  	Return the quotient and remainder of ``self`` divided by ``other``.
  	This operation may not be defined in all rings.
  	EXAMPLES::
  	sage: divmod(5,3)
  	(1, 2)
  	sage: divmod(25r,12)
  	(2, 1)
  	sage: divmod(25,12r)
  	(2, 1)
  	::
  	sage: R.<x> = QQ[]
  	sage: f = -19/13*x^5 - x^4 - 2/3*x^3 + 6*x^2 - 2
  	sage: g = 3*x^2 + 5
  	sage: q,r = divmod(f,g)
  	sage: q
  	-19/39*x^3 - 1/3*x^2 + 23/39*x + 23/9
  	sage: r
  	-115/39*x - 133/9
  	sage: f == q*g + r
  	True
  	::
  	sage: R.<x> = ZZ[]
  	sage: f = -2*x^5 + x^4 - 9*x^3 - 5*x^2 + 7*x + 4
  	sage: g = x^2 + 5
  	sage: q,r = divmod(f,g)
  	sage: q
  	-2*x^3 + x^2 + x - 10
  	sage: r
  	2*x + 54
  	sage: f == q*g + r
  	True
  	sage: h = 3*x^2 + 5
  	sage: q,r = divmod(f,h)
  	sage: q
  	-3*x - 2
  	sage: r
  	-2*x^5 + x^4 + x^2 + 22*x + 14
  	sage: f == q*h + r
  	True
  	::
  	sage: R.<x> = GF(7)[]
  	sage: divmod(x^2, x - 1)
  	(x + 1, 1)
  	::
  	sage: divmod(22./7, RR(pi)) # needs sage.symbolic
  	(1.00040249943477, 0.000000000000000)
  	"""
  	try:
  	return self.quo_rem(other)
  	except (AttributeError, NotImplementedError):
  	pass
  	return (self // other, self % other)

• https://sagecell.sagemath.org/?z=eJx1jk0OgjAQhfcm3mF2UG3QhrDhBp6iqWUITUjBmbrw9rYlGH9w-8375r0Oe7CjYdaDQzJkh0dpR5bgfIc-iHa_A5jJ-VAWVXFYqIwKi3TpJwK-z0gRRCXxSuurYWStsws_79f82nFU8VUXdzjPwXiLb9mEPjZc_IDkcgxeMZj6QmY9j_ouTIe4asFaQh1TG11qG9dNc1Lqj8M3CqU6C_EEJilu4A==&lang=sage&interacts=eJyLjgUAARUAuQ==

def class_hierarchy(cls, indent):
  print('.'*indent, cls)
  for supercls in cls.__bases__:
    class_hierarchy(supercls, indent+1)
def instance_hierarchy(inst):
  print('Inheritance hierarchy of', inst)
  class_hierarchy(inst.__class__, 3)
instance_hierarchy(1)
instance_hierarchy(355/113)
instance_hierarchy(sqrt(10))

Inheritance hierarchy of 1
... <class 'sage.rings.integer.Integer'>
.... <class 'sage.structure.element.EuclideanDomainElement'>
..... <class 'sage.structure.element.PrincipalIdealDomainElement'>
...... <class 'sage.structure.element.DedekindDomainElement'>
....... <class 'sage.structure.element.IntegralDomainElement'>
........ <class 'sage.structure.element.CommutativeRingElement'>
......... <class 'sage.structure.element.RingElement'>
.......... <class 'sage.structure.element.ModuleElement'>
........... <class 'sage.structure.element.Element'>
............ <class 'sage.structure.sage_object.SageObject'>
............. <class 'object'>
Inheritance hierarchy of 355/113
... <class 'sage.rings.rational.Rational'>
.... <class 'sage.structure.element.FieldElement'>
..... <class 'sage.structure.element.CommutativeRingElement'>
...... <class 'sage.structure.element.RingElement'>
....... <class 'sage.structure.element.ModuleElement'>
........ <class 'sage.structure.element.Element'>
......... <class 'sage.structure.sage_object.SageObject'>
.......... <class 'object'>
Inheritance hierarchy of sqrt(10)
... <class 'sage.symbolic.expression.Expression'>
.... <class 'sage.structure.element.Expression'>
..... <class 'sage.structure.element.CommutativeRingElement'>
...... <class 'sage.structure.element.RingElement'>
....... <class 'sage.structure.element.ModuleElement'>
........ <class 'sage.structure.element.Element'>
......... <class 'sage.structure.sage_object.SageObject'>
.......... <class 'object'>

Environment

- **OS**: Ubuntu jammy
- **Sage Version**: 9.5

Checklist

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