Modular arithmetic: Difference between revisions
m (fixing wikipedia link) |
m (rephrasing) |
||
Line 5: | Line 5: | ||
<math>a = b + k p</math> |
<math>a = b + k p</math> |
||
p is called the congruence ''modulus''. The corresponding set of integers is called the <math>\frac{\mathbf{Z}}{p\mathbf{Z}}</math> [[wp:Ring (mathematics)|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. |
p is called the congruence ''modulus''. The corresponding set of integers is called the <math>\frac{\mathbf{Z}}{p\mathbf{Z}}</math> [[wp:Ring (mathematics)|ring]], and each element of this ring is uniquely represented by the remainder of its [[wp:euclidean division|euclidean division]] by p. 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. |
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. |
Revision as of 07:10, 21 February 2013
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 congruence. This means that two numbers a and b are considered congruent whenever there exists an integer k such that:
p is called the congruence modulus. The corresponding set of integers is called the ring, and each element of this ring is uniquely represented by the remainder of its euclidean division by p. 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:
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.
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 a Panda module called Modular which works basically as Perl 5's Math::ModInt.
<lang Perl 6>use Modular; sub f(\x) { x**100 + x + 1}; say f( 10 Mod 13 )</lang>
- Output:
1 「mod 13」