How to resolve the algorithm Modular arithmetic step by step in the D programming language
How to resolve the algorithm Modular arithmetic step by step in the D programming language
Table of Contents
Problem Statement
Modular arithmetic is a form of arithmetic (a calculation technique involving the concepts of addition and multiplication) which is done on numbers with a defined equivalence relation called congruence.
For any positive integer
p
{\displaystyle p}
called the congruence modulus, two numbers
a
{\displaystyle a}
and
b
{\displaystyle b}
are said to be congruent modulo p whenever there exists an integer
k
{\displaystyle k}
such that: The corresponding set of equivalence classes forms a ring denoted
Z
p
Z
{\displaystyle {\frac {\mathbb {Z} }{p\mathbb {Z} }}}
. When p is a prime number, this ring becomes a field denoted
F
p
{\displaystyle \mathbb {F} _{p}}
, but you won't have to implement the multiplicative inverse for this task.
Addition and multiplication on this ring have the same algebraic structure as in usual arithmetic, so that a function such as a polynomial expression could receive a ring element as argument and give a consistent result.
The purpose of this task is to show, if your programming language allows it,
how to redefine operators so that they can be used transparently on modular integers.
You can do it either by using a dedicated library, or by implementing your own class.
You will use the following function for demonstration:
You will use
13
{\displaystyle 13}
as the congruence modulus and you will compute
f ( 10 )
{\displaystyle f(10)}
. It is important that the function
f
{\displaystyle f}
is agnostic about whether or not its argument is modular; it should behave the same way with normal and modular integers.
In other words, the function is an algebraic expression that could be used with any ring, not just integers.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Modular arithmetic step by step in the D programming language
Source code in the d programming language
import std.stdio;
version(unittest) {
void assertEquals(T)(T actual, T expected) {
import core.exception;
import std.conv;
if (actual != expected) {
throw new AssertError("Actual [" ~ to!string(actual) ~ "]; Expected [" ~ to!string(expected) ~ "]");
}
}
}
void main() {
auto input = ModularInteger(10,13);
auto output = f(input);
writeln("f(", input, ") = ", output);
}
V f(V)(const V x) {
return x^^100 + x + 1;
}
/// Integer tests on f
unittest {
assertEquals(f(1), 3);
assertEquals(f(0), 1);
}
/// Floating tests on f
unittest {
assertEquals(f(1.0), 3.0);
assertEquals(f(0.0), 1.0);
}
struct ModularInteger {
private:
int value;
int modulus;
public:
this(int value, int modulus) {
this.modulus = modulus;
this.value = value % modulus;
}
ModularInteger opBinary(string op : "+")(ModularInteger rhs) const in {
assert(this.modulus == rhs.modulus);
} body {
return ModularInteger((this.value + rhs.value) % this.modulus, this.modulus);
}
ModularInteger opBinary(string op : "+")(int rhs) const {
return ModularInteger((this.value + rhs) % this.modulus, this.modulus);
}
ModularInteger opBinary(string op : "*")(ModularInteger rhs) const in {
assert(this.modulus == rhs.modulus);
assert(this.value < this.modulus);
assert(rhs.value < this.modulus);
} body {
return ModularInteger((this.value * rhs.value) % this.modulus, this.modulus);
}
ModularInteger opBinary(string op : "^^")(int pow) const in {
assert(pow >= 0);
} body {
auto base = ModularInteger(1, this.modulus);
while (pow-- > 0) {
base = base * this;
}
return base;
}
string toString() {
import std.format;
return format("ModularInteger(%s, %s)", value, modulus);
}
}
/// Addition with same type of int
unittest {
auto a = ModularInteger(2,5);
auto b = ModularInteger(3,5);
assertEquals(a+b, ModularInteger(0,5));
}
/// Addition with differnt int types
unittest {
auto a = ModularInteger(2,5);
assertEquals(a+0, a);
assertEquals(a+1, ModularInteger(3,5));
}
/// Muliplication
unittest {
auto a = ModularInteger(2,5);
auto b = ModularInteger(3,5);
assertEquals(a*b, ModularInteger(1,5));
}
/// Power
unittest {
const a = ModularInteger(3,13);
assertEquals(a^^2, ModularInteger(9,13));
assertEquals(a^^3, ModularInteger(1,13));
const b = ModularInteger(10,13);
assertEquals(b^^1, ModularInteger(10,13));
assertEquals(b^^2, ModularInteger(9,13));
assertEquals(b^^3, ModularInteger(12,13));
assertEquals(b^^4, ModularInteger(3,13));
assertEquals(b^^5, ModularInteger(4,13));
assertEquals(b^^6, ModularInteger(1,13));
assertEquals(b^^7, ModularInteger(10,13));
assertEquals(b^^8, ModularInteger(9,13));
assertEquals(b^^10, ModularInteger(3,13));
assertEquals(b^^20, ModularInteger(9,13));
assertEquals(b^^30, ModularInteger(1,13));
assertEquals(b^^50, ModularInteger(9,13));
assertEquals(b^^75, ModularInteger(12,13));
assertEquals(b^^90, ModularInteger(1,13));
assertEquals(b^^95, ModularInteger(4,13));
assertEquals(b^^97, ModularInteger(10,13));
assertEquals(b^^98, ModularInteger(9,13));
assertEquals(b^^99, ModularInteger(12,13));
assertEquals(b^^100, ModularInteger(3,13));
}
You may also check:How to resolve the algorithm Rate counter step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Rosetta Code/Rank languages by popularity step by step in the Bracmat programming language
You may also check:How to resolve the algorithm Variable-length quantity step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Perfect numbers step by step in the MAD programming language
You may also check:How to resolve the algorithm Closures/Value capture step by step in the J programming language