Modular arithmetic

(Redirected from Modular Arithmetic)
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 p called the congruence modulus, two numbers a and b are said to be congruent modulo p whenever there exists an integer k such that:

$a = b + k\,p$

The corresponding set of equivalence classes forms a ring denoted $\frac{\Z}{p\Z}$. 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:

f(x) = x100 + x + 1

You will use 13 as the congruence modulus and you will compute f(10).

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

Contents

-- 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 -> ℤ/13f x = x^100 + x + 1 main :: IO ()main = print (f 10)
Output:
./modarith
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) Perl 6 There is a Panda module called Modular which works basically as Perl 5's Math::ModInt. use Modular;sub f(\x) { x**100 + x + 1};say f( 10 Mod 13 ) 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 ). :- 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 operatorimport functools @functools.total_orderingclass 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) 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 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 # Demox, y = Modulo.new(10), Modulo.new(20) p x > y # truep x == y # falsep [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 # 9p y + 2 ##<Modulo:0x00000000ad1d30 @n=9, @m=13> p x**100 + x +1 ##<Modulo:0x00000000ad1998 @n=1, @m=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.6package require pt::pgen ###### A simple expression parser for a subset of Tcl's expression language### # Define the grammar of expressions that we want to handleset 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 classcatch [pt::pgen peg $grammar snit -class Calculator -name Grammar] # An engine that compiles an expression into Tcl codeoo::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 arithmeticoo::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 togetherset comp [CompileAST new [ModEval create mod13 13]] Finally, demonstrating… set compiled [$comp compile {$x**100 +$x + 1}]set x 10puts "[eval $compiled] =$compiled"
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:

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