Modular arithmetic

From Rosetta Code
Task
Modular arithmetic
You are encouraged to solve this task according to the task description, using any language you may know.

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 called the congruence modulus, two numbers and are said to be congruent modulo p whenever there exists an integer such that:

The corresponding set of equivalence classes forms a ring denoted . When p is a prime number, this ring becomes a field denoted , 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 as the congruence modulus and you will compute .

It is important that the function 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.

Related tasks

Modular exponentiation

Ada

Ada has modular types.

with Ada.Text_IO;

procedure Modular_Demo is

   type Modul_13 is mod 13;

   function F (X : Modul_13) return Modul_13 is
   begin
      return X**100 + X + 1;
   end F;

   package Modul_13_IO is
      new Ada.Text_IO.Modular_IO (Modul_13);

   use Ada.Text_IO;
   use Modul_13_IO;
   X_Integer  : constant Integer  := 10;
   X_Modul_13 : constant Modul_13 := Modul_13'Mod (X_Integer);
   F_10       : constant Modul_13 := F (X_Modul_13);
begin
   Put ("f("); Put (X_Modul_13); Put (" mod "); Put (Modul_13'Modulus'Image); Put (") = ");
   Put (F_10); Put (" mod ");    Put (Modul_13'Modulus'Image);
   New_Line;
end Modular_Demo;
Output:
f( 10 mod  13) =   1 mod  13

ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.8.win32
# allow for large integers in Algol 68G #
PR precision 200 PR

# modular integer type #
MODE MODULARINT = STRUCT( LONG LONG INT v, INT modulus );

# modular integer + and * operators #
# where both operands are modular, they must have the same modulus #
OP +  = ( MODULARINT a,     b )MODULARINT: ( ( v OF a + v OF b ) MOD modulus OF a, modulus OF a ); 
OP +  = ( MODULARINT a, INT b )MODULARINT: ( ( v OF a + b      ) MOD modulus OF a, modulus OF a ); 
OP *  = ( MODULARINT a,     b )MODULARINT: ( ( v OF a * v OF b ) MOD modulus OF a, modulus OF a );
OP ** = ( MODULARINT a, INT b )MODULARINT: ( ( v OF a ** b     ) MOD modulus OF a, modulus OF a );

# f(x) function - can be applied to either LONG LONG INT or MODULARINT values #
# the result is always a LONG LONG INT #
PROC f = ( UNION( LONG LONG INT, MODULARINT ) x )LONG LONG INT:
    CASE x
      IN ( LONG LONG INT ix ):      ( ix**100 + ix + 1 )
       , ( MODULARINT    mx ): v OF ( mx**100 + mx + 1 )
    ESAC;

print( ( whole( f( MODULARINT( 10, 13 ) ), 0 ), newline ) )
Output:
1

ATS

The following program uses the unsigned __int128 type of GNU C. I use the compiler extension to implement modular multiplication that works for all moduli possible with the ordinary integer types on AMD64.

And I let "modulus 0" mean to do ordinary unsigned arithmetic, so I might be tempted to say the code is transparently supporting both modular and non-modular integers. However, 10**100 would overflow the register, so the result would actually be modulo 2**(wordsize). There is, in fact, with C semantics for unsigned integers, no way to do non-modular arithmetic! You automatically get 2**(wordsize) as a modulus. And you cannot safely use signed integers at all.

(There is support for multiple precision exact rationals, with overloaded operators, in the ats2-xprelude package. If the denominators are one, then such numbers are integers. The macro g(x) defined near the end of the program should work with those numbers.)

(* The program is compiled to C and the integer types have C
   semantics. This means ordinary unsigned arithmetic is already
   modular!  However, the modulus is fixed at 2**n, where n is the
   number of bits in the unsigned integer type.

   Below, I let a "modulus" of zero mean to use 2**n as the
   modulus. *)

(*------------------------------------------------------------------*)

#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"

(*------------------------------------------------------------------*)

(* An abstract type, the size of @(g0uint tk, g1uint (tk, modulus)) *)
abst@ype modular_g0uint (tk : tkind, modulus : int) =
  @(g0uint tk, g1uint (tk, modulus))

(* Because the type is abstract, we need a constructor: *)
extern fn {tk : tkind}
modular_g0uint_make
          {m : int}             (* "For any integer m" *)
          (a : g0uint tk,
           m : g1uint (tk, m))
    :<> modular_g0uint (tk, m)

(* A deconstructor: *)
extern fn {tk : tkind}
modular_g0uint_unmake
          {m : int}
          (a : modular_g0uint (tk, m))
    :<> @(g0uint tk, g1uint (tk, m))

extern fn {tk : tkind}
modular_g0uint_succ     (* "Successor" *)
          {m : int}
          (a : modular_g0uint (tk, m))
    :<> modular_g0uint (tk, m)

extern fn {tk : tkind}  (* This won't be used, but let us write it. *)
modular_g0uint_pred     (* "Predecessor" *)
          {m : int}
          (a : modular_g0uint (tk, m))
    :<> modular_g0uint (tk, m)

extern fn {tk : tkind}   (* This won't be used, but let us write it.*)
modular_g0uint_neg
          {m : int}
          (a : modular_g0uint (tk, m))
    :<> modular_g0uint (tk, m)

extern fn {tk : tkind}
modular_g0uint_add
          {m : int}
          (a : modular_g0uint (tk, m),
           b : modular_g0uint (tk, m))
    :<> modular_g0uint (tk, m)

extern fn {tk : tkind}   (* This won't be used, but let us write it.*)
modular_g0uint_sub
          {m : int}
          (a : modular_g0uint (tk, m),
           b : modular_g0uint (tk, m))
    :<> modular_g0uint (tk, m)

extern fn {tk : tkind}
modular_g0uint_mul
          {m : int}
          (a : modular_g0uint (tk, m),
           b : modular_g0uint (tk, m))
    :<> modular_g0uint (tk, m)

extern fn {tk : tkind}
modular_g0uint_npow
          {m : int}
          (a : modular_g0uint (tk, m),
           i : intGte 0)
    :<> modular_g0uint (tk, m)

overload succ with modular_g0uint_succ
overload pred with modular_g0uint_pred
overload ~ with modular_g0uint_neg
overload + with modular_g0uint_add
overload - with modular_g0uint_sub
overload * with modular_g0uint_mul
overload ** with modular_g0uint_npow

(*------------------------------------------------------------------*)

local

  (* We make the type be @(g0uint tk, g1uint (tk, modulus)).
     The first element is the least residue, the second is the
     modulus. A modulus of 0 indicates that the modulus is 2**n, where
     n is the number of bits in the typekind. *)
  typedef _modular_g0uint (tk : tkind, modulus : int) =
    @(g0uint tk, g1uint (tk, modulus))

in (* local *)

  assume modular_g0uint (tk, modulus) = _modular_g0uint (tk, modulus)

  implement {tk}
  modular_g0uint_make (a, m) =
    if m = g1i2u 0 then
      @(a, m)
    else
      @(a mod m, m)

  implement {tk}
  modular_g0uint_unmake a =
    a

  implement {tk}
  modular_g0uint_succ a =
    let
      val @(a, m) = a
    in
      if (m = g1i2u 0) || (succ a <> m) then
        @(succ a, m)
      else
        @(g1i2u 0, m)
    end

  implement {tk}
  modular_g0uint_pred a =
    let
      val @(a, m) = a
      prval () = lemma_g1uint_param m
    in
      (* An exercise for the advanced reader: how come in
         modular_g0uint_succ I could use "||", but here I have to use
         "+" instead? *)
      if (m = g1i2u 0) + (a <> g1i2u 0) then
        @(pred a, m)
      else
        @(pred m, m)
    end

  implement {tk}
  modular_g0uint_neg a =
    let
      val @(a, m) = a
    in
      if m = g1i2u 0 then
        @(succ (lnot a), m)       (* Two's complement. *)
      else if a = g0i2u 0 then
        @(a, m)
      else
        @(m - a, m)
    end

  implement {tk}
  modular_g0uint_add (a, b) =
    let
      (* The modulus of b WILL be same as that of a. The type system
         guarantees this at compile time. *)
      val @(a, m) = a
      and @(b, _) = b
    in
      if m = g1i2u 0 then
        @(a + b, m)
      else
        @((a + b) mod m, m)
    end

  implement {tk}
  modular_g0uint_mul (a, b) =
    (* For multiplication there is a complication, which is that the
       product might overflow the register and so end up reduced
       modulo the 2**(wordsize). Approaches to that problem are
       discussed here:
       https://en.wikipedia.org/w/index.php?title=Modular_arithmetic&oldid=1145603919#Example_implementations

       However, what I will do is inline some C, and use a GNU C
       extension for an integer type that (on AMD64, at least) is
       twice as large as uintmax_t.
       
       In so doing, perhaps I help demonstrate how suitable ATS is for
       low-level systems programming. Inlining the C is very easy to
       do. *)
    let
      val @(a, m) = a
      and @(b, _) = b
    in
      if m = g1i2u 0 then
        @(a * b, m)
      else
        let
          typedef big = $extype"unsigned __int128"

          (* A call to _modular_g0uint_mul will actually be a call to
             a C function or macro, which happens also to be named
             _modular_g0uint_mul. *)
          extern fn
          _modular_g0uint_mul
                    (a : big,
                     b : big,
                     m : big)
              :<> big = "mac#_modular_g0uint_mul"
        in
          (* The following will work only as long as the C compiler
             itself knows how to cast the integer types. There are
             safer methods of casting, but, for this task, let us
             ignore that. *)
          @($UN.cast (_modular_g0uint_mul ($UN.cast a,
                                           $UN.cast b,
                                           $UN.cast m)),
            m)
        end
    end

(* The following puts a static inline function _modular_g0uint_mul
   near the top of the C source file. *)
%{^

ATSinline() unsigned __int128
_modular_g0uint_mul (unsigned __int128 a,
                     unsigned __int128 b,
                     unsigned __int128 m)
{
  return ((a * b) % m);
} 

%}

end (* local *)

implement {tk}
modular_g0uint_sub (a, b) =
  a + (~b)

implement {tk}
modular_g0uint_npow {m} (a, i) =
  (* To compute a power, the multiplication implementation devised
     above can be used. The algorithm here is simply the squaring
     method:
     https://en.wikipedia.org/w/index.php?title=Exponentiation_by_squaring&oldid=1144956501 *)
  let
    fun
    repeat {i : nat}     (* <-- This number consistently shrinks. *)
           .<i>.         (* <-- Proof the recursion will terminate. *)
           (accum : modular_g0uint (tk, m), (* "Accumulator" *)
            base  : modular_g0uint (tk, m),
            i     : int i)
        :<> modular_g0uint (tk, m) =
      if i = 0 then
        accum
      else
        let
          val i_halved = half i (* Integer division. *)
          and base_squared = base * base
        in
          if i_halved + i_halved = i then
            repeat (accum, base_squared, i_halved)
          else
            repeat (base * accum, base_squared, i_halved)
        end

    val @(_, m) = modular_g0uint_unmake<tk> a
  in
    repeat (modular_g0uint_make<tk> (g0i2u 1, m), a, i)
  end

(*------------------------------------------------------------------*)

extern fn {tk : tkind}
f : {m : int} modular_g0uint (tk, m) -<> modular_g0uint (tk, m)

(* Using the "successor" function below means that, to add 1, we do
   not need to know the modulus. That is why I added "succ". *)
implement {tk}
f(x) = succ (x**100 + x)

(* Using a macro, and thanks to operator overloading, we can use the
   same code for modular integers, floating point, etc. *)
macdef g(x) =
  let
    val x_ = ,(x)               (* Evaluate the argument just once. *)
  in
    succ (x_**100 + x_)
  end

implement
main0 () =
  let
    val x = modular_g0uint_make (10U, 13U)
  in
    println! ((modular_g0uint_unmake (f(x))).0);
    println! ((modular_g0uint_unmake (g(x))).0);
    println! (g(10.0))
  end

(*------------------------------------------------------------------*)
Output:
$ patscc -std=gnu2x -g -O2 modular_arithmetic_task.dats && ./a.out
1
1
10000000000000002101697803323328251387822715387464188032188166609887360023982790799717755191065313280.000000

C

Translation of: C++
#include <stdio.h>

struct ModularArithmetic {
    int value;
    int modulus;
};

struct ModularArithmetic make(const int value, const int modulus) {
    struct ModularArithmetic r = { value % modulus, modulus };
    return r;
}

struct ModularArithmetic add(const struct ModularArithmetic a, const struct ModularArithmetic b) {
    return make(a.value + b.value, a.modulus);
}

struct ModularArithmetic addi(const struct ModularArithmetic a, const int v) {
    return make(a.value + v, a.modulus);
}

struct ModularArithmetic mul(const struct ModularArithmetic a, const struct ModularArithmetic b) {
    return make(a.value * b.value, a.modulus);
}

struct ModularArithmetic pow(const struct ModularArithmetic b, int pow) {
    struct ModularArithmetic r = make(1, b.modulus);
    while (pow-- > 0) {
        r = mul(r, b);
    }
    return r;
}

void print(const struct ModularArithmetic v) {
    printf("ModularArithmetic(%d, %d)", v.value, v.modulus);
}

struct ModularArithmetic f(const struct ModularArithmetic x) {
    return addi(add(pow(x, 100), x), 1);
}

int main() {
    struct ModularArithmetic input = make(10, 13);
    struct ModularArithmetic output = f(input);

    printf("f(");
    print(input);
    printf(") = ");
    print(output);
    printf("\n");

    return 0;
}
Output:
f(ModularInteger(10, 13)) = ModularInteger(1, 13)

C#

Translation of: Java
using System;

namespace ModularArithmetic {
    interface IAddition<T> {
        T Add(T rhs);
    }
    interface IMultiplication<T> {
        T Multiply(T rhs);
    }
    interface IPower<T> {
        T Power(int pow);
    }
    interface IOne<T> {
        T One();
    }

    class ModInt : IAddition<ModInt>, IMultiplication<ModInt>, IPower<ModInt>, IOne<ModInt> {
        private int modulo;

        public ModInt(int value, int modulo) {
            Value = value;
            this.modulo = modulo;
        }

        public int Value { get; }

        public ModInt One() {
            return new ModInt(1, modulo);
        }

        public ModInt Add(ModInt rhs) {
            return this + rhs;
        }

        public ModInt Multiply(ModInt rhs) {
            return this * rhs;
        }

        public ModInt Power(int pow) {
            return Pow(this, pow);
        }

        public override string ToString() {
            return string.Format("ModInt({0}, {1})", Value, modulo);
        }

        public static ModInt operator +(ModInt lhs, ModInt rhs) {
            if (lhs.modulo != rhs.modulo) {
                throw new ArgumentException("Cannot add rings with different modulus");
            }
            return new ModInt((lhs.Value + rhs.Value) % lhs.modulo, lhs.modulo);
        }

        public static ModInt operator *(ModInt lhs, ModInt rhs) {
            if (lhs.modulo != rhs.modulo) {
                throw new ArgumentException("Cannot add rings with different modulus");
            }
            return new ModInt((lhs.Value * rhs.Value) % lhs.modulo, lhs.modulo);
        }

        public static ModInt Pow(ModInt self, int p) {
            if (p < 0) {
                throw new ArgumentException("p must be zero or greater");
            }

            int pp = p;
            ModInt pwr = self.One();
            while (pp-- > 0) {
                pwr *= self;
            }
            return pwr;
        }
    }

    class Program {
        static T F<T>(T x) where T : IAddition<T>, IMultiplication<T>, IPower<T>, IOne<T> {
            return x.Power(100).Add(x).Add(x.One());
        }

        static void Main(string[] args) {
            ModInt x = new ModInt(10, 13);
            ModInt y = F(x);
            Console.WriteLine("x ^ 100 + x + 1 for x = {0} is {1}", x, y);
        }
    }
}
Output:
x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(1, 13)

C++

Translation of: D
#include <iostream>
#include <ostream>

template<typename T>
T f(const T& x) {
    return (T) pow(x, 100) + x + 1;
}

class ModularInteger {
private:
    int value;
    int modulus;

    void validateOp(const ModularInteger& rhs) const {
        if (modulus != rhs.modulus) {
            throw std::runtime_error("Left-hand modulus does not match right-hand modulus.");
        }
    }

public:
    ModularInteger(int v, int m) {
        modulus = m;
        value = v % m;
    }

    int getValue() const {
        return value;
    }

    int getModulus() const {
        return modulus;
    }

    ModularInteger operator+(const ModularInteger& rhs) const {
        validateOp(rhs);
        return ModularInteger(value + rhs.value, modulus);
    }

    ModularInteger operator+(int rhs) const {
        return ModularInteger(value + rhs, modulus);
    }

    ModularInteger operator*(const ModularInteger& rhs) const {
        validateOp(rhs);
        return ModularInteger(value * rhs.value, modulus);
    }

    friend std::ostream& operator<<(std::ostream&, const ModularInteger&);
};

std::ostream& operator<<(std::ostream& os, const ModularInteger& self) {
    return os << "ModularInteger(" << self.value << ", " << self.modulus << ")";
}

ModularInteger pow(const ModularInteger& lhs, int pow) {
    if (pow < 0) {
        throw std::runtime_error("Power must not be negative.");
    }

    ModularInteger base(1, lhs.getModulus());
    while (pow-- > 0) {
        base = base * lhs;
    }
    return base;
}

int main() {
    using namespace std;

    ModularInteger input(10, 13);
    auto output = f(input);
    cout << "f(" << input << ") = " << output << endl;

    return 0;
}
Output:
f(ModularInteger(10, 13)) = ModularInteger(1, 13)

Common Lisp

Translation of: Scheme

In Scheme all procedures are anonymous, and names such as + and expt are really the names of variables. Thus one can trivially redefine "functions" locally, by storing procedures in variables having the same names as the global ones. Common Lisp has functions with actual names, and which are not the contents of variables. There is no attempt below to copy the Scheme example's trickery with names. (Some less trivial method would be necessary.)

(defvar *modulus* nil)

(defmacro define-enhanced-op (enhanced-op op)
  `(defun ,enhanced-op (&rest args)
     (if *modulus*
         (mod (apply ,op args) *modulus*)
         (apply ,op args))))

(define-enhanced-op enhanced+ #'+)
(define-enhanced-op enhanced-expt #'expt)

(defun f (x)
  (enhanced+ (enhanced-expt x 100) x 1))

;; Use f on regular integers.
(princ "No modulus:  ")
(princ (f 10))
(terpri)

;; Use f on modular integers.
(let ((*modulus* 13))
  (princ "modulus 13:  ")
  (princ (f 10))
  (terpri))
Output:
$ sbcl --script modular_arithmetic_task.lisp
No modulus:  10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13:  1

D

import std.stdio;

version(unittest) {
    void assertEquals(T)(T actual, T expected) {
        import core.exception;
        import std.conv;
        if (actual != expected) {
            throw new AssertError("Actual [" ~ to!string(actual) ~ "]; Expected [" ~ to!string(expected) ~ "]");
        }
    }
}

void main() {
    auto input = ModularInteger(10,13);
    auto output = f(input);
    writeln("f(", input, ") = ", output);
}

V f(V)(const V x) {
    return x^^100 + x + 1;
}

/// Integer tests on f
unittest {
    assertEquals(f(1), 3);
    assertEquals(f(0), 1);
}

/// Floating tests on f
unittest {
    assertEquals(f(1.0), 3.0);
    assertEquals(f(0.0), 1.0);
}

struct ModularInteger {
    private:
    int value;
    int modulus;

    public:
    this(int value, int modulus) {
        this.modulus = modulus;
        this.value = value % modulus;
    }

    ModularInteger opBinary(string op : "+")(ModularInteger rhs) const in {
        assert(this.modulus == rhs.modulus);
    } body {
        return ModularInteger((this.value + rhs.value) % this.modulus, this.modulus);
    }

    ModularInteger opBinary(string op : "+")(int rhs) const {
        return ModularInteger((this.value + rhs) % this.modulus, this.modulus);
    }

    ModularInteger opBinary(string op : "*")(ModularInteger rhs) const in {
        assert(this.modulus == rhs.modulus);
        assert(this.value < this.modulus);
        assert(rhs.value < this.modulus);
    } body {
        return ModularInteger((this.value * rhs.value) % this.modulus, this.modulus);
    }

    ModularInteger opBinary(string op : "^^")(int pow) const in {
        assert(pow >= 0);
    } body {
        auto base = ModularInteger(1, this.modulus);
        while (pow-- > 0) {
            base = base * this;
        }
        return base;
    }

    string toString() {
        import std.format;
        return format("ModularInteger(%s, %s)", value, modulus);
    }
}

/// Addition with same type of int
unittest {
    auto a = ModularInteger(2,5);
    auto b = ModularInteger(3,5);
    assertEquals(a+b, ModularInteger(0,5));
}

/// Addition with differnt int types
unittest {
    auto a = ModularInteger(2,5);
    assertEquals(a+0, a);
    assertEquals(a+1, ModularInteger(3,5));
}

/// Muliplication
unittest {
    auto a = ModularInteger(2,5);
    auto b = ModularInteger(3,5);
    assertEquals(a*b, ModularInteger(1,5));
}

/// Power
unittest {
    const a = ModularInteger(3,13);
    assertEquals(a^^2, ModularInteger(9,13));
    assertEquals(a^^3, ModularInteger(1,13));

    const b = ModularInteger(10,13);
    assertEquals(b^^1, ModularInteger(10,13));
    assertEquals(b^^2, ModularInteger(9,13));
    assertEquals(b^^3, ModularInteger(12,13));
    assertEquals(b^^4, ModularInteger(3,13));
    assertEquals(b^^5, ModularInteger(4,13));
    assertEquals(b^^6, ModularInteger(1,13));
    assertEquals(b^^7, ModularInteger(10,13));
    assertEquals(b^^8, ModularInteger(9,13));
    assertEquals(b^^10, ModularInteger(3,13));
    assertEquals(b^^20, ModularInteger(9,13));
    assertEquals(b^^30, ModularInteger(1,13));
    assertEquals(b^^50, ModularInteger(9,13));
    assertEquals(b^^75, ModularInteger(12,13));
    assertEquals(b^^90, ModularInteger(1,13));
    assertEquals(b^^95, ModularInteger(4,13));
    assertEquals(b^^97, ModularInteger(10,13));
    assertEquals(b^^98, ModularInteger(9,13));
    assertEquals(b^^99, ModularInteger(12,13));
    assertEquals(b^^100, ModularInteger(3,13));
}
Output:
f(ModularInteger(10, 13)) = ModularInteger(1, 13)

Factor

While it's probably not the best idea to define methods in arithmetic words that specialize on custom classes, it can be done. There are a few pitfalls to doing so, which is why custom types typically implement their own arithmetic words. Examples are words like v+ from the math.vectors vocabulary and q+ from the math.quaternions vocabulary.

The pitfalls are as follows:
First, arithmetic words are declared using MATH:, which means they use the math method combination. These methods will dispatch on both their arguments, and promote lower-priority numeric types to higher-priority types when both types are different. The math method combination also means that methods added to MATH: words cannot specialize on any classes except for fixnum, bignum, ratio, float, complex, object, or unions of them.

This is a bit of a problem, because we must specialize on object and then do a bunch of manual type checking and stack shuffling to make sure we are performing the correct operations on the correct objects.

Second, if any other vocabularies add methods that specialize on arithmetic words, they will conflict with our modular arithmetic vocabulary due to the aforementioned inability to specialize on specific classes.

For these reasons, I would normally opt to define my own arithmetic words, with the added bonus of being able to use non-MATH: multiple dispatch (from the multi-methods vocabulary) to cleanly implement mixed-type dispatch.

Also note that since ^ is not a generic word, we employ the strategy of renaming it to ** inside our vocabulary and defining a new word named ^ that can also handle modular integers. This is an acceptable way to handle it because Factor has pretty good word-disambiguation faculties. I just wouldn't want to have to employ them for more frequently-used arithmetic.

USING: accessors generalizations io kernel math math.functions
parser prettyprint prettyprint.custom sequences ;
IN: rosetta-code.modular-arithmetic
RENAME: ^ math.functions => **

! Define a modular integer class.
TUPLE: mod-int
    { n integer read-only } { mod integer read-only } ;

! Define a constructor for mod-int.
C: <mod-int> mod-int

ERROR: non-equal-modulus m1 m2 ;

! Define a literal syntax for mod-int. 
<< SYNTAX: MI{ \ } [ first2 <mod-int> ] parse-literal ; >>

! Implement prettyprinting for mod-int custom syntax.
M: mod-int pprint-delims drop \ MI{ \ } ;
M: mod-int >pprint-sequence [ n>> ] [ mod>> ] bi { } 2sequence ;
M: mod-int pprint* pprint-object ;

<PRIVATE

! Helper words for displaying the results of an arithmetic
! operation.
: show ( quot -- )
    [ unparse 2 tail but-last "= " append write ] [ call . ] bi
    ; inline

: 2show ( quots -- )
    [ 2curry show ] map-compose [ call( -- ) ] each ; inline

! Check whether two mod-ints have the same modulus and throw an
! error if not.
: check-mod ( m1 m2 -- )
    2dup [ mod>> ] bi@ = [ 2drop ] [ non-equal-modulus ] if ;

! Apply quot to the integer parts of two mod-ints and create a
! new mod-int from the result.
: mod-int-op ( m1 m2 quot -- m3 )
    [ [ n>> ] bi@ ] prepose [ 2dup check-mod ] dip over
    mod>> [ call( x x -- x ) ] dip [ mod ] keep <mod-int>
    ; inline

! Promote an integer to a mod-int and call mod-int-op.
: integer-op ( obj1 obj2 quot -- mod-int )
    [
        dup integer?
        [ over mod>> <mod-int> ]
        [ dup [ mod>> <mod-int> ] dip ] if
    ] dip mod-int-op ; inline

! Apply quot, a binary function, to any combination of integers
! and mod-ints.
: binary-op ( obj1 obj2 quot -- mod-int )
    2over [ mod-int? ] both? [ mod-int-op ] [ integer-op ] if
    ; inline

PRIVATE>

! This is where the arithmetic words are 'redefined' by adding a
! method to them that specializes on the object class.
M: object + [ + ] binary-op ;
M: object - [ - ] binary-op ;
M: object * [ * ] binary-op ;
M: object /i [ /i ] binary-op ;

! ^ is a special case because it is not generic.
: ^ ( obj1 obj2 -- obj3 )
    2dup [ mod-int? ] either? [ [ ** ] binary-op ] [ ** ] if ;

: fn ( obj -- obj' ) dup 100 ^ + 1 + ;

: modular-arithmetic-demo ( -- )
    [ MI{ 10 13 } fn ]
    [ 2 fn ] [ show ] bi@
    {
        [ MI{ 10 13 } MI{ 5 13 } [ + ] ]
        [ MI{ 10 13 } 5 [ + ] ]
        [ 5 MI{ 10 13 } [ + ] ]
        [ MI{ 10 13 } 2 [ /i ] ]
        [ 5 10 [ * ] ]
        [ MI{ 3 7 } MI{ 4 7 } [ * ] ]
        [ MI{ 3 7 } 50 [ ^ ] ]
    } 2show ;

MAIN: modular-arithmetic-demo
Output:
MI{ 10 13 } fn = MI{ 1 13 }
2 fn = 1267650600228229401496703205379
MI{ 10 13 } MI{ 5 13 } + = MI{ 2 13 }
MI{ 10 13 } 5 + = MI{ 2 13 }
5 MI{ 10 13 } + = MI{ 2 13 }
MI{ 10 13 } 2 /i = MI{ 5 13 }
5 10 * = 50
MI{ 3 7 } MI{ 4 7 } * = MI{ 5 7 }
MI{ 3 7 } 50 ^ = MI{ 2 7 }

Forth

Contrary to other contributions, this present a modular package that is complete, i.e. they contain a full set of operators, notably division. It relies not on a library supplied with Forth, but presents the implementation, defined using only Forth kernel definitions.

\ We would normally define operators that have a suffix `m' in order
\ not to be confused:  +m -m *m /m **m
\ Also useful is %:m reduce a number modulo.

\ Words that may be not be present in the kernel.
\ This example loads them in ciforth.
WANT ALIAS VOCABULARY

VARIABLE _m ( Modulo number)
\ Set the modulus to  m .
: set-modulus  _m ! ;

\ For A B return C GCD where C*A+x*B=GCD
: XGCD 1 0 2SWAP   BEGIN OVER /MOD OVER WHILE >R SWAP
   2SWAP OVER R> * - SWAP 2SWAP REPEAT 2DROP NIP ;
\ Suffix n : normalized number.
: _norm_-m  DUP 0< _m @ AND + ; ( x -- xn ) \ -m<xn<+m
: +m   + _m @ - _norm_-m  ;   ( an bn -- sumn )
: -m   - _norm_-m  ;         ( an bn -- diffn)
: *m   M* _m @ SM/REM DROP ;  ( an bn -- prodn)
: /m    _m @ XGCD DROP _norm_-m  *m ; ( a b -- quotn)
: %:m  S>D _m @ SM/REM DROP _norm_-m  ;  ( a -- an)

\ Both steps: For A B and C: return A B en C.  Invariant A*B^C.
: _reduce_1-  1- >R >R    R@ *m   R> R> ;
: _reduce_2/  2/ >R    DUP *m        R> ;
( a b -- apowbn )
: **m    1 ROT ROT BEGIN   DUP 1 AND IF   _reduce_1-   THEN
    _reduce_2/ DUP 0= UNTIL   2DROP   ;  

\ The solution is
13 set-modulus
10  DUP 100 **m +m 1 +m . CR

\ In order to comply with the problem we can generate a separate namespace
\ and import the above definitions.

VOCABULARY MODULO
ALSO MODULO DEFINITIONS
' set-modulus ALIAS set-modulus
' +m   ALIAS   +
' -m   ALIAS   -
' *m   ALIAS   *
' /m   ALIAS   /
' **m  ALIAS   **
' %:m   ALIAS   %:m

\ now the calculation becomes
13 set-modulus
10  DUP 100 ** + 1 + . CR

Fortran

Works with: GCC version 12.2.1

Program 1

This program requires the C preprocessor (or, if your Fortran compiler has it, the "fortranized" preprocessor fpp). For gfortran, one gets the C preprocessor simply by capitalizing the source file extension: .F90

module modular_arithmetic
  implicit none

  type :: modular
     integer :: val
     integer :: modulus
  end type modular

  interface operator(+)
     module procedure modular_modular_add
     module procedure modular_integer_add
  end interface operator(+)

  interface operator(**)
     module procedure modular_integer_pow
  end interface operator(**)

contains

  function modular_modular_add (a, b) result (c)
    type(modular), intent(in) :: a
    type(modular), intent(in) :: b
    type(modular) :: c

    if (a%modulus /= b%modulus) error stop
    c%val = modulo (a%val + b%val, a%modulus)
    c%modulus = a%modulus
  end function modular_modular_add

  function modular_integer_add (a, i) result (c)
    type(modular), intent(in) :: a
    integer, intent(in) :: i
    type(modular) :: c

    c%val = modulo (a%val + i, a%modulus)
    c%modulus = a%modulus
  end function modular_integer_add

  function modular_integer_pow (a, i) result (c)
    type(modular), intent(in) :: a
    integer, intent(in) :: i
    type(modular) :: c

    ! One cannot simply use the integer ** operator and then compute
    ! the least residue, because the integers will overflow. Let us
    ! instead use the right-to-left binary method:
    ! https://en.wikipedia.org/w/index.php?title=Modular_exponentiation&oldid=1136216610#Right-to-left_binary_method

    integer :: modulus
    integer :: base
    integer :: exponent

    modulus = a%modulus
    exponent = i

    if (modulus < 1) error stop
    if (exponent < 0) error stop

    c%modulus = modulus
    if (modulus == 1) then
       c%val = 0
    else
       c%val = 1
       base = modulo (a%val, modulus)
       do while (exponent > 0)
          if (modulo (exponent, 2) /= 0) then
             c%val = modulo (c%val * base, modulus)
          end if
          exponent = exponent / 2
          base = modulo (base * base, modulus)
       end do
    end if
  end function modular_integer_pow

end module modular_arithmetic

! If one uses the extension .F90 instead of .f90, then gfortran will
! pass the program through the C preprocessor. Thus one can write f(x)
! without considering the type of the argument
#define f(x) ((x)**100 + (x) + 1)

program modular_arithmetic_task
  use, intrinsic :: iso_fortran_env
  use, non_intrinsic :: modular_arithmetic
  implicit none

  type(modular) :: x, y

  x = modular(10, 13)
  y = f(x)

  write (*, '("    modulus 13:  ", I0)') y%val
  write (*, '("floating point:  ", E55.50)') f(10.0_real64)

end program modular_arithmetic_task
Output:
$ gfortran -O2 -fbounds-check -Wall -Wextra -g modular_arithmetic_task.F90 && ./a.out
    modulus 13:  1
floating point:  .10000000000000000159028911097599180468360808563945+101

Program 2

Works with: GCC version 12.2.1

This program uses unlimited runtime polymorphism.

module modular_arithmetic
  implicit none

  type :: modular_integer
     integer :: val
     integer :: modulus
  end type modular_integer

  interface operator(+)
     module procedure add
  end interface operator(+)

  interface operator(*)
     module procedure mul
  end interface operator(*)

  interface operator(**)
     module procedure npow
  end interface operator(**)

contains

  function modular (val, modulus) result (modint)
    integer, intent(in) :: val, modulus
    type(modular_integer) :: modint

    modint%val = modulo (val, modulus)
    modint%modulus = modulus
  end function modular

  subroutine write_number (x)
    class(*), intent(in) :: x

    select type (x)
    class is (modular_integer)
       write (*, '(I0)', advance = 'no') x%val
    type is (integer)
       write (*, '(I0)', advance = 'no') x
    class default
       error stop
    end select
  end subroutine write_number

  function add (a, b) result (c)
    class(*), intent(in) :: a, b
    class(*), allocatable :: c

    select type (a)
    class is (modular_integer)
       select type (b)
       class is (modular_integer)
          if (a%modulus /= b%modulus) error stop
          allocate (c, source = modular (a%val + b%val, a%modulus))
       type is (integer)
          allocate (c, source = modular (a%val + b, a%modulus))
       class default
          error stop
       end select
    type is (integer)
       select type (b)
       class is (modular_integer)
          allocate (c, source = modular (a + b%val, b%modulus))
       type is (integer)
          allocate (c, source = a + b)
       class default
          error stop
       end select
    class default
       error stop
    end select
  end function add

  function mul (a, b) result (c)
    class(*), intent(in) :: a, b
    class(*), allocatable :: c

    select type (a)
    class is (modular_integer)
       select type (b)
       class is (modular_integer)
          if (a%modulus /= b%modulus) error stop
          allocate (c, source = modular (a%val * b%val, a%modulus))
       type is (integer)
          allocate (c, source = modular (a%val * b, a%modulus))
       class default
          error stop
       end select
    type is (integer)
       select type (b)
       class is (modular_integer)
          allocate (c, source = modular (a * b%val, b%modulus))
       type is (integer)
          allocate (c, source = a * b)
       class default
          error stop
       end select
    class default
       error stop
    end select
  end function mul

  function npow (a, i) result (c)
    class(*), intent(in) :: a
    integer, intent(in) :: i
    class(*), allocatable :: c

    class(*), allocatable :: base
    integer :: exponent, exponent_halved

    if (i < 0) error stop

    select type (a)
    class is (modular_integer)
       allocate (c, source = modular (1, a%modulus))
    class default
       c = 1
    end select

    allocate (base, source = a)

    exponent = i
    do while (exponent /= 0)
       exponent_halved = exponent / 2
       if (2 * exponent_halved /= exponent) c = base * c
       base = base * base
       exponent = exponent_halved
    end do
  end function npow

end module modular_arithmetic

program modular_arithmetic_task
  use, non_intrinsic :: modular_arithmetic
  implicit none

  write (*, '("f(10) ≅ ")', advance = 'no')
  call write_number (f (modular (10, 13)))
  write (*, '("   (mod 13)")')

  write (*, '()')
  write (*, '("f applied to a regular integer would overflow, so, in what")')
  write (*, '("follows, instead we use g(x) = x**2 + x + 1")')
  write (*, '()')

  write (*, '("g(10) = ")', advance = 'no')
  call write_number (g (10))
  write (*, '()')
  write (*, '("g(10) ≅ ")', advance = 'no')
  call write_number (g (modular (10, 13)))
  write (*, '("   (mod 13)")')
contains

  function f(x) result (y)
    class(*), intent(in) :: x
    class(*), allocatable :: y

    y = x**100 + x + 1
  end function f

  function g(x) result (y)
    class(*), intent(in) :: x
    class(*), allocatable :: y

    y = x**2 + x + 1
  end function g

end program modular_arithmetic_task
Output:
$ gfortran -O2 -fbounds-check -Wall -Wextra -g modular_arithmetic_task-2.f90 && ./a.out
f(10) ≅ 1   (mod 13)

f applied to a regular integer would overflow, so, in what
follows, instead we use g(x) = x**2 + x + 1

g(10) = 111
g(10) ≅ 7   (mod 13)

FreeBASIC

Translation of: Visual Basic .NET
Type ModInt
    As Ulongint Value
    As Ulongint Modulo
End Type

Function Add_(lhs As ModInt, rhs As ModInt) As ModInt
    If lhs.Modulo <> rhs.Modulo Then Print "Cannot add rings with different modulus": End
    Dim res As ModInt
    res.Value = (lhs.Value + rhs.Value) Mod lhs.Modulo
    res.Modulo = lhs.Modulo
    Return res
End Function

Function Multiply(lhs As ModInt, rhs As ModInt) As ModInt
    If lhs.Modulo <> rhs.Modulo Then Print "Cannot multiply rings with different modulus": End
    Dim res As ModInt
    res.Value = (lhs.Value * rhs.Value) Mod lhs.Modulo
    res.Modulo = lhs.Modulo
    Return res
End Function

Function One(self As ModInt) As ModInt
    Dim res As ModInt
    res.Value = 1
    res.Modulo = self.Modulo
    Return res
End Function

Function Power(self As ModInt, p As Ulongint) As ModInt
    If p < 0 Then Print "p must be zero or greater": End
    Dim pp As Ulongint = p
    Dim pwr As ModInt = One(self)
    While pp > 0
        pp -= 1
        pwr = Multiply(pwr, self)
    Wend
    Return pwr
End Function

Function F(x As ModInt) As ModInt
    Return Add_(Power(x, 100), Add_(x, One(x)))
End Function

Dim x As ModInt
x.Value = 10
x.Modulo = 13
Dim y As ModInt = F(x)
Print Using "x ^ 100 + x + 1 for x = ModInt(&, &) is ModInt(&, &)"; x.Value; x.Modulo; y.Value; y.Modulo

Sleep
Output:
x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(1, 13)

Go

Go does not allow redefinition of operators. That element of the task cannot be done in Go. The element of defining f so that it can be used with any ring however can be done, just not with the syntactic sugar of operator redefinition.

package main

import "fmt"

// Define enough of a ring to meet the needs of the task.  Addition and
// multiplication are mentioned in the task; multiplicative identity is not
// mentioned but is useful for the power function.

type ring interface {
    add(ringElement, ringElement) ringElement
    mul(ringElement, ringElement) ringElement
    mulIdent() ringElement
}

type ringElement interface{}

// Define a power function that works for any ring.

func ringPow(r ring, a ringElement, p uint) (pow ringElement) {
    for pow = r.mulIdent(); p > 0; p-- {
        pow = r.mul(pow, a)
    }
    return
}

// The task function f has that constant 1 in it.
// Define a special kind of ring that has this element.

type oneRing interface {
    ring
    one() ringElement // return ring element corresponding to '1'
}

// Now define the required function f.
// It works for any ring (that has a "one.")

func f(r oneRing, x ringElement) ringElement {
    return r.add(r.add(ringPow(r, x, 100), x), r.one())
}

// With rings and the function f defined in a general way, now define
// the specific ring of integers modulo n.

type modRing uint // value is congruence modulus n

func (m modRing) add(a, b ringElement) ringElement {
    return (a.(uint) + b.(uint)) % uint(m)
}

func (m modRing) mul(a, b ringElement) ringElement {
    return (a.(uint) * b.(uint)) % uint(m)
}

func (modRing) mulIdent() ringElement { return uint(1) }

func (modRing) one() ringElement { return uint(1) }

// Demonstrate the general function f on the specific ring with the
// specific values.

func main() {
    fmt.Println(f(modRing(13), uint(10)))
}
Output:
1

Haskell

-- We use a couple of GHC extensions to make the program cooler.  They let us
-- use / as an operator and 13 as a literal at the type level.  (The library
-- also provides the fancy Zahlen (ℤ) symbol as a synonym for Integer.)

{-# Language DataKinds #-}
{-# Language TypeOperators #-}

import Data.Modular

f :: /13 -> /13
f x = x^100 + x + 1

main :: IO ()
main = print (f 10)
Output:
./modarith 
1

J

J does not allow "operator redefinition", but J's operators are capable of operating consistently on values which represent modular integers:

 f=: (+./1 1,:_101{.1x)&p.

Task example:

   13|f 10
1

Java

Translation of: Kotlin
Works with: Java version 8
public class ModularArithmetic {
    private interface Ring<T> {
        Ring<T> plus(Ring<T> rhs);

        Ring<T> times(Ring<T> rhs);

        int value();

        Ring<T> one();

        default Ring<T> pow(int p) {
            if (p < 0) {
                throw new IllegalArgumentException("p must be zero or greater");
            }

            int pp = p;
            Ring<T> pwr = this.one();
            while (pp-- > 0) {
                pwr = pwr.times(this);
            }
            return pwr;
        }
    }

    private static class ModInt implements Ring<ModInt> {
        private int value;
        private int modulo;

        private ModInt(int value, int modulo) {
            this.value = value;
            this.modulo = modulo;
        }

        @Override
        public Ring<ModInt> plus(Ring<ModInt> other) {
            if (!(other instanceof ModInt)) {
                throw new IllegalArgumentException("Cannot add an unknown ring.");
            }
            ModInt rhs = (ModInt) other;
            if (modulo != rhs.modulo) {
                throw new IllegalArgumentException("Cannot add rings with different modulus");
            }
            return new ModInt((value + rhs.value) % modulo, modulo);
        }

        @Override
        public Ring<ModInt> times(Ring<ModInt> other) {
            if (!(other instanceof ModInt)) {
                throw new IllegalArgumentException("Cannot multiple an unknown ring.");
            }
            ModInt rhs = (ModInt) other;
            if (modulo != rhs.modulo) {
                throw new IllegalArgumentException("Cannot multiply rings with different modulus");
            }
            return new ModInt((value * rhs.value) % modulo, modulo);
        }

        @Override
        public int value() {
            return value;
        }

        @Override
        public Ring<ModInt> one() {
            return new ModInt(1, modulo);
        }

        @Override
        public String toString() {
            return String.format("ModInt(%d, %d)", value, modulo);
        }
    }

    private static <T> Ring<T> f(Ring<T> x) {
        return x.pow(100).plus(x).plus(x.one());
    }

    public static void main(String[] args) {
        ModInt x = new ModInt(10, 13);
        Ring<ModInt> y = f(x);
        System.out.print("x ^ 100 + x + 1 for x = ModInt(10, 13) is ");
        System.out.println(y);
        System.out.flush();
    }
}
Output:
x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(1, 13)

jq

Works with: jq

Works with gojq, the Go implementation of jq

This entry focuses on the requirement that the function, f, "should behave the same way with normal and modular integers."

To illustrate that the function `ring::f` defined here does satisfy this requirement, we will evaluate it at both the integer 1 and the element «10 % 13» of ℤ/13ℤ.

To keep the distinctions between functions defined on different types clear, this entry uses jq's support for name spaces. Specifically, we will use the prefix "modint::" for the modular arithmetic functions, and "ring::" for the generic ring functions.

Since jq supports neither redefining any of the symbolic operators (such as "+") nor dynamic dispatch, ring functions (such as `ring::add`) must be written with the specific rings that are to be supported in mind.

Preliminaries

def assert($e; $msg): if $e then . else "assertion violation @ \($msg)" | error end;

def is_integer: type=="number" and floor == .;

# To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);

Modular Arithmetic

# "ModularArithmetic" objects are represented by JSON objects of the form: {value, mod}.
# The function modint::assert/0 checks the input is of this form with integer values.

def is_modint: type=="object" and has("value") and has("mod");

def modint::assert:
   assert(type=="object"; "object expected")
   | assert(has("value"); "object should have a value")
   | assert(has("mod"); "object should have a mod")
   | assert(.value | is_integer; "value should be an integer")
   | assert(.mod   | is_integer; "mod should be an integer");

def modint::make($value; $mod):
  assert($value|is_integer; "value should be an integer")
  | assert($mod|is_integer; "mod should be an integer")
  | { value: ($value % $mod), mod: $mod};

def modint::add($A; $B):
  if ($B|type) == "object"
  then assert($A.mod == $B.mod ; "modint::add")
  | modint::make( $A.value + $B.value; $A.mod )
  else modint::make( $A.value + $B; $A.mod )
  end;

def modint::mul($A; $B):
  if ($B|type) == "object"
  then assert($A.mod == $B.mod ; "mul")
  | modint::make( $A.value * $B.value; $A.mod )
  else modint::make( $A.value * $B; $A.mod )
  end;

def modint::pow($A; $pow):
  assert($pow | is_integer; "pow")
  | reduce range(0; $pow) as $i ( modint::make(1; $A.mod);
      modint::mul( .; $A) );

# pretty print
def modint::pp: "«\(.value) % \(.mod)»";

Ring Functions

def ring::add($A; $B):
  if $A|is_modint then modint::add($A; $B)
  elif $A|is_integer then $A + $B
  else "ring::add" | error
  end;

def ring::mul($A; $B):
  if $A|is_modint then modint::mul($A; $B)
  elif $A|is_integer then $A * $B
  else "ring::mul" | error
  end;

def ring::pow($A; $B):
  if $A|is_modint then modint::pow($A; $B)
  elif $A|is_integer then $A|power($B)
  else "ring::pow" | error
  end;

def ring::pp:
  if is_modint then modint::pp
  elif is_integer then .
  else "ring::pp" | error
  end;

def ring::f($x):
  ring::add( ring::add( ring::pow($x; 100); $x); 1);

Evaluating ring::f

def main:
  (ring::f(1) | "f(\(1)) => \(.)"),
  (modint::make(10;13)
   | ring::f(.) as $out
    | "f(\(ring::pp)) => \($out|ring::pp)");
Output:
f(1) => 3
f(«10 % 13») => «1 % 13»

Julia

Works with: Julia version 0.6

Implements the Modulo struct and basic operations.

struct Modulo{T<:Integer} <: Integer
    val::T
    mod::T
    Modulo(n::T, m::T) where T = new{T}(mod(n, m), m)
end
modulo(n::Integer, m::Integer) = Modulo(promote(n, m)...)

Base.show(io::IO, md::Modulo) = print(io, md.val, " (mod $(md.mod))")
Base.convert(::Type{T}, md::Modulo) where T<:Integer = convert(T, md.val)
Base.copy(md::Modulo{T}) where T = Modulo{T}(md.val, md.mod)

Base.:+(md::Modulo) = copy(md)
Base.:-(md::Modulo) = Modulo(md.mod - md.val, md.mod)
for op in (:+, :-, :*, , :^)
    @eval function Base.$op(a::Modulo, b::Integer)
        val = $op(a.val, b)
        return Modulo(mod(val, a.mod), a.mod)
    end
    @eval Base.$op(a::Integer, b::Modulo) = $op(b, a)
    @eval function Base.$op(a::Modulo, b::Modulo)
        if a.mod != b.mod throw(InexactError()) end
        val = $op(a.val, b.val)
        return Modulo(mod(val, a.mod), a.mod)
    end
end

f(x) = x ^ 100 + x + 1
@show f(modulo(10, 13))
Output:
f(modulo(10, 13)) = 11 (mod 13)

Kotlin

// version 1.1.3

interface Ring<T> {
    operator fun plus(other: Ring<T>): Ring<T>
    operator fun times(other: Ring<T>): Ring<T>
    val value: Int
    val one: Ring<T>
}

fun <T> Ring<T>.pow(p: Int): Ring<T> {
    require(p >= 0)
    var pp = p
    var pwr = this.one
    while (pp-- > 0) pwr *= this
    return pwr
}

class ModInt(override val value: Int, val modulo: Int): Ring<ModInt> {
 
    override operator fun plus(other: Ring<ModInt>): ModInt {
        require(other is ModInt &&  modulo == other.modulo)
        return ModInt((value + other.value) % modulo, modulo)
    }
    
    override operator fun times(other: Ring<ModInt>): ModInt {
        require(other is ModInt && modulo == other.modulo)
        return ModInt((value * other.value) % modulo, modulo)
    }

    override val one get() = ModInt(1, modulo)

    override fun toString() = "ModInt($value, $modulo)"
}

fun <T> f(x: Ring<T>): Ring<T> = x.pow(100) + x + x.one

fun main(args: Array<String>) {
    val x = ModInt(10, 13)
    val y = f(x)
    println("x ^ 100 + x + 1 for x == ModInt(10, 13) is $y")
}
Output:
x ^ 100 + x + 1 for x == ModInt(10, 13) is ModInt(1, 13)

Lua

function make(value, modulo)
    local v = value % modulo
    local tbl = {value=v, modulo=modulo}

    local mt = {
        __add = function(lhs, rhs)
            if type(lhs) == "table" then
                if type(rhs) == "table" then
                    if lhs.modulo ~= rhs.modulo then
                        error("Cannot add rings with different modulus")
                    end
                    return make(lhs.value + rhs.value, lhs.modulo)
                else
                    return make(lhs.value + rhs, lhs.modulo)
                end
            else
                error("lhs is not a table in +")
            end
        end,
        __mul = function(lhs, rhs)
            if lhs.modulo ~= rhs.modulo then
                error("Cannot multiply rings with different modulus")
            end
            return make(lhs.value * rhs.value, lhs.modulo)
        end,
        __pow = function(b,p)
            if p<0 then
                error("p must be zero or greater")
            end

            local pp = p
            local pwr = make(1, b.modulo)
            while pp > 0 do
                pp = pp - 1
                pwr = pwr * b
            end
            return pwr
        end,
        __concat = function(lhs, rhs)
            if type(lhs) == "table" and type(rhs) == "string" then
                return "ModInt("..lhs.value..", "..lhs.modulo..")"..rhs
            elseif type(lhs) == "string" and type(rhs) == "table" then
                return lhs.."ModInt("..rhs.value..", "..rhs.modulo..")"
            else
                return "todo"
            end
        end
    }

    setmetatable(tbl, mt)
    return tbl
end

function func(x)
    return x ^ 100 + x + 1
end

-- main
local x = make(10, 13)
local y = func(x)
print("x ^ 100 + x + 1 for "..x.." is "..y)
Output:
x ^ 100 + x + 1 for ModInt(10, 13) is ModInt(1, 13)

Mathematica/Wolfram Language

For versions prior to 13.3, the best way to do it is probably to use the finite fields package.

<< FiniteFields`
x^100 + x + 1 /. x -> GF[13]@{10}
Output:

{1}13

Version 13.3 has a "complete, consistent coverage of all finite fields":

OutputForm[
  x^100 + x + 1 /. x -> FiniteField[13][10]
]

We have to show the `OutputForm` though, because the `StandardForm` is not easy to render here.

Output:
FiniteFieldElement[<1,13,1,+>]

Mercury

Works with: Mercury version 22.01.1

Numbers have to be converted to ordinary(Number) or modular(Number, Modulus) before they are plugged into f. The two kinds can be mixed: if any operation involves a "modular" number, then the result will be "modular", but otherwise the result will be "ordinary".

(There are limitations in Mercury's current system of overloads that make it more difficult than I care to deal with, to do this so that f could be invoked directly on the integer type.)

%% -*- mode: mercury; prolog-indent-width: 2; -*-

:- module modular_arithmetic_task.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.

:- implementation.
:- import_module exception.
:- import_module integer.

:- type modular_integer
   ---> modular(integer, integer)
   ;    ordinary(integer).

:- func operate((func(integer, integer) = integer),
                 modular_integer, modular_integer) = modular_integer.
operate(OP, modular(A, M1), modular(B, M2)) = C :-
  if (M1 = M2)
  then (C = modular(mod(OP(A, B), M1), M1))
  else throw("mismatched moduli").
operate(OP, modular(A, M), ordinary(B)) = C :-
  C = modular(mod(OP(A, B), M), M).
operate(OP, ordinary(A), modular(B, M)) = C :-
  C = modular(mod(OP(A, B), M), M).
operate(OP, ordinary(A), ordinary(B)) = C :-
  C = ordinary(OP(A, B)).

:- func '+'(modular_integer, modular_integer) = modular_integer.
(A : modular_integer) + (B : modular_integer) = operate(+, A, B).

:- func pow(modular_integer, modular_integer) = modular_integer.
pow(A : modular_integer, B : modular_integer) = operate(pow, A, B).

:- pred display(modular_integer::in, io::di, io::uo) is det.
display(X, !IO) :-
  if (X = modular(A, _)) then print(A, !IO)
  else if (X = ordinary(A)) then print(A, !IO)
  else true.

:- func f(modular_integer) = modular_integer.
f(X) = Y :-
  Y = pow(X, ordinary(integer(100))) + X
      + ordinary(integer(1)).

main(!IO) :-
  X1 = ordinary(integer(10)),
  X2 = modular(integer(10), integer(13)),
  print("No modulus:  ", !IO),
  display(f(X1), !IO),
  nl(!IO),
  print("modulus 13:  ", !IO),
  display(f(X2), !IO),
  nl(!IO).

:- end_module modular_arithmetic_task.
Output:
$ mmc --use-subdirs --make modular_arithmetic_task && ./modular_arithmetic_task
Making Mercury/int3s/modular_arithmetic_task.int3
Making Mercury/ints/modular_arithmetic_task.int
Making Mercury/cs/modular_arithmetic_task.c
Making Mercury/os/modular_arithmetic_task.o
Making modular_arithmetic_task
No modulus:  10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13:  1

Nim

Modular integers are represented as distinct integers with a modulus N managed by the compiler.

import macros, sequtils, strformat, strutils

const Subscripts: array['0'..'9', string] = ["₀", "₁", "₂", "₃", "₄", "₅", "₆", "₇", "₈", "₉"]

# Modular integer with modulus N.
type ModInt[N: static int] = distinct int


#---------------------------------------------------------------------------------------------------
# Creation.

func initModInt[N](n: int): ModInt[N] =
  ## Create a modular integer from an integer.
  static:
    when N < 2: error "Modulus must be greater than 1."
  if n >= N: raise newException(ValueError, &"value must be in 0..{N - 1}.")
  result = ModInt[N](n)


#---------------------------------------------------------------------------------------------------
# Arithmetic operations: ModInt op ModInt, ModInt op int and int op ModInt.

func `+`*[N](a, b: ModInt[N]): ModInt[N] =
  ModInt[N]((a.int + b.int) mod N)

func `+`*[N](a: ModInt[N]; b: int): ModInt[N] =
  a + initModInt[N](b)

func `+`*[N](a: int; b: ModInt[N]): ModInt[N] =
  initModInt[N](a) + b

func `*`*[N](a, b: ModInt[N]): ModInt[N] =
  ModInt[N]((a.int * b.int) mod N)

func `*`*[N](a: ModInt[N]; b: int): ModInt[N] =
  a * initModInt[N](b)

func `*`*[N](a: int; b: ModInt[N]): ModInt[N] =
  initModInt[N](a) * b

func `^`*[N](a: ModInt[N]; n: Natural): ModInt[N] =
  var a = a
  var n = n
  result = initModInt[N](1)
  while n > 0:
    if (n and 1) != 0:
      result = result * a
    n = n shr 1
    a = a * a


#---------------------------------------------------------------------------------------------------
# Representation of a modular integer as a string.

template subscript(n: Natural): string =
  mapIt($n, Subscripts[it]).join()

func `$`(a: ModInt): string =
  &"{a.int}{subscript(a.N)})"


#---------------------------------------------------------------------------------------------------
# The function "f" defined for any modular integer, the same way it would be defined for an
# integer argument (except that such a function would be of no use as it would overflow for
# any argument different of 0 and 1).

func f(x: ModInt): ModInt = x^100 + x + 1


#———————————————————————————————————————————————————————————————————————————————————————————————————

when isMainModule:

  var x = initModInt[13](10)
  echo &"f({x}) = {x}^100 + {x} + 1 = {f(x)}."
Output:
f(10₁₃) = 10₁₃^100 + 10₁₃ + 1 = 1₁₃.

ObjectIcon

# -*- ObjectIcon -*-
#
# Object Icon has a "Number" class (with subclasses) that has "add"
# and "mul" methods. These methods can be implemented in a modular
# numbers class, even though we cannot redefine the symbolic operators
# "+" and "*". Neither can we inherit from Number, but that turns out
# not to get in our way.
#

import io
import ipl.types
import numbers (Rat)
import util (need_integer)

procedure main ()
  local x

  x := Rat (10)     # The number 10 as a rational with denominator 1.
  write ("no modulus:  ", f(x).n)

  x := Modular (10, 13)
  write ("modulus 13:  ", f(x).least_residue)
end

procedure f(x)
  return npow(x, 100).add(x).add(1)
end

procedure npow (x, i)
  # Raise a number to a non-negative power, using the methods of its
  # class. The algorithm is the squaring method.

  local accum, i_halved

  if i < 0 then runerr ("Non-negative number expected", i)

  accum := typeof(x) (1)

  # Perhaps the following hack can be eliminated?
  if is (x, Modular) then accum := Modular (1, x.modulus)

  while i ~= 0 do
  {
    i_halved := i / 2
    if i_halved + i_halved ~= i then accum := x.mul(accum)
    x := x.mul(x)
    i := i_halved
  }
  return accum
end

class Modular ()
  public const least_residue
  public const modulus

  public new (num, m)
    if /m & is (num, Modular) then
    {
      self.least_residue := num.least_residue
      self.modulus := num.modulus
    }
    else
    {
      /m := 0
      m := need_integer (m)
      if m < 0 then runerr ("Non-negative number expected", m)
      self.modulus := m
      num := need_integer (num)
      if m = 0 then
        self.least_residue := num # A regular integer.
      else
        self.least_residue := residue (num, modulus)
    }
    return
  end

  public add (x)
    if is (x, Modular) then x := x.least_residue
    return Modular (least_residue + x, need_modulus (self, x))
  end

  public mul (x)
    if is (x, Modular) then x := x.least_residue
    return Modular (least_residue * x, need_modulus (self, x))
  end
end

procedure need_modulus (x, y)
  local mx, my

  mx := if is (x, Modular) then x.modulus else 0
  my := if is (y, Modular) then y.modulus else 0
  if mx = 0 then
  {
    if my = 0 then runerr ("Cannot determine the modulus", [x, y])
    mx := my
  }
  else if my = 0 then
    my := mx
  if mx ~= my then runerr ("Mismatched moduli", [x, y])
  return mx
end

procedure residue(i, m, j)
  # Residue for j-based integers, taken from the Arizona Icon IPL
  # (which is in the public domain). With the default value j=0, this
  # is what we want for reducing numbers to their least residues.
  /j := 0
  i %:= m
  if i < j then i +:= m
  return i
end
Output:
$ oiscript modular_arithmetic_task_OI.icn
no modulus:  10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13:  1

Owl Lisp

Translation of: Scheme
;; Owl Lisp, though a dialect of Scheme, has no true variables: it has
;; only value-bindings. We cannot use "make-parameter" to specify an
;; optional modulus. Instead let us introduce a new type for modular
;; integers.

(define (modular? x)
  ;; The new type is simply a pair of integers.
  (and (pair? x) (integer? (car x)) (integer? (cdr x))))

(define (enhanced-op op)
  (lambda (x y)
    (if (modular? x)
        (if (modular? y)
            (begin
              (unless (= (cdr x) (cdr y))
                (error "mismatched moduli"))
              (cons (floor-remainder (op (car x) (car y)) (cdr x))
                    (cdr x)))
            (cons (floor-remainder (op (car x) y) (cdr x))
                  (cdr x)))
        (if (modular? y)
            (cons (floor-remainder (op x (car y)) (cdr y))
                  (cdr y))
            (op x y)))))

(define enhanced+ (enhanced-op +))
(define enhanced-expt (enhanced-op expt))

(define (f x)
  ;; Temporarily redefine + and expt so they can handle either regular
  ;; numbers or modular integers.
  (let ((+ enhanced+)
        (expt enhanced-expt))
    ;; Here is a definition of f(x), in the notation of Owl Lisp:
    (+ (+ (expt x 100) x) 1)))

;; Use f on regular integers.
(display "No modulus:  ")
(display (f 10))
(newline)

(display "modulus 13:  ")
(display (car (f (cons 10 13))))
(newline)
Output:
$ ol modular_arithmetic_task_Owl.scm
No modulus:  10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13:  1

PARI/GP

This feature exists natively in GP:

Mod(3,7)+Mod(4,7)

Perl

There is a CPAN module called Math::ModInt which does the job.

use Math::ModInt qw(mod);
sub f { my $x = shift; $x**100 + $x + 1 };
print f mod(10, 13);
Output:
mod(1, 13)

Phix

Phix does not allow operator overloading, but an f() which is agnostic about whether its parameter is a modular or normal int, we can do.

type mi(object m)
    return sequence(m) and length(m)=2 and integer(m[1]) and integer(m[2])
end type
 
type mii(object m)
    return mi(m) or atom(m)
end type
 
function mi_one(mii a)
    if atom(a) then a=1 else a = {1,a[2]} end if
    return a
end function
 
function mi_add(mii a, mii b)
    if atom(a) then
        if not atom(b) then throw("error") end if
        return a+b
    end if
    if a[2]!=b[2] then throw("error") end if
    a[1] = mod(a[1]+b[1],a[2])
    return a
end function
 
function mi_mul(mii a, mii b)
    if atom(a) then
        if not atom(b) then throw("error") end if
        return a*b
    end if
    if a[2]!=b[2] then throw("error") end if
    a[1] = mod(a[1]*b[1],a[2])
    return a
end function
 
function mi_power(mii x, integer p)
    mii res = mi_one(x)
    for i=1 to p do
        res = mi_mul(res,x)
    end for
    return res
end function
 
function mi_print(mii m)
    return sprintf(iff(atom(m)?"%g":"modint(%d,%d)"),m)
end function
 
function f(mii x)
    return mi_add(mi_power(x,100),mi_add(x,mi_one(x)))
end function
 
procedure test(mii x)
    printf(1,"x^100 + x + 1 for x == %s is %s\n",{mi_print(x),mi_print(f(x))})
end procedure
test(10)
test({10,13})
Output:
x^100 + x + 1 for x == 10 is 1e+100
x^100 + x + 1 for x == modint(10,13) is modint(1,13)

Prolog

Works with SWI-Prolog versin 6.4.1 and module lambda (found there : http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl ).

:- use_module(library(lambda)).

congruence(Congruence,  In, Fun, Out) :-
	maplist(Congruence +\X^Y^(Y is X mod Congruence), In, In1),
	call(Fun, In1, Out1),
	maplist(Congruence +\X^Y^(Y is X mod Congruence), Out1, Out).

fun_1([X], [Y]) :-
	Y is X^100 + X + 1.

fun_2(L, [R]) :-
	sum_list(L, R).
Output:
 ?- congruence(13, [10], fun_1, R).
R = [1].

 ?- congruence(13, [10, 15, 13, 9, 22], fun_2, R).
R = [4].

 ?- congruence(13, [10, 15, 13, 9, 22], maplist(\X^Y^(Y is X * 13)), R).
R = [0,0,0,0,0].

Python

Works with: Python version 3.x

We need to implement a Modulo type first, then give one of its instances to the "f" function.
Thanks to duck typing, the function doesn't need to care about the actual type it's given. We also use the dynamic nature of Python to dynamically build the operator overload methods and avoid repeating very similar code.

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)

Quackery

Quackery is an extensible assembler for the Quackery Virtual Processor, which is implemented in Python3 (but could be implemented in any language). The QVP recognises three static types; Number (Python Int), Nest (Python List) and Operator (Python function). Adding more static types would require adding functionality to the QVP by modifying the source code for Quackery.

However it is possible to extend the assembler to include dynamic typing without modifying the QVP. The first part of the code presented here adds just sufficient dynamic typing to Quackery to fulfil the requirements of this task. It could be considered a first sketch towards adding more comprehensive dynamic typing to Quackery.

The second part of the code uses this to overload the Quackery words + and **.

The third part fulfils the requirements of this task.

[ stack ]                        is modulus           (     --> s )  

[ this ]                         is modular           (     --> [ )

[ modulus share mod 
  modular nested join ]          is modularise        (   n --> N )

[ dup nest? iff 
    [ -1 peek modular oats ]
  else [ drop false ] ]          is modular?          (   N --> b )

[ modular? swap
  modular? or ]                  is 2modular?         ( N N --> b )

[ dup modular? if [ 0 peek ] ]   is demodularise      (   N --> n )

[ demodularise swap
  demodularise swap ]            is 2demodularise     ( N N --> n )

[ dup $ '' = if
    [ $ '"modularify(2-->1)" '
      $ "needs a name after it."
      join message put bail ]
  nextword
  $ "[ 2dup 2modular? iff
     [ 2demodularise " over join
  $ " modularise ] 
      else " join over join
  $ " ] is " join swap join
  space join 
  swap join ]                builds modularify(2-->1) (     -->   )

( --------------------------------------------------------------- )

                  modularify(2-->1) +                 ( N N --> N )

                  modularify(2-->1) **                ( N N --> N )

( --------------------------------------------------------------- )

[ dup 100 ** + 1 + ]             is f                 (   N --> N )

13 modulus put
10 f echo cr
10 modularise f echo
modulus release cr

Output:

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
[ 1 modular ]


Racket

#lang racket
(require racket/require
         ;; grab all "mod*" names, but get them without the "mod", so
         ;; `+' and `expt' is actually `mod+' and `modexpt'
         (filtered-in (λ(n) (and (regexp-match? #rx"^mod" n)
                                 (regexp-replace #rx"^mod" n "")))
                      math)
         (only-in math with-modulus))
(define (f x) (+ (expt x 100) x 1))
(with-modulus 13 (f 10))
;; => 1

Raku

(formerly Perl 6)

We'll use the FiniteFields repo.

use FiniteField;
$*modulus = 13;

sub f(\x) { x**100 + x + 1};

say f(10);
Output:
1

Red

This implementation of +,-,*,/ uses a loose test (object?) to check operands type. As soon as one is a modular integer, the other one is treated as a modular integer too.

Red ["Modular arithmetic"]

; defining the modular integer class, and a constructor
modulus: 13
m: function [n] [
	either object? n [make n []] [context [val: n % modulus]]
]                           
; redefining operators +, -, *, / to include modular integers
foreach [op fun][+ add - subtract * multiply / divide][
	set op make op! function [a b] compose/deep [
		either any [object? a object? b][
			a: m a
			b: m b
			m (fun) a/val b/val
		][(fun) a b]	
	]
]
; redefining power - ** ; second operand must be an integer
**: make op! function [a n] [ 
	either object? a [
		tmp: 1
		loop n [tmp: tmp * a/val % modulus]
		m tmp
	][power a n]	
]
; testing
f: function [x] [x ** 100 + x + 1]
print ["f definition is:" mold :f]
print ["f((integer) 10) is:" f 10]
print ["f((modular) 10) is: (modular)" f m 10]
Output:
f definition is: func [x][x ** 100 + x + 1]
f((integer) 10) is: 1.0e100
f((modular) 10) is: (modular) val: 1

Ruby

# stripped version of Andrea Fazzi's submission to Ruby Quiz #179

class Modulo
  include Comparable

  def initialize(n = 0, m = 13)
    @n, @m = n % m, m
  end

  def to_i
    @n
  end
 
  def <=>(other_n)
    @n <=> other_n.to_i
  end

  [:+, :-, :*, :**].each do |meth|
    define_method(meth) { |other_n| Modulo.new(@n.send(meth, other_n.to_i), @m) }
  end

  def coerce(numeric)
    [numeric, @n]
  end

end

# Demo
x, y = Modulo.new(10), Modulo.new(20)

p x > y          # true
p x == y         # false
p [x,y].sort     #[#<Modulo:0x000000012ae0f8 @n=7, @m=13>, #<Modulo:0x000000012ae148 @n=10, @m=13>]
p x + y          ##<Modulo:0x0000000117e110 @n=4, @m=13>
p 2 + y          # 9
p y + 2          ##<Modulo:0x00000000ad1d30 @n=9, @m=13>

p x**100 + x +1  ##<Modulo:0x00000000ad1998 @n=1, @m=13>

Scala

Output:
Best seen running in your browser either by ScalaFiddle (ES aka JavaScript, non JVM) or Scastie (remote JVM).
object ModularArithmetic extends App {
  private val x = new ModInt(10, 13)
  private val y = f(x)

  private def f[T](x: Ring[T]) = (x ^ 100) + x + x.one

  private trait Ring[T] {
    def +(rhs: Ring[T]): Ring[T]

    def *(rhs: Ring[T]): Ring[T]

    def one: Ring[T]

    def ^(p: Int): Ring[T] = {
      require(p >= 0, "p must be zero or greater")
      var pp = p
      var pwr = this.one
      while ( {
        pp -= 1;
        pp
      } >= 0) pwr = pwr * this
      pwr
    }
  }

  private class ModInt(var value: Int, var modulo: Int) extends Ring[ModInt] {
    def +(other: Ring[ModInt]): Ring[ModInt] = {
      require(other.isInstanceOf[ModInt], "Cannot add an unknown ring.")
      val rhs = other.asInstanceOf[ModInt]
      require(modulo == rhs.modulo, "Cannot add rings with different modulus")
      new ModInt((value + rhs.value) % modulo, modulo)
    }

    def *(other: Ring[ModInt]): Ring[ModInt] = {
      require(other.isInstanceOf[ModInt], "Cannot multiple an unknown ring.")
      val rhs = other.asInstanceOf[ModInt]
      require(modulo == rhs.modulo,
        "Cannot multiply rings with different modulus")
      new ModInt((value * rhs.value) % modulo, modulo)
    }

    override def one = new ModInt(1, modulo)

    override def toString: String = f"ModInt($value%d, $modulo%d)"
  }

  println("x ^ 100 + x + 1 for x = ModInt(10, 13) is " + y)

}

Scheme

Works with: Gauche Scheme version 0.9.12
Works with: Chibi Scheme version 0.10.0
Works with: CHICKEN Scheme version 5.3.0

The program is for R7RS Scheme.

"Modular integers" are not introduced here as a type distinct from "integers". Instead, a modulus may be imposed on "enhanced" versions of arithmeti operations.

Note the use of floor-remainder instead of truncate-remainder. The latter would function incorrectly if there were negative numbers.

(cond-expand
  (r7rs)
  (chicken (import r7rs)))

(import (scheme base))
(import (scheme write))

(define *modulus*
  (make-parameter
   #f
   (lambda (mod)
     (if (or (not mod)
             (and (exact-integer? mod)
                  (positive? mod)))
         mod
         (error "not a valid modulus")))))

(define-syntax enhanced-op
  (syntax-rules ()
    ((_ op)
     (lambda args
       (let ((mod (*modulus*))
             (tentative-result (apply op args)))
         (if mod
             (floor-remainder tentative-result mod)
             tentative-result))))))

(define enhanced+ (enhanced-op +))
(define enhanced-expt (enhanced-op expt))

(define (f x)
  ;; Temporarily redefine + and expt so they can handle either regular
  ;; numbers or modular integers.
  (let ((+ enhanced+)
        (expt enhanced-expt))
    ;; Here is a definition of f(x), in the notation of Scheme:
    (+ (expt x 100) x 1)))

;; Use f on regular integers.
(display "No modulus:  ")
(display (f 10))
(newline)

;; Use f on modular integers.
(parameterize ((*modulus* 13))
  (display "modulus 13:  ")
  (display (f 10))
  (newline))
Output:
$ gosh modular_arithmetic_task.scm 
No modulus:  10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13:  1

Sidef

Translation of: Ruby
class Modulo(n=0, m=13) {

  method init {
     (n, m) = (n % m, m)
  }

  method to_n { n }

  < + - * ** >.each { |meth|
      Modulo.def_method(meth, method(n2) { Modulo(n.(meth)(n2.to_n), m) })
  }

  method to_s { "#{n} 「mod #{m}」" }
}

func f(x) { x**100 + x + 1 }
say f(Modulo(10, 13))
Output:
1 「mod 13」

Swift

Translation of: Scala
precedencegroup ExponentiationGroup {
  higherThan: MultiplicationPrecedence
}

infix operator ** : ExponentiationGroup

protocol Ring {
  associatedtype RingType: Numeric

  var one: Self { get }

  static func +(_ lhs: Self, _ rhs: Self) -> Self
  static func *(_ lhs: Self, _ rhs: Self) -> Self
  static func **(_ lhs: Self, _ rhs: Int) -> Self
}

extension Ring  {
  static func **(_ lhs: Self, _ rhs: Int) -> Self {
    var ret = lhs.one

    for _ in stride(from: rhs, to: 0, by: -1) {
      ret = ret * lhs
    }

    return ret
  }
}

struct ModInt: Ring {
  typealias RingType = Int

  var value: Int
  var modulo: Int

  var one: ModInt { ModInt(1, modulo: modulo) }

  init(_ value: Int, modulo: Int) {
    self.value = value
    self.modulo = modulo
  }

  static func +(lhs: ModInt, rhs: ModInt) -> ModInt {
    precondition(lhs.modulo == rhs.modulo)

    return ModInt((lhs.value + rhs.value) % lhs.modulo, modulo: lhs.modulo)
  }

  static func *(lhs: ModInt, rhs: ModInt) -> ModInt {
    precondition(lhs.modulo == rhs.modulo)

    return ModInt((lhs.value * rhs.value) % lhs.modulo, modulo: lhs.modulo)
  }
}

func f<T: Ring>(_ x: T) -> T { (x ** 100) + x + x.one }

let x = ModInt(10, modulo: 13)
let y = f(x)

print("x ^ 100 + x + 1 for x = ModInt(10, 13) is \(y)")
Output:
x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(value: 1, modulo: 13)

Tcl

Tcl does not permit overriding of operators, but does not force an expression to be evaluated as a standard expression.
Creating a parser and custom evaluation engine is relatively straight-forward, as is shown here.

Library: Tcllib (Package: pt::pgen)
package require Tcl 8.6
package require pt::pgen

###
### A simple expression parser for a subset of Tcl's expression language
###

# Define the grammar of expressions that we want to handle
set grammar {
PEG Calculator (Expression)
    Expression	<- Term (' '* AddOp ' '* Term)*			;
    Term	<- Factor (' '* MulOp ' '* Factor)*		;
    Fragment	<- '(' ' '* Expression ' '*  ')' / Number / Var	;
    Factor	<- Fragment (' '* PowOp ' '* Fragment)*		;
    Number	<- Sign? Digit+					;
    Var		<- '$' ( 'x'/'y'/'z' )				;

    Digit	<- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9'	;
    Sign	<- '-' / '+'					;
    MulOp	<- '*' / '/'					;
    AddOp	<- '+' / '-'					;
    PowOp	<- '**'						;
END;
}

# Instantiate the parser class
catch [pt::pgen peg $grammar snit -class Calculator -name Grammar]

# An engine that compiles an expression into Tcl code
oo::class create CompileAST {
    variable sourcecode opns
    constructor {semantics} {
	set opns $semantics
    }
    method compile {script} {
	# Instantiate the parser
	set c [Calculator]
	set sourcecode $script
	try {
	    return [my {*}[$c parset $script]]
	} finally {
	    $c destroy
	}
    }

    method Expression-Empty args {}
    method Expression-Compound {from to args} {
	foreach {o p} [list Expression-Empty {*}$args] {
	    set o [my {*}$o]; set p [my {*}$p]
	    set v [expr {$o ne "" ? "$o \[$v\] \[$p\]" : $p}]
	}
	return $v
    }
    forward Expression	my Expression-Compound
    forward Term	my Expression-Compound
    forward Factor	my Expression-Compound
    forward Fragment	my Expression-Compound

    method Expression-Operator {from to args} {
	list ${opns} [string range $sourcecode $from $to]
    }
    forward AddOp	my Expression-Operator
    forward MulOp	my Expression-Operator
    forward PowOp	my Expression-Operator

    method Number {from to args} {
	list ${opns} value [string range $sourcecode $from $to]
    }

    method Var {from to args} {
	list ${opns} variable [string range $sourcecode [expr {$from+1}] $to]
    }
}

None of the code above knows about modular arithmetic at all, or indeed about actual expression evaluation. Now we define the semantics that we want to actually use.

# The semantic evaluation engine; this is the part that knows mod arithmetic
oo::class create ModEval {
    variable mod
    constructor {modulo} {set mod $modulo}
    method value {literal} {return [expr {$literal}]}
    method variable {name} {return [expr {[set ::$name]}]}
    method + {a b} {return [expr {($a + $b) % $mod}]}
    method - {a b} {return [expr {($a - $b) % $mod}]}
    method * {a b} {return [expr {($a * $b) % $mod}]}
    method / {a b} {return [expr {($a / $b) % $mod}]}
    method ** {a b} {
	# Tcl supports bignums natively, so we use the naive version
	return [expr {($a ** $b) % $mod}]
    }
    export + - * / **
}

# Put all the pieces together
set comp [CompileAST new [ModEval create mod13 13]]

Finally, demonstrating…

set compiled [$comp compile {$x**100 + $x + 1}]
set x 10
puts "[eval $compiled] = $compiled"
Output:
1 = ::mod13 + [::mod13 + [::mod13 ** [::mod13 variable x] [::mod13 value 100]] [::mod13 variable x]] [::mod13 value 1]

VBA

Translation of: Phix
Option Base 1
Private Function mi_one(ByVal a As Variant) As Variant
    If IsArray(a) Then
        a(1) = 1
    Else
        a = 1
    End If
    mi_one = a
End Function

Private Function mi_add(ByVal a As Variant, b As Variant) As Variant
    If IsArray(a) Then
        If IsArray(b) Then
             If a(2) <> b(2) Then
                mi_add = CVErr(2019)
            Else
                a(1) = (a(1) + b(1)) Mod a(2)
                mi_add = a
            End If
        Else
            mi_add = CVErr(2018)
        End If
    Else
        If IsArray(b) Then
            mi_add = CVErr(2018)
        Else
           a = a + b
           mi_add = a
        End If
    End If
End Function

Private Function mi_mul(ByVal a As Variant, b As Variant) As Variant
    If IsArray(a) Then
        If IsArray(b) Then
            If a(2) <> b(2) Then
                mi_mul = CVErr(2019)
            Else
                a(1) = (a(1) * b(1)) Mod a(2)
                mi_mul = a
            End If
        Else
            mi_mul = CVErr(2018)
        End If
    Else
        If IsArray(b) Then
            mi_mul = CVErr(2018)
        Else
            a = a * b
            mi_mul = a
        End If
    End If
End Function
 
Private Function mi_power(x As Variant, p As Integer) As Variant
    res = mi_one(x)
    For i = 1 To p
        res = mi_mul(res, x)
    Next i
    mi_power = res
End Function
 
Private Function mi_print(m As Variant) As Variant
    If IsArray(m) Then
        s = "modint(" & m(1) & "," & m(2) & ")"
    Else
        s = CStr(m)
    End If
    mi_print = s
End Function
 
Private Function f(x As Variant) As Variant
    f = mi_add(mi_power(x, 100), mi_add(x, mi_one(x)))
End Function
 
Private Sub test(x As Variant)
    Debug.Print "x^100 + x + 1 for x == " & mi_print(x) & " is " & mi_print(f(x))
End Sub
Public Sub main()
    test 10
    test [{10,13}]
End Sub
Output:
x^100 + x + 1 for x == 10 is 1E+100
x^100 + x + 1 for x == modint(10,13) is modint(1,13)

Visual Basic .NET

Translation of: C#
Module Module1

    Interface IAddition(Of T)
        Function Add(rhs As T) As T
    End Interface

    Interface IMultiplication(Of T)
        Function Multiply(rhs As T) As T
    End Interface

    Interface IPower(Of T)
        Function Power(pow As Integer) As T
    End Interface

    Interface IOne(Of T)
        Function One() As T
    End Interface

    Class ModInt
        Implements IAddition(Of ModInt), IMultiplication(Of ModInt), IPower(Of ModInt), IOne(Of ModInt)

        Sub New(value As Integer, modulo As Integer)
            Me.Value = value
            Me.Modulo = modulo
        End Sub

        ReadOnly Property Value As Integer
        ReadOnly Property Modulo As Integer

        Public Function Add(rhs As ModInt) As ModInt Implements IAddition(Of ModInt).Add
            Return Me + rhs
        End Function

        Public Function Multiply(rhs As ModInt) As ModInt Implements IMultiplication(Of ModInt).Multiply
            Return Me * rhs
        End Function

        Public Function Power(pow_ As Integer) As ModInt Implements IPower(Of ModInt).Power
            Return Pow(Me, pow_)
        End Function

        Public Function One() As ModInt Implements IOne(Of ModInt).One
            Return New ModInt(1, Modulo)
        End Function

        Public Overrides Function ToString() As String
            Return String.Format("ModInt({0}, {1})", Value, Modulo)
        End Function

        Public Shared Operator +(lhs As ModInt, rhs As ModInt) As ModInt
            If lhs.Modulo <> rhs.Modulo Then
                Throw New ArgumentException("Cannot add rings with different modulus")
            End If
            Return New ModInt((lhs.Value + rhs.Value) Mod lhs.Modulo, lhs.Modulo)
        End Operator

        Public Shared Operator *(lhs As ModInt, rhs As ModInt) As ModInt
            If lhs.Modulo <> rhs.Modulo Then
                Throw New ArgumentException("Cannot multiply rings with different modulus")
            End If
            Return New ModInt((lhs.Value * rhs.Value) Mod lhs.Modulo, lhs.Modulo)
        End Operator

        Public Shared Function Pow(self As ModInt, p As Integer) As ModInt
            If p < 0 Then
                Throw New ArgumentException("p must be zero or greater")
            End If

            Dim pp = p
            Dim pwr = self.One()
            While pp > 0
                pp -= 1
                pwr *= self
            End While
            Return pwr
        End Function
    End Class

    Function F(Of T As {IAddition(Of T), IMultiplication(Of T), IPower(Of T), IOne(Of T)})(x As T) As T
        Return x.Power(100).Add(x).Add(x.One)
    End Function

    Sub Main()
        Dim x As New ModInt(10, 13)
        Dim y = F(x)
        Console.WriteLine("x ^ 100 + x + 1 for x = {0} is {1}", x, y)
    End Sub

End Module
Output:
x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(1, 13)

Wren

// Semi-abstract though we can define a 'pow' method in terms of the other operations.
class Ring {
    +(other) {}
    *(other) {}
    one      {}

    pow(p) {
        if (p.type != Num || !p.isInteger || p < 0) {
            Fiber.abort("Argument must be non-negative integer.")
        }
        var pwr = one
        while (p > 0) {
            pwr = pwr * this
            p = p - 1
        }
        return pwr
    }
}

class ModInt is Ring {
    construct new(value, modulo) {
        _value = value
        _modulo = modulo
    }

    value  { _value }
    modulo { _modulo }

    +(other) {
        if (other.type != ModInt || _modulo != other.modulo) {
            Fiber.abort("Argument must be a ModInt with the same modulus.")
        }
        return ModInt.new((_value + other.value) % _modulo, _modulo)
    }

    *(other) {
        if (other.type != ModInt || _modulo != other.modulo) {
            Fiber.abort("Argument must be a ModInt with the same modulus.")
        }
        return ModInt.new((_value * other.value) % _modulo, _modulo)
    }

    one { ModInt.new(1, _modulo) }

    toString { "Modint(%(_value), %(_modulo))" }
}

var f = Fn.new { |x|
    if (!(x is Ring)) Fiber.abort("Argument must be a Ring.")
    return x.pow(100) + x + x.one
}

var x = ModInt.new(10, 13)
System.print("x^100 + x + 1 for x = %(x) is %(f.call(x))")
Output:
x^100 + x + 1 for x = Modint(10, 13) is Modint(1, 13)

zkl

Doing just enough to perform the task:

class MC{
   fcn init(n,mod){ var N=n,M=mod; }
   fcn toString   { String(N.divr(M)[1],"M",M) }
   fcn pow(p)     { self( N.pow(p).divr(M)[1], M ) }
   fcn __opAdd(mc){ 
      if(mc.isType(Int)) z:=N+mc; else z:=N*M + mc.N*mc.M;
      self(z.divr(M)[1],M) 
   }
}

Using GNU GMP lib to do the big math (to avoid writing a powmod function):

var BN=Import("zklBigNum");
fcn f(n){ n.pow(100) + n + 1 }
f(1).println(" <-- 1^100 + 1 + 1");
n:=MC(BN(10),13);
(n+3).println(" <-- 10M13 + 3");
f(n).println(" <-- 10M13^100 + 10M13 + 1");
Output:
3 <-- 1^100 + 1 + 1
0M13 <-- 10M13 + 3
1M13 <-- 10M13^100 + 10M13 + 1