Modular arithmetic

From Rosetta Code
(Redirected from Modular Arithmetic)
Jump to: navigation, search
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 is called the \frac{\mathbf{Z}}{p\mathbf{Z}} ring. Addition and multiplication on this ring have the same algebraic structure, 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

[edit] PARI/GP

This feature exists natively in GP:

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

[edit] 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)

[edit] 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」

[edit] 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].

[edit] 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

[edit] 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>
 

[edit] 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]
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox