Modular arithmetic: Difference between revisions
no edit summary
(Swift: add missing operator definition) |
No edit summary |
||
(37 intermediate revisions by 9 users not shown) | |||
Line 6:
:<math>a = b + k\,p</math>
The corresponding set of [[wp:equivalence class|equivalence class]]es forms a [[wp:ring (mathematics)|ring]] denoted <math>\frac{\Z}{p\Z}</math>. When p is a prime number, this ring becomes a [[wp:field (mathematics)|field]] denoted <math>\mathbb{F}_p</math>, but you won't have to implement the [[wp:multiplicative inverse|multiplicative inverse]] for this task.
Addition and multiplication on this ring have the same algebraic structure as in usual
The purpose of this task is to show, if your programming language allows it,
Line 21:
In other words, the function is an algebraic expression that could be used with any ring, not just integers.
<br><br>
;Related tasks:
[[Modular exponentiation]]
<br><br>
=={{header|Ada}}==
Ada has modular types.
<
procedure Modular_Demo is
Line 47 ⟶ 49:
Put (F_10); Put (" mod "); Put (Modul_13'Modulus'Image);
New_Line;
end Modular_Demo;</
{{out}}
Line 54 ⟶ 56:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
PR precision 200 PR
Line 75 ⟶ 77:
ESAC;
print( ( whole( f( MODULARINT( 10, 13 ) ), 0 ), newline ) )</
{{out}}
<pre>
1
</pre>
=={{header|ATS}}==
The following program uses the <code>unsigned __int128</code> 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 [https://sourceforge.net/p/chemoelectric/ats2-xprelude/ ats2-xprelude] package. If the denominators are one, then such numbers are integers. The macro <code>g(x)</code> defined near the end of the program should work with those numbers.)
<syntaxhighlight lang="ATS">
(* 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
(*------------------------------------------------------------------*)
</syntaxhighlight>
{{out}}
<pre>$ patscc -std=gnu2x -g -O2 modular_arithmetic_task.dats && ./a.out
1
1
10000000000000002101697803323328251387822715387464188032188166609887360023982790799717755191065313280.000000</pre>
=={{header|C}}==
{{trans|C++}}
<
struct ModularArithmetic {
Line 134 ⟶ 448:
return 0;
}</
{{out}}
<pre>f(ModularInteger(10, 13)) = ModularInteger(1, 13)</pre>
Line 140 ⟶ 454:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
namespace ModularArithmetic {
Line 225 ⟶ 539:
}
}
}</
{{out}}
<pre>x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(1, 13)</pre>
Line 231 ⟶ 545:
=={{header|C++}}==
{{trans|D}}
<
#include <ostream>
Line 305 ⟶ 619:
return 0;
}</
{{out}}
<pre>f(ModularInteger(10, 13)) = ModularInteger(1, 13)</pre>
=={{header|Common Lisp}}==
{{trans|Scheme}}
In Scheme all procedures are anonymous, and names such as <code>+</code> and <code>expt</code> 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.)
<syntaxhighlight lang="lisp">
(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))
</syntaxhighlight>
{{out}}
<pre>$ sbcl --script modular_arithmetic_task.lisp
No modulus: 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13: 1
</pre>
=={{header|D}}==
<
version(unittest) {
Line 436 ⟶ 788:
assertEquals(b^^99, ModularInteger(12,13));
assertEquals(b^^100, ModularInteger(3,13));
}</
{{out}}
<pre>
Line 457 ⟶ 809:
Also note that since <code>^</code> is not a generic word, we employ the strategy of renaming it to <code>**</code> inside our vocabulary and defining a new word named <code>^</code> 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.
<
parser prettyprint prettyprint.custom sequences ;
IN: rosetta-code.modular-arithmetic
Line 544 ⟶ 896:
} 2show ;
MAIN: modular-arithmetic-demo</
{{out}}
<pre>
Line 557 ⟶ 909:
MI{ 3 7 } 50 ^ = MI{ 2 7 }
</pre>
=={{header|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.
<pre>
\ 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
</pre>
=={{header|Fortran}}==
{{works with|GCC|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'''
<syntaxhighlight lang="fortran">
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
</syntaxhighlight>
{{out}}
<pre>$ gfortran -O2 -fbounds-check -Wall -Wextra -g modular_arithmetic_task.F90 && ./a.out
modulus 13: 1
floating point: .10000000000000000159028911097599180468360808563945+101
</pre>
===Program 2===
{{works with|GCC|12.2.1}}
This program uses unlimited runtime polymorphism.
<syntaxhighlight lang="fortran">
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
</syntaxhighlight>
{{out}}
<pre>$ 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)
</pre>
=={{header|FreeBASIC}}==
{{trans|Visual Basic .NET}}
<syntaxhighlight lang="vbnet">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</syntaxhighlight>
{{out}}
<pre>x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(1, 13)</pre>
=={{header|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.
<
import "fmt"
Line 622 ⟶ 1,382:
func main() {
fmt.Println(f(modRing(13), uint(10)))
}</
{{out}}
<pre>
Line 629 ⟶ 1,389:
=={{header|Haskell}}==
<
-- 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.)
Line 642 ⟶ 1,402:
main :: IO ()
main = print (f 10)</
{{out}}
Line 649 ⟶ 1,409:
1
</pre>
=={{header|J}}==
J does not allow "operator redefinition", but J's operators are capable of operating consistently on values which represent modular integers:
<syntaxhighlight lang="j"> f=: (+./1 1,:_101{.1x)&p.</syntaxhighlight>
Task example:
<syntaxhighlight lang="j"> 13|f 10
1</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|Java|8}}
<
private interface Ring<T> {
Ring<T> plus(Ring<T> rhs);
Line 737 ⟶ 1,508:
System.out.flush();
}
}</
{{out}}
<pre>x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(1, 13)</pre>
=={{header|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'''
<syntaxhighlight lang="jq">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);
</syntaxhighlight>
'''Modular Arithmetic'''
<syntaxhighlight lang="jq"># "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)»";</syntaxhighlight>
''' Ring Functions'''
<syntaxhighlight lang="jq">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);</syntaxhighlight>
'''Evaluating ring::f'''
<syntaxhighlight lang="jq">def main:
(ring::f(1) | "f(\(1)) => \(.)"),
(modint::make(10;13)
| ring::f(.) as $out
| "f(\(ring::pp)) => \($out|ring::pp)");</syntaxhighlight>
{{out}}
<pre>
f(1) => 3
f(«10 % 13») => «1 % 13»
</pre>
=={{header|Julia}}==
Line 745 ⟶ 1,623:
Implements the <tt>Modulo</tt> struct and basic operations.
<
val::T
mod::T
Line 772 ⟶ 1,650:
f(x) = x ^ 100 + x + 1
@show f(modulo(10, 13))</
{{out}}
Line 778 ⟶ 1,656:
=={{header|Kotlin}}==
<
interface Ring<T> {
Line 818 ⟶ 1,696:
val y = f(x)
println("x ^ 100 + x + 1 for x == ModInt(10, 13) is $y")
}</
{{out}}
Line 826 ⟶ 1,704:
=={{header|Lua}}==
<
local v = value % modulo
local tbl = {value=v, modulo=modulo}
Line 886 ⟶ 1,764:
local x = make(10, 13)
local y = func(x)
print("x ^ 100 + x + 1 for "..x.." is "..y)</
{{out}}
<pre>x ^ 100 + x + 1 for ModInt(10, 13) is ModInt(1, 13)</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
For versions prior to 13.3, the best way to do it is probably to use the finite fields package.
<syntaxhighlight lang="mathematica"><< FiniteFields`
x^100 + x + 1 /. x -> GF[13]@{10}</syntaxhighlight>
{{out}}
{1}<sub>13</sub>
Version 13.3 has a "complete, consistent coverage of all finite fields":
<syntaxhighlight lang="mathematica">
OutputForm[
x^100 + x + 1 /. x -> FiniteField[13][10]
]
</syntaxhighlight>
We have to show the `OutputForm` though, because the `StandardForm` is not easy to render here.
{{out}}
<pre>FiniteFieldElement[<1,13,1,+>]</pre>
=={{header|Mercury}}==
{{works with|Mercury|22.01.1}}
Numbers have to be converted to <code>ordinary(Number)</code> or <code>modular(Number, Modulus)</code> before they are plugged into <code>f</code>. 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 <code>f</code> could be invoked directly on the <code>integer</code> type.)
<syntaxhighlight lang="mercury">
%% -*- 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.
</syntaxhighlight>
{{out}}
<pre>$ 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
</pre>
=={{header|Nim}}==
Modular integers are represented as distinct integers with a modulus N managed by the compiler.
<
const Subscripts: array['0'..'9', string] = ["₀", "₁", "₂", "₃", "₄", "₅", "₆", "₇", "₈", "₉"]
Line 966 ⟶ 1,940:
var x = initModInt[13](10)
echo &"f({x}) = {x}^100 + {x} + 1 = {f(x)}."</
{{out}}
<pre>f(10₁₃) = 10₁₃^100 + 10₁₃ + 1 = 1₁₃.</pre>
=={{header|ObjectIcon}}==
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>$ oiscript modular_arithmetic_task_OI.icn
no modulus: 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13: 1
</pre>
=={{header|Owl Lisp}}==
{{trans|Scheme}}
<syntaxhighlight lang="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)
</syntaxhighlight>
{{out}}
<pre>$ ol modular_arithmetic_task_Owl.scm
No modulus: 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13: 1
</pre>
=={{header|PARI/GP}}==
This feature exists natively in GP:
<
=={{header|Perl}}==
There is a CPAN module called Math::ModInt which does the job.
<
sub f { my $x = shift; $x**100 + $x + 1 };
print f mod(10, 13);</
{{out}}
<pre>mod(1, 13)</pre>
Line 987 ⟶ 2,140:
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.
<!--<
<span style="color: #008080;">type</span> <span style="color: #000000;">mi</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">2</span> <span style="color: #008080;">and</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">and</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
Line 1,042 ⟶ 2,195:
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
Line 1,052 ⟶ 2,205:
=={{header|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 ).
<
congruence(Congruence, In, Fun, Out) :-
Line 1,064 ⟶ 2,217:
fun_2(L, [R]) :-
sum_list(L, R).
</syntaxhighlight>
{{out}}
<pre> ?- congruence(13, [10], fun_1, R).
Line 1,083 ⟶ 2,236:
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 functools
Line 1,171 ⟶ 2,324:
print(f(Mod(10,13)))
# Output: Mod(1, 13)</
=={{header|Quackery}}==
Line 1,183 ⟶ 2,336:
The third part fulfils the requirements of this task.
<
[ this ] is modular ( --> [ )
Line 1,228 ⟶ 2,381:
10 f echo cr
10 modularise f echo
modulus release cr</
'''Output:'''
<pre>10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
Line 1,237 ⟶ 2,390:
=={{header|Racket}}==
<
(require racket/require
;; grab all "mod*" names, but get them without the "mod", so
Line 1,247 ⟶ 2,400:
(define (f x) (+ (expt x 100) x 1))
(with-modulus 13 (f 10))
;; => 1</
=={{header|Raku}}==
(formerly Perl 6)
We'll use the [https://raku.land/github:grondilu/finite-fields-raku FiniteFields] repo.
<syntaxhighlight lang="raku" line>use FiniteField;
$*modulus = 13;
sub f(\x) { x**100 + x + 1};
say f(10);</syntaxhighlight>
{{out}}
<pre>1
=={{header|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.
<
; defining the modular integer class, and a constructor
Line 1,289 ⟶ 2,448:
print ["f definition is:" mold :f]
print ["f((integer) 10) is:" f 10]
print ["f((modular) 10) is: (modular)" f m 10]</
{{out}}
<pre>f definition is: func [x][x ** 100 + x + 1]
Line 1,296 ⟶ 2,455:
=={{header|Ruby}}==
<
class Modulo
Line 1,334 ⟶ 2,493:
p x**100 + x +1 ##<Modulo:0x00000000ad1998 @n=1, @m=13>
</syntaxhighlight>
=={{header|Scala}}==
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/jOSxPQu/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/ZSeJw1lBRZiHenoQ6coDdA Scastie (remote JVM)].
<
private val x = new ModInt(10, 13)
private val y = f(x)
Line 1,386 ⟶ 2,545:
println("x ^ 100 + x + 1 for x = ModInt(10, 13) is " + y)
}</
=={{header|Scheme}}==
{{works with|Gauche Scheme|0.9.12}}
{{works with|Chibi Scheme|0.10.0}}
{{works with|CHICKEN Scheme|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 <code>floor-remainder</code> instead of <code>truncate-remainder</code>. The latter would function incorrectly if there were negative numbers.
<syntaxhighlight lang="scheme">
(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))
</syntaxhighlight>
{{out}}
<pre>$ gosh modular_arithmetic_task.scm
No modulus: 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
modulus 13: 1
</pre>
=={{header|Sidef}}==
{{trans|Ruby}}
<
method init {
Line 1,406 ⟶ 2,633:
func f(x) { x**100 + x + 1 }
say f(Modulo(10, 13))</
{{out}}
<pre>1 「mod 13」</pre>
Line 1,414 ⟶ 2,641:
{{trans|Scala}}
<
higherThan: MultiplicationPrecedence
}
Line 1,473 ⟶ 2,700:
let y = f(x)
print("x ^ 100 + x + 1 for x = ModInt(10, 13) is \(y)")</
{{out}}
Line 1,485 ⟶ 2,712:
as is shown here.
{{tcllib|pt::pgen}}
<
package require pt::pgen
Line 1,557 ⟶ 2,784:
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.
<
oo::class create ModEval {
variable mod
Line 1,578 ⟶ 2,805:
# Put all the pieces together
set comp [CompileAST new [ModEval create mod13 13]]</
Finally, demonstrating…
<
set x 10
puts "[eval $compiled] = $compiled"</
{{out}}
<pre>
Line 1,589 ⟶ 2,816:
=={{header|VBA}}==
{{trans|Phix}}<
Private Function mi_one(ByVal a As Variant) As Variant
If IsArray(a) Then
Line 1,670 ⟶ 2,897:
test 10
test [{10,13}]
End Sub</
<pre>x^100 + x + 1 for x == 10 is 1E+100
x^100 + x + 1 for x == modint(10,13) is modint(1,13)</pre>
Line 1,676 ⟶ 2,903:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Interface IAddition(Of T)
Line 1,764 ⟶ 2,991:
End Sub
End Module</
{{out}}
<pre>x ^ 100 + x + 1 for x = ModInt(10, 13) is ModInt(1, 13)</pre>
=={{header|Wren}}==
<
class Ring {
+(other) {}
Line 1,822 ⟶ 3,049:
var x = ModInt.new(10, 13)
System.print("x^100 + x + 1 for x = %(x) is %(f.call(x))")</
{{out}}
Line 1,831 ⟶ 3,058:
=={{header|zkl}}==
Doing just enough to perform the task:
<
fcn init(n,mod){ var N=n,M=mod; }
fcn toString { String(N.divr(M)[1],"M",M) }
Line 1,839 ⟶ 3,066:
self(z.divr(M)[1],M)
}
}</
Using GNU GMP lib to do the big math (to avoid writing a powmod function):
<
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");</
{{out}}
<pre>
|