我正在实现一个 Natural 类，其中自然数定义为 {1, 2, 3, ...}，并且故意排除了0。

在这个练习中，不能使用减法和除法，因为它们会把我们带出自然数集合。仅允许下列运算：

• 加法
• 乘法
• 比较 (<)
• 等于

我想在这些约束下实现模运算符（a % b）。

注：在我最初提出的问题中，我没有考虑自然数自身取模时会发生什么。0被明确排除。用户 @JaMiT的一个评论建议在这个运算中返回原值。

以下是相关的类结构：

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 0 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()

问题： 鉴于禁止减法和除法，我如何仅使用加法、乘法、比较和相等来计算 a % b？

我在寻找一个在这些约束内的算法思路。

我也愿意实现其他合理的方法，确保不离开该集合。

解决方案

我使用了两个循环：

第一个循环用于搜索满足 Nmax x b < a 的最大的自然数 Nmax。

第二个循环用于搜索最大的自然数 modulo，使得 Nmax x b + modulo <= a。

正如 @furas所提到的，a == b 情况会产生一个余数 0，在你的算术中被排除了。因此，在该函数中，它将返回值 nan。 情况 b > a 将导致 modulo = a。

正如 @JaMiT指出的一样（我也忽略了这个情况），b 需要不能整除 a（modulo = 0）。我已经加入了条件 n x b > a 以验证这一点，其中 n = nmax + 1。

    def __mod__(self, other):
        assert isinstance(other, Natural), "other must be a natural"
        a = self
        b = other
        if b > a:
            return self
        if b < a:
            one = Natural(1)
            nmax = one # maximum divisor
            n = one

            while n * b < a:
                nmax = n
                n = n + one

            if n * b > a: #b not divides a
                product = nmax * b
                modulo = one

                while product + modulo < a:
                    modulo = modulo + one

                return modulo

        return float('nan') # remainder 0

我也考虑了余数为零的情况，返回一个 float('nan')（不是一个数字）——我认为这是最适合该情形的值。