Page 1 of 1

The use of the modulo (%) operator Rate Topic: -----

#1 karabasf  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 202
  • View blog
  • Posts: 417
  • Joined: 29-August 10

Posted 04 April 2012 - 01:27 AM

*
POPULAR

Although many got an explanation about the modulo operator, few really know what purposes it can serve. This tutorial will show some basic applications of the modulo operator, ranging from daily life "issues" till some (extremely simplified) data structures in JAVA.

Before we start, we need to know what exactly the modulo operator is. According to it's definition, it's given as:

Modulo operator (Note that '%' is the modulo operator in Java)
if r = x % y, then a non-negative q exist, such that
x = q*y + r

Now we know the definition of the modulo operator, let's consider some daily life applications, starting with:

Even numbers
We know that when a number is even, it doesn't have any decimals when it's divided by two. So,

0-1-2-3-4-5-6-7-8-9-10
//Divide by 2
0-0.5-1-1.5-2-2.5-3-3.5-4-4.5-5



It appears that I could determine whether a number is even or uneven by checking the decimals. This could be done by the remaining double (as integers will round off) in a string and check if this has a decimal. I could, but I should not. The reason is that you will introduce aextra steps, which is quite error prone.
So, how to simplify this operation? Exactly, we could use the modulo operator. By using the definition of the modulo operator we can deduce that when you use the modulo operator on a even number, r = 0. On the other hand, using it on an uneven number, r = 1.

Thus, instead of casting my integer to a string and check whether it has a decimal, you can use the following algorithm to check if a number is even or uneven:

integer x

if (x % 2 == 0)
  x is even
else
  x is uneven



Let's consider another application, namely:

Leap years
http://en.wikipedia.org/wiki/Leap_year

So we know that:
- If year % 4 = 0, then it's a leap year
- if a year % 100 and if year % 400 = 0, then it's a leap year
- if a year % 100 and if year % 400 != 0, then it's not a leap year
- else, it's not a leap year

By using a few if statements you can determine whether it's a leap year or not. This would look like:

if (((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0)
  year is a leap year
else 
  year is not a leap year



But the modulo operator is not only useful for determining whether a number is (un)even or to check if a year is a leap year, we can also use it for some (simplified) data structures in Java. One of the concepts is the:

Circularly array
In principle, you can use circularly arrays to implement queues. You might wonder: "Queues? What are those?" Well, wikipedia has an answer: http://en.wikipedia....ta_structure%29
So, to keep a long story short, a queue is comparable when doing groceries and you're queued. First who gets in the queue, is the first one who gets out. (this is the so-called FIFO principle)

Now, suppose I use an array to store elements in my queue. Let's assume I already enqueued (added items to the queue) and dequeued (removed items), leading to the following situation:

[][][][][][F][I]....[I]...[R]....[][][][]
//F is front
//I is just an item
//R is rear
//[] are empty spots



What happens in the queue, is that when I enqueue, I add the element at the rear [R] and when I dequeue, I remove the item at the front [F].

Now, given this situation, if I continue to enqueue, this situation might arise:
[][][][][][F][I]....[I]...[R]
//F is front
//I is just an item
//R is rear
//[] are empty spots


Now [R] is at the end of my array. If I would add two more elements, I'd get an Array Out of Bound Exception. (as the index R would be lying outside the bounds of the array) But... My array is actually not full, I can still store items in front of [F]

So, what I can do, is wrap R around the array. In that case, the positions R and F can be calculated by the modulo operator:
r = (r+1) % N
f = (f+1) % N
N being the capacity of the array holding/representing the queue.

Another example would be:

Hashtables
Suppose I want to implement a hashtable by means of an array (I know this implementation is not the "real way" you should implement it, but it's for illustrative purposes only)

A hashtable makes use of hashes, integers representing a string or an object. If I would have an array with the size 10 and a hashcode is 49 (because this is possible), I cannot add that entry in my table, as this will result in an Array Out of Bound Exception.

But what I can do, is this:
i = hashcode % N
N being the capacity and i being the index where the hashcode needs to be saved.

Basically, the modulo operator "scales" my hashcode down such that it "fits" within the indices of the array.
Furthermore, another application of the modulo operator in the context of hashtables is linear probing: http://en.wikipedia..../Linear_probing

Hope this clearifies the magic and applications of the % (modulo) operator ^^

Other References:
Implementation of the datastructures by means of an array were cited from Algorithms and Datastructures in JAVA, by Michael T. Goodrich and Roberti Tamassia.

Is This A Good Question/Topic? 5
  • +

Replies To: The use of the modulo (%) operator

#2 elgose  Icon User is offline

  • D.I.C Head

Reputation: 102
  • View blog
  • Posts: 228
  • Joined: 03-December 09

Posted 05 April 2012 - 06:13 PM

Good overview of modulo - it's a funky topic for a new programmer.

One thing you may want to reconsider or reword:

View Postkarabasf, on 04 April 2012 - 02:27 AM, said:

Modulo operator (Note that '%' is the modulo operator in Java)
if r = x % y, then a non-negative q exist, such that
x = q*y + r


While I believe the mathematical definition of a modulo operation requires 'x' and 'y' to be non-negative (and thus 'q'), in Java I don't believe this is the case.

Just running a test:
	int a = 15 % (-4);
	System.out.println(a);


outputs 3. Using your values above:
x := 15
y := -4
r := 3
then x = q*y+r becomes
15 = -4q + 3
12 = -4q
q = -3

Not a biggie, and like I said I think your definition follows the stricter definition of modulo in mathematics, but it may set limitations for the operator that doesn't actually exist for a new programmer.

On another note, I find it very interesting that you can get negative remainders:

	int a = (-15) % (-4);
	System.out.println(a);


will output -3. Weird and definitely a potential pitfall!
Was This Post Helpful? 0
  • +
  • -

#3 karabasf  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 202
  • View blog
  • Posts: 417
  • Joined: 29-August 10

Posted 06 April 2012 - 01:33 AM

Hello elgose, I am glad that you liked my tutorial about the modulo operator.

Regarding to your two questions, I did some (extra) research about the modulo operator, references can be found here:

http://en.wikipedia....odulo_operation
http://en.wikipedia....ular_arithmetic

But to keep a long story short, I consider first the negative divisor. According to the second link:

Quote

For a positive integer n, two integers a and b are said to be congruent modulo n, written:


Although this says nothing about the range of values for n, I am not sure if it's meaningful if n has a negative value. (So even this mystery remains unclear for me)

However, regarding the second question, consider the second link. According to the table, the result of the modulo operator in Java has the same sign as the dividend (the number which needs to be divided, or in your case, -15)

Although I couldn't answer all of your questions, I hope this clarifies the things a little bit ^^
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1