8.1 OPERATIONS IN Zm

Given a natural number m > 1, the set Zm = {0, 1, … , m − 1} is a ring whose operations are defined modulo m (Chapter 2):

image

8.1.1 Addition

Given two natural numbers x and y belonging to the interval 0 ≤ x, y < m, compute z = (x + y) mod m. Taking into account that

image

z must be equal to either x + y or x + ym. The corresponding algorithm is the following.

Algorithm 8.1 Modulo m Addition

z1:=x+y; z2:=z1 − m;
if z2>=0 then z:=z2; else z:=z1; end if;

Assume now that Bn−1 < mBn and that x and y are n-digit base-B numbers. Consider three cases:

image

So Algorithm 8.1 can be substituted by the following one where all operands have n digits.

Algorithm 8.2 Base B Modulo m Addition

z1:=(x+y) mod B**n; c1:=(x+y)/B**n;
z2:=(z1+B**n - m) mod B**n; c2:=(z1+B**n - m)/B**n;
if c1=0 and c2=0 then z:=z1; else z:=z2; end if;

Example 8.1 Assume that B = 10, n = 3, m = 750, so that Bnm = 250:

image

8.1.2 Subtraction

Given two natural numbers x and y belonging to the interval 0 ≤ x, y < m, compute z = (x − y) mod m. Taking into account that

z must be equal to either x − y or x − y + m ...

Get Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.