如何在不含0的Natural类中用指定操作实现模运算（%）？

我正在实现一个Natural类，自然数定义为{1,2,3,...}，明确排除0。练习要求禁止使用减法和除法（会超出自然数集合），仅允许使用以下操作：

• 加法（addition）
• 乘法（multiplication）
• 小于比较（<）
• 相等判断（==）

需要在该约束下实现模运算符（a % b），特别规则：当自然数对自身取模时，返回原数值。

以下是原类结构：

class Natural:
    """
    The set of natural numbers: {1, 2, 3, ...}.

    They are commutative, distributive, and associative under addition 
    and multiplication.

    Subtraction and division are deliberately undefined, as that uncloses the set.

    The goal of this question is to define the mod operation (%) using only the defined operations.

    It is critical that the naturals are exclusive of zero for the purposes of my question.
    """

    def __init__(self, val):
        """
        We use the positive python integers as the values of our Natural numbers.
        @param val int the positive integer
        """
        assert isinstance(val, int), "your integer isn't an integer."
        assert val >= 1, "this integer isn't greater than 1"
        self.val = val

    def __str__(self):
        """pretty printer for Naturals"""
        return str(self.val)
    
    def __eq__(self, other):
        """
        Equality test for naturals.
        @param other Natural the one being compared to
        """
        if isinstance(other, Natural):
            return self.val == other.val
        return False
    
    def __hash__(self):
        """Tuple hash function"""
        return hash((self.val))
    
    def __add__(self, other):
        """
        Natural addition
        @param other Natural the one being added to self
        """
        assert isinstance(other, Natural), "other must be a Natural"
        return Natural(self.val + other.val)
        
    def __mul__(self, other):
        assert isinstance(other, Natural), "other must be a natural"
        return Natural(self.val * other.val)
        
    def __lt__(self, other):
        assert isinstance(other, Natural), "other must be a natural"
        return self.val < other.val
    
    def __mod__(self, other):
        """
        I need to implement mod on the Naturals (which in this case are exclusive of zero.)
        Remember, subtraction and division are undefined here.
        """
        pass

def main():
    print(Natural(7) % Natural(2))

if __name__ == "__main__":
    main()

实现思路 #

模运算的核心是找到符合自然数规则的余数r：

• 若a == b，则r = a（满足题目特殊规则）
• 若a < b，则r = a
• 若a > b，则r = (a - b) % b（递归缩小问题规模）

由于直接减法会超出自然数集合，但当a > b时，a - b仍属于自然数，因此可以实现一个仅在a > b时生效的减法辅助方法，完全通过加法和比较操作实现，不违反约束。

完整实现代码 #

class Natural:
    """
    The set of natural numbers: {1, 2, 3, ...}.

    They are commutative, distributive, and associative under addition 
    and multiplication.

    Subtraction and division are deliberately undefined, as that uncloses the set.

    The goal of this question is to define the mod operation (%) using only the defined operations.

    It is critical that the naturals are exclusive of zero for the purposes of my question.
    """

    def __init__(self, val):
        """
        We use the positive python integers as the values of our Natural numbers.
        @param val int the positive integer
        """
        assert isinstance(val, int), "your integer isn't an integer."
        assert val >= 1, "this integer isn't greater than 1"
        self.val = val

    def __str__(self):
        """pretty printer for Naturals"""
        return str(self.val)
    
    def __eq__(self, other):
        """
        Equality test for naturals.
        @param other Natural the one being compared to
        """
        if isinstance(other, Natural):
            return self.val == other.val
        return False
    
    def __hash__(self):
        """Tuple hash function"""
        return hash((self.val))
    
    def __add__(self, other):
        """
        Natural addition
        @param other Natural the one being added to self
        """
        assert isinstance(other, Natural), "other must be a Natural"
        return Natural(self.val + other.val)
        
    def __mul__(self, other):
        assert isinstance(other, Natural), "other must be a natural"
        return Natural(self.val * other.val)
        
    def __lt__(self, other):
        assert isinstance(other, Natural), "other must be a natural"
        return self.val < other.val
    
    def __sub__(self, other):
        """
        辅助减法方法：仅当self > other时生效，返回自然数结果
        """
        assert isinstance(other, Natural), "other must be a Natural"
        assert self > other, "subtraction result is not a Natural"
        # 通过加法逆向推导差值：找到r使得 other + r = self
        r = Natural(1)
        while (other + r) < self:
            r = r + Natural(1)
        return r
    
    def __mod__(self, other):
        """
        实现模运算，仅使用允许的操作
        """
        assert isinstance(other, Natural), "other must be a Natural"
        if self == other:
            return self
        if self < other:
            return self
        # 递归缩小问题规模
        return (self - other) % other

def main():
    print(Natural(7) % Natural(2))  # 输出1
    print(Natural(6) % Natural(3))  # 输出3
    print(Natural(5) % Natural(7))  # 输出5
    print(Natural(4) % Natural(4))  # 输出4

if __name__ == "__main__":
    main()

关键说明 #

1. 辅助减法方法__sub__：仅在self > other时允许调用，通过循环累加找到满足other + r = self的自然数r，完全依赖加法和比较操作，符合约束。
2. 模运算__mod__：
   • 优先处理特殊情况：自身取模返回自身，小于除数时返回自身
   • 其他情况通过递归调用(self - other) % other逐步缩小数值，最终得到符合自然数规则的余数

内容的提问来源于stack exchange，提问作者Jasper