How to resolve the algorithm Modular arithmetic step by step in the Python programming language

Published on 12 May 2024 09:40 PM
#Python

How to resolve the algorithm Modular arithmetic step by step in the Python programming language

Table of Contents

Problem Statement

Modular arithmetic is a form of arithmetic (a calculation technique involving the concepts of addition and multiplication) which is done on numbers with a defined equivalence relation called congruence.
For any positive integer

p

{\displaystyle p}

called the congruence modulus, two numbers

a

{\displaystyle a}

and

b

{\displaystyle b}

are said to be congruent modulo p whenever there exists an integer

k

{\displaystyle k}

such that: The corresponding set of equivalence classes forms a ring denoted

Z

p

Z

{\displaystyle {\frac {\mathbb {Z} }{p\mathbb {Z} }}}

. When p is a prime number, this ring becomes a field denoted

F

p

{\displaystyle \mathbb {F} _{p}}

, but you won't have to implement the multiplicative inverse for this task. Addition and multiplication on this ring have the same algebraic structure as in usual arithmetic, so that a function such as a polynomial expression could receive a ring element as argument and give a consistent result. The purpose of this task is to show, if your programming language allows it, how to redefine operators so that they can be used transparently on modular integers.
You can do it either by using a dedicated library, or by implementing your own class. You will use the following function for demonstration: You will use

13

{\displaystyle 13}

as the congruence modulus and you will compute

f ( 10 )

{\displaystyle f(10)}

. It is important that the function

f

{\displaystyle f}

is agnostic about whether or not its argument is modular; it should behave the same way with normal and modular integers.
In other words, the function is an algebraic expression that could be used with any ring, not just integers.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Modular arithmetic step by step in the Python programming language

This Python code defines a custom class called Mod that represents integers with modulo arithmetic. It provides operators for basic mathematical operations, such as addition, subtraction, multiplication, and exponentiation, while ensuring that the result is always within the specified modulo range. It also uses the built-in modular exponentiation function for efficient exponentiation operations. Here's a detailed breakdown of the code:

  1. Class Definition and Initialization:

    • The Mod class is defined as a functools.total_ordering class, meaning it supports comparison operators (<, <=, >, >=, ==, and !=).
    • The class has two attributes: val (the value of the integer) and mod (the modulo value).
    • The constructor __init__ validates that the val is an integer and the mod is a positive integer.
    • It then assigns the val attribute to the value obtained by performing the modulo operation val % mod.

  2. Special Methods:

    • __repr__: Defines the string representation of the Mod object as Mod({val}, {mod}).
    • __int__: Converts the Mod object to an integer, returning the val attribute.
    • __eq__: Implements equality comparison. If other is an instance of Mod and has the same mod, it compares the val attributes. If other is an integer, it simply checks if val is equal to other. Otherwise, it returns NotImplemented.
    • __lt__: Implements less-than comparison. Similar to __eq__, it checks for consistent mod and compares val if both operands are Mod instances or if other is an integer. Otherwise, it returns NotImplemented.

  3. Private Helper Method:

    • _check_operand: Checks if the other operand is an integer or a Mod instance and raises exceptions if they are inconsistent (e.g., different mod values for Mod instances).

  4. Mathematical Operation Methods:

    • __pow__: Implements exponentiation using the built-in modular exponentiation function to avoid working with large numbers.
    • __neg__: Implements negation by subtracting val from mod.
    • __pos__: Implements the unary plus operator, which does nothing.
    • __abs__: Implements the absolute value operator, which does nothing since the value is always non-negative.

  5. Operator Overloading:

    • The code dynamically generates operator overload methods using the _make_op and _make_reflected_op helper functions.
    • _make_op creates methods for operators like __add__ and __mul__, which perform the operation on the val attributes and apply the modulo operation to the result.
    • _make_reflected_op creates methods for operators like __radd__ and __rmul__, which perform the operation with val on the right-hand side.

  6. Example Function:

    • The f function is defined to demonstrate the use of the Mod class. It takes a Mod object x and computes x**100 + x + 1.

  7. Usage:

    • The code calls the f function with an instance of Mod(10, 13) and prints the result, which is Mod(1, 13). This demonstrates the modulo arithmetic capabilities of the Mod class.

Source code in the python programming language

import operator
import functools

@functools.total_ordering
class Mod:
    __slots__ = ['val','mod']

    def __init__(self, val, mod):
        if not isinstance(val, int):
            raise ValueError('Value must be integer')
        if not isinstance(mod, int) or mod<=0:
            raise ValueError('Modulo must be positive integer')
        self.val = val % mod
        self.mod = mod

    def __repr__(self):
        return 'Mod({}, {})'.format(self.val, self.mod)

    def __int__(self):
        return self.val

    def __eq__(self, other):
        if isinstance(other, Mod):
            if self.mod == other.mod:
                return self.val==other.val
            else:
                return NotImplemented
        elif isinstance(other, int):
            return self.val == other
        else:
            return NotImplemented

    def __lt__(self, other):
        if isinstance(other, Mod):
            if self.mod == other.mod:
                return self.val<other.val
            else:
                return NotImplemented
        elif isinstance(other, int):
            return self.val < other
        else:
            return NotImplemented

    def _check_operand(self, other):
        if not isinstance(other, (int, Mod)):
            raise TypeError('Only integer and Mod operands are supported')
        if isinstance(other, Mod) and self.mod != other.mod:
            raise ValueError('Inconsistent modulus: {} vs. {}'.format(self.mod, other.mod))

    def __pow__(self, other):
        self._check_operand(other)
        # We use the built-in modular exponentiation function, this way we can avoid working with huge numbers.
        return Mod(pow(self.val, int(other), self.mod), self.mod)

    def __neg__(self):
        return Mod(self.mod - self.val, self.mod)

    def __pos__(self):
        return self # The unary plus operator does nothing.

    def __abs__(self):
        return self # The value is always kept non-negative, so the abs function should do nothing.

# Helper functions to build common operands based on a template.
# They need to be implemented as functions for the closures to work properly.
def _make_op(opname):
    op_fun = getattr(operator, opname)  # Fetch the operator by name from the operator module
    def op(self, other):
        self._check_operand(other)
        return Mod(op_fun(self.val, int(other)) % self.mod, self.mod)
    return op

def _make_reflected_op(opname):
    op_fun = getattr(operator, opname)
    def op(self, other):
        self._check_operand(other)
        return Mod(op_fun(int(other), self.val) % self.mod, self.mod)
    return op

# Build the actual operator overload methods based on the template.
for opname, reflected_opname in [('__add__', '__radd__'), ('__sub__', '__rsub__'), ('__mul__', '__rmul__')]:
    setattr(Mod, opname, _make_op(opname))
    setattr(Mod, reflected_opname, _make_reflected_op(opname))

def f(x):
    return x**100+x+1

print(f(Mod(10,13)))
# Output: Mod(1, 13)

You may also check:How to resolve the algorithm Greyscale bars/Display step by step in the AWK programming language
You may also check:How to resolve the algorithm Permutations step by step in the Scheme programming language
You may also check:How to resolve the algorithm Product of min and max prime factors step by step in the Arturo programming language
You may also check:How to resolve the algorithm 100 doors step by step in the Relation programming language
You may also check:How to resolve the algorithm Angle difference between two bearings step by step in the Scala programming language