Modular Division (C Plus Plus)

From LiteratePrograms

Modular division is a division operation performed in modular arithmetic. Specifically, given two integers a and b and a modulo m, the result of the modular division of a by b is a number z such that:

For example:

since

Unlike the other three arithmetic operators, the result of a division may not always exist. For example: $1 / 2(mod 8)$ does not exist, since there is no integer z such that: .

A necessary and sufficient condition for the result to exist is that the GCD (greatest common divisor) of b and m divides a:

g c d (b, m) | a

In the above example, gcd(2,8) = 2, and 1 is not a multiple of 2, so the division is not defined.

Unlike the other three arithmetic operators, the result of a division is not always unique. For example:

but it is also true that:

since:

In general, if:

Then for each integer k:

Since for each such k:

The result of the division is unique modulu m/gcd(b,m).

The modular division may be calculated using the Extended Euclidean algorithm. The latter algorithm finds the GCD of two given numbers (in this case: b and m), and additionally calculates numbers x, y such that:

The result of the division can be calculated if and only if a is a multiple of gcd(b,m), i.e. there exists an integer q such that:

a = q * g c d (b, m)

In this case we can multiple the previous equation by q, and get:

b q x + m q y = q * g c d (b, m) = a

Therefore. by the definition of modulus:

so qx is the result of the division.

Source

First we copy the implementation from Extended Euclidean algorithm (C Plus Plus):

<<eea>>=
void eea (int a, int b,
        int& gcd, int& x, int& y) {
        x=0, y=1; 
        int u=1, v=0, m, n, q, r;
        gcd = b;
        while (a!=0) {
                q=gcd/a; r=gcd%a;
                m=x-u*q; n=y-v*q;
                gcd=a; a=r; x=u; y=v; u=m; v=n;
        }
}

And here is the implementation of modular division:

<<divide>>=
eea
#include <assert.h>
int divide (int A, int B, int m) {
	assert (0 <= A && A<m);
	assert (0 <= B && B<m);
	int gcd, x, y;
	eea (B, m, gcd, x, y);  // x B + y p = gcd(B,p)
	if (A%gcd == 0) {        
		int q = A / gcd;       // x q B + y q p = q gcd = A
		return ((x + m)*q) % (m/gcd);   // Return the smallest result possible
	} else {
		throw "no quotient";
	}
}

Tests

The following program calculates all division results for the moduli 6, 7, 8, 9 and 10.

<<divide.cpp>>=
#include <iostream>
using namespace std;
divide
void assertDivide(int X, int Y, int m, int expected) {
        int a = divide(X, Y, m);
        if (a!=expected) {
                cerr << "ERROR: " << X << " / " << Y << " [mod " << m << "] == " << expected << " but got " << a << endl;
        } else {
                cout << X << " / " << Y << " [mod " << m << "] == " << expected << endl;
        }
}
void assertCycle (int Y, int m) {
        for (int Z=1, X=Y; Z<m && X!=0; Z+=1, X=(X+Y)%m) {
                assertDivide(X,Y,m,Z);
        }
}
void assertCycles(int m) {
        for (int Y=1; Y<m; ++Y) {
                assertCycle(Y, m);
        }
}
int main() {
        assertCycles(6);
        assertCycles(7);
        assertCycles(8);
        assertCycles(9);
        assertCycles(10);
        return 0;
}

Results

1 / 1 [mod 6] == 1
2 / 1 [mod 6] == 2
3 / 1 [mod 6] == 3
4 / 1 [mod 6] == 4
5 / 1 [mod 6] == 5
2 / 2 [mod 6] == 1
4 / 2 [mod 6] == 2
3 / 3 [mod 6] == 1
4 / 4 [mod 6] == 1
2 / 4 [mod 6] == 2
5 / 5 [mod 6] == 1
4 / 5 [mod 6] == 2
3 / 5 [mod 6] == 3
2 / 5 [mod 6] == 4
1 / 5 [mod 6] == 5
1 / 1 [mod 7] == 1
2 / 1 [mod 7] == 2
3 / 1 [mod 7] == 3
4 / 1 [mod 7] == 4
5 / 1 [mod 7] == 5
6 / 1 [mod 7] == 6
2 / 2 [mod 7] == 1
4 / 2 [mod 7] == 2
6 / 2 [mod 7] == 3
1 / 2 [mod 7] == 4
3 / 2 [mod 7] == 5
5 / 2 [mod 7] == 6
3 / 3 [mod 7] == 1
6 / 3 [mod 7] == 2
2 / 3 [mod 7] == 3
5 / 3 [mod 7] == 4
1 / 3 [mod 7] == 5
4 / 3 [mod 7] == 6
4 / 4 [mod 7] == 1
1 / 4 [mod 7] == 2
5 / 4 [mod 7] == 3
2 / 4 [mod 7] == 4
6 / 4 [mod 7] == 5
3 / 4 [mod 7] == 6
5 / 5 [mod 7] == 1
3 / 5 [mod 7] == 2
1 / 5 [mod 7] == 3
6 / 5 [mod 7] == 4
4 / 5 [mod 7] == 5
2 / 5 [mod 7] == 6
6 / 6 [mod 7] == 1
5 / 6 [mod 7] == 2
4 / 6 [mod 7] == 3
3 / 6 [mod 7] == 4
2 / 6 [mod 7] == 5
1 / 6 [mod 7] == 6
1 / 1 [mod 8] == 1
2 / 1 [mod 8] == 2
3 / 1 [mod 8] == 3
4 / 1 [mod 8] == 4
5 / 1 [mod 8] == 5
6 / 1 [mod 8] == 6
7 / 1 [mod 8] == 7
2 / 2 [mod 8] == 1
4 / 2 [mod 8] == 2
6 / 2 [mod 8] == 3
3 / 3 [mod 8] == 1
6 / 3 [mod 8] == 2
1 / 3 [mod 8] == 3
4 / 3 [mod 8] == 4
7 / 3 [mod 8] == 5
2 / 3 [mod 8] == 6
5 / 3 [mod 8] == 7
4 / 4 [mod 8] == 1
5 / 5 [mod 8] == 1
2 / 5 [mod 8] == 2
7 / 5 [mod 8] == 3
4 / 5 [mod 8] == 4
1 / 5 [mod 8] == 5
6 / 5 [mod 8] == 6
3 / 5 [mod 8] == 7
6 / 6 [mod 8] == 1
4 / 6 [mod 8] == 2
2 / 6 [mod 8] == 3
7 / 7 [mod 8] == 1
6 / 7 [mod 8] == 2
5 / 7 [mod 8] == 3
4 / 7 [mod 8] == 4
3 / 7 [mod 8] == 5
2 / 7 [mod 8] == 6
1 / 7 [mod 8] == 7
1 / 1 [mod 9] == 1
2 / 1 [mod 9] == 2
3 / 1 [mod 9] == 3
4 / 1 [mod 9] == 4
5 / 1 [mod 9] == 5
6 / 1 [mod 9] == 6
7 / 1 [mod 9] == 7
8 / 1 [mod 9] == 8
2 / 2 [mod 9] == 1
4 / 2 [mod 9] == 2
6 / 2 [mod 9] == 3
8 / 2 [mod 9] == 4
1 / 2 [mod 9] == 5
3 / 2 [mod 9] == 6
5 / 2 [mod 9] == 7
7 / 2 [mod 9] == 8
3 / 3 [mod 9] == 1
6 / 3 [mod 9] == 2
4 / 4 [mod 9] == 1
8 / 4 [mod 9] == 2
3 / 4 [mod 9] == 3
7 / 4 [mod 9] == 4
2 / 4 [mod 9] == 5
6 / 4 [mod 9] == 6
1 / 4 [mod 9] == 7
5 / 4 [mod 9] == 8
5 / 5 [mod 9] == 1
1 / 5 [mod 9] == 2
6 / 5 [mod 9] == 3
2 / 5 [mod 9] == 4
7 / 5 [mod 9] == 5
3 / 5 [mod 9] == 6
8 / 5 [mod 9] == 7
4 / 5 [mod 9] == 8
6 / 6 [mod 9] == 1
3 / 6 [mod 9] == 2
7 / 7 [mod 9] == 1
5 / 7 [mod 9] == 2
3 / 7 [mod 9] == 3
1 / 7 [mod 9] == 4
8 / 7 [mod 9] == 5
6 / 7 [mod 9] == 6
4 / 7 [mod 9] == 7
2 / 7 [mod 9] == 8
8 / 8 [mod 9] == 1
7 / 8 [mod 9] == 2
6 / 8 [mod 9] == 3
5 / 8 [mod 9] == 4
4 / 8 [mod 9] == 5
3 / 8 [mod 9] == 6
2 / 8 [mod 9] == 7
1 / 8 [mod 9] == 8
1 / 1 [mod 10] == 1
2 / 1 [mod 10] == 2
3 / 1 [mod 10] == 3
4 / 1 [mod 10] == 4
5 / 1 [mod 10] == 5
6 / 1 [mod 10] == 6
7 / 1 [mod 10] == 7
8 / 1 [mod 10] == 8
9 / 1 [mod 10] == 9
2 / 2 [mod 10] == 1
4 / 2 [mod 10] == 2
6 / 2 [mod 10] == 3
8 / 2 [mod 10] == 4
3 / 3 [mod 10] == 1
6 / 3 [mod 10] == 2
9 / 3 [mod 10] == 3
2 / 3 [mod 10] == 4
5 / 3 [mod 10] == 5
8 / 3 [mod 10] == 6
1 / 3 [mod 10] == 7
4 / 3 [mod 10] == 8
7 / 3 [mod 10] == 9
4 / 4 [mod 10] == 1
8 / 4 [mod 10] == 2
2 / 4 [mod 10] == 3
6 / 4 [mod 10] == 4
5 / 5 [mod 10] == 1
6 / 6 [mod 10] == 1
2 / 6 [mod 10] == 2
8 / 6 [mod 10] == 3
4 / 6 [mod 10] == 4
7 / 7 [mod 10] == 1
4 / 7 [mod 10] == 2
1 / 7 [mod 10] == 3
8 / 7 [mod 10] == 4
5 / 7 [mod 10] == 5
2 / 7 [mod 10] == 6
9 / 7 [mod 10] == 7
6 / 7 [mod 10] == 8
3 / 7 [mod 10] == 9
8 / 8 [mod 10] == 1
6 / 8 [mod 10] == 2
4 / 8 [mod 10] == 3
2 / 8 [mod 10] == 4
9 / 9 [mod 10] == 1
8 / 9 [mod 10] == 2
7 / 9 [mod 10] == 3
6 / 9 [mod 10] == 4
5 / 9 [mod 10] == 5
4 / 9 [mod 10] == 6
3 / 9 [mod 10] == 7
2 / 9 [mod 10] == 8
1 / 9 [mod 10] == 9

Download code

Retrieved from "http://literateprograms.org/Modular_Division_%28C_Plus_Plus%29"

Categories: Modular Division | Programming language:C Plus Plus | Environment:Portable

Modular Division (C Plus Plus)

From LiteratePrograms

Source

Tests

Results

Views

Navigation