Modular arithmetic: Difference between revisions
no edit summary
No edit summary |
|||
| (16 intermediate revisions by 4 users not shown) | |||
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 83 ⟶ 85:
=={{header|ATS}}==
The following program uses the <code>unsigned __int128</code> type of GNU C
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">
Line 362 ⟶ 366:
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
Line 368 ⟶ 381:
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
Line 376 ⟶ 391:
{{out}}
<pre>$ patscc -std=gnu2x -g -O2 modular_arithmetic_task.dats && ./a.out
1
1
10000000000000002101697803323328251387822715387464188032188166609887360023982790799717755191065313280.000000</pre>
=={{header|C}}==
Line 605 ⟶ 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 910 ⟶ 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,362 ⟶ 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,448 ⟶ 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,878 ⟶ 2,553:
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">
Line 2,317 ⟶ 2,996:
=={{header|Wren}}==
<syntaxhighlight lang="
class Ring {
+(other) {}
| |||