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.
MultiQuote
| 