Modular arithmetic: Difference between revisions
no edit summary
No edit summary |
|||
| (4 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 2,739 ⟶ 2,996:
=={{header|Wren}}==
<syntaxhighlight lang="
class Ring {
+(other) {}
| |||