Modular arithmetic: Difference between revisions
no edit summary
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
No edit summary |
||
| (23 intermediate revisions by 4 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.
Line 80 ⟶ 82:
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}}==
Line 308 ⟶ 622:
{{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}}==
Line 613 ⟶ 965:
</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}}==
Line 1,065 ⟶ 1,769:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<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}}==
Line 1,151 ⟶ 1,944:
{{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}}==
Line 1,433 ⟶ 2,405:
(formerly Perl 6)
<syntaxhighlight lang="raku" line>use FiniteField;
$*modulus = 13;
sub f(\x) { x**100 + x + 1};
say f(10);</syntaxhighlight>
{{out}}
<pre>1
=={{header|Red}}==
Line 1,592 ⟶ 2,546:
}</syntaxhighlight>
=={{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}}==
Line 1,974 ⟶ 2,996:
=={{header|Wren}}==
<syntaxhighlight lang="
class Ring {
+(other) {}
| |||