Modular arithmetic: Difference between revisions
no edit summary
No edit summary |
|||
| (7 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 967 ⟶ 969:
{{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">
Line 1,072 ⟶ 1,076:
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,524 ⟶ 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}}==
Line 1,687 ⟶ 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 2,560 ⟶ 2,996:
=={{header|Wren}}==
<syntaxhighlight lang="
class Ring {
+(other) {}
| |||