Modular arithmetic: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added Java)
m (→‎{{header|Perl 6}}: fix markup)
Line 461: Line 461:


=={{header|Perl 6}}==
=={{header|Perl 6}}==
There is a Panda module called Modular which works basically as Perl 5's Math::ModInt.
There is an ecosystem module called Modular which works basically as Perl 5's Math::ModInt.
<lang Perl 6>use Modular;
<lang perl6>use Modular;
sub f(\x) { x**100 + x + 1};
sub f(\x) { x**100 + x + 1};
say f( 10 Mod 13 )</lang>
say f( 10 Mod 13 )</lang>

Revision as of 00:10, 19 April 2018

Modular arithmetic is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 . Addition and multiplication on this ring have the same algebraic structure as in usual arithmetics, 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.

ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.8.win32

<lang algol68># allow for large integers in Algol 68G # PR precision 200 PR

  1. modular integer type #

MODE MODULARINT = STRUCT( LONG LONG INT v, INT modulus );

  1. modular integer + and * operators #
  2. 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 );

  1. f(x) function - can be applied to either LONG LONG INT or MODULARINT values #
  2. 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 ) )</lang>

Output:
1

D

<lang 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));

}</lang>

Output:
f(ModularInteger(10, 13)) = ModularInteger(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. <lang go>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)))

}</lang>

Output:
1

Haskell

<lang 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)</lang>

Output:
./modarith 
1

Java

Translation of: Kotlin
Works with: Java version 8

<lang Java>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();
   }

}</lang>

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

Julia

Works with: Julia version 0.6

Implements the Modulo struct and basic operations. <lang julia>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))</lang>

Output:
f(modulo(10, 13)) = 11 (mod 13)

Kotlin

<lang scala>// 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")

}</lang>

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

PARI/GP

This feature exists natively in GP: <lang parigp>Mod(3,7)+Mod(4,7)</lang>

Perl

There is a CPAN module called Math::ModInt which does the job. <lang Perl>use Math::ModInt qw(mod); sub f { my $x = shift; $x**100 + $x + 1 }; print f mod(10, 13);</lang>

Output:
mod(1, 13)

Perl 6

There is an ecosystem module called Modular which works basically as Perl 5's Math::ModInt. <lang perl6>use Modular; sub f(\x) { x**100 + x + 1}; say f( 10 Mod 13 )</lang>

Output:
1 「mod 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 ). <lang Prolog>:- 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). </lang>

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.

<lang Python>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.
  1. Helper functions to build common operands based on a template.
  2. 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
  1. 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)))

  1. Output: Mod(1, 13)</lang>

Racket

<lang 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</lang>

Ruby

<lang 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

  1. 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> </lang>

Sidef

Translation of: Ruby

<lang 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))</lang>

Output:
1 「mod 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)

<lang tcl>package require Tcl 8.6 package require pt::pgen

      2. A simple expression parser for a subset of Tcl's expression language
  1. 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; }

  1. Instantiate the parser class

catch [pt::pgen peg $grammar snit -class Calculator -name Grammar]

  1. 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] 

   }

}</lang> 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. <lang tcl># 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 + - * / **

}

  1. Put all the pieces together

set comp [CompileAST new [ModEval create mod13 13]]</lang> Finally, demonstrating… <lang tcl>set compiled [$comp compile {$x**100 + $x + 1}] set x 10 puts "[eval $compiled] = $compiled"</lang>

Output:
1 = ::mod13 + [::mod13 + [::mod13 ** [::mod13 variable x] [::mod13 value 100]] [::mod13 variable x]] [::mod13 value 1]

zkl

Doing just enough to perform the task: <lang zkl>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) 
  }

}</lang> Using GNU GMP lib to do the big math (to avoid writing a powmod function): <lang zkl>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");</lang>

Output:
3 <-- 1^100 + 1 + 1
0M13 <-- 10M13 + 3
1M13 <-- 10M13^100 + 10M13 + 1
Retrieved from "https://rosettacode.org/wiki/Modular_arithmetic?oldid=226338"