Calendrical Calculations, Part 2: Mod Math
— Arvada, Colorado UNITED STATES
I'm hungry. Now, I have one of those microwavable Asian meals; all I need to do is add water and put it in the microwave. The instructions are telling me to heat it up for ninety seconds. Okay, but my microwave won't accept ninety seconds. Instead, I have to express the value in components of minutes and seconds. Now, the answer is 1:30—I know this, and I didn't need a calculator to figure this out… but how would we program a computer to calculate this for us?
These type of problems come up frequently when working with calendars, so I want to talk about this before we delve further because different computer languages do different things and also come to different conclusions when you ask them to perform the same calculation.
When I first learned long division back in third grade, I was taught to compute remainders. For example, if I was asked to calculate nine divided by four, I would have told you that it was two with a remainder of one. The next year, in fourth grade, I was taught how to divide using decimals. Now, nine divided by four became 2.25.
In some computer languages like JavaScript or PHP, if I program it to divide two numbers, I will get the fourth-grade answer—that is, a floating-point number as a result. In JavaScript, console.log(90 / 60) gives me 1.5. Simple.
However, when working with calendars, it's typically the third-grade answer that we want. This is called integer division. Other computer languages like C, C++, Java and C# will do integer division by default if we're dividing two integers. For example, in Java, evaluating System.out.println(90 / 60); will give a result of 1 and not 1.5 as we may expect. What about the remainder then? We would have to do something called a modulo operation to obtain that. In Java, the modulo operation would look like this: System.out.println(90 % 60);. That percent sign is essentially saying, “Divide 90 by 60, but return the remainder instead of the quotient”. The result that we get from that is 30. Combining those two results, we just split 90 seconds into its components of 1 minute and 30 seconds.
Integer division and modulo are two operations that have a special mathematical relationship. The general rule is this:
Most computer languages follow this rule. If that's the case, how then can computer languages come to different results? Well, you'll notice that there's a round function in that formula. While each computer language may follow this general rule, computer languages do not necessarily round using the same method.
So let's talk about rounding now. In mathematics, there are several different ways to round numbers. We're going to focus on two: the floor function and the ceiling function. You'll typically find these in any programming language's standard library.
The ceiling function (sometimes spelled ceil), will round the parameter to the closest integer that is greater than or equal to the parameter. We don't use it that much for calendrical calculations. The floor function on the other hand gets used very much. It does the opposite of ceiling: it rounds the parameter to the closest integer that is less than or equal to the parameter. When we do integer division and modulo, we almost always want to use the floor function as our rounding method.
That is not what we get with C, C++, Java, C#, JavaScript or PHP. When these languages perform integer division, they simply get rid of the digits on the right side of the decimal point of the result. This is called truncation. Now, if you think about it, truncation sounds like it's the same as the floor function. That's because it is… for positive numbers! As soon as negative numbers get thrown into the mix, we end up with results consistent with performing the ceiling function. That's bad!
The consequences for modulo arithmetic are this: if we use the floor function when doing integer division, the result of the modulo operation will always have the same sign as the divisor. However, if we truncate the result of the integer division instead, the result of the modulo operation will always have the same sign of the dividend.
Here's an example. Last week, I talked about representing dates as linear numbers. I put all of my family members' birthdates into a table with the linear-date values. One benefit of representing dates like this is that it's easy to find out what day of the week a certain date is. You just divide the number by seven and take the remainder. The remainder will correspond to a day of the week. What happens if we do that to my family members' birthdates?
| Name | Ordinal Date | Ordinal Date mod 7 | Day of the Week |
|---|---|---|---|
| Lance | 20368 | 5 | Thursday |
| Lucy | 20559 | 0 | Saturday |
| Samuel | 29728 | 6 | Friday |
| Helena | 30227 | 1 | Sunday |
| Nicholas | 30855 | 6 | Friday |
| Susan | 31069 | 3 | Tuesday |
| Daniel | 31475 | 3 | Tuesday |
| Juliana | 37382 | 2 | Monday |
| Ana | 39348 | 1 | Sunday |
| Amy | 40466 | 6 | Friday |
| Catherine | 41169 | 2 | Monday |
| Anastasia | 41363 | 0 | Saturday |
| Emily | 41731 | 4 | Wednesday |
| Patricia | 42152 | 5 | Thursday |
| Elisa | 42155 | 1 | Sunday |
It worked great. Now suppose that I want to add my great-grandmother to the list. She was born 1893 February 13. In the number system that we're using, that translates to -2511. That's a negative number, but the beauty of representing dates on a linear scale is that negative numbers aren't a problem. So what day of the week was my great-grandmother born on? Well, if we do the modulo operation in a computer language that uses the floor method like Ruby, Lua, Perl or Python, we get 2 which corresponds to Monday. However, what happens when we try that modulo operation in computer languages that use the truncate method like C, Java or PHP? Well, the dividend is negative and, in these programming languages, the result of the modulo operation has to have the same sign as the dividend, so we end up with… -5. Positive dividends can have positive results and negative dividends can have negative results. Since both positive and negative dividends are possible, the unfortunate consequence of this is that we need to program our code to handle negative and non-negative results.
With calendars, we consistently want to use the floor method, so how do we deal with the these problems?
One way is to use a computer language that has floor division right out of the box. Guido van Rossum, the creator of Python, once wrote a blog post about Python's use of the floor method instead of the truncate method. He made the right choice in my opinion.
Some computer languages provide give you options. For example, while Java's / and % operators use the truncate method, Java now has floorDiv and floorMod functions that you can use when you need the floor method. Both Haskell and Lisp have a rem function that uses the truncate method and a mod function that uses the floor method.
Sometimes, we don't have a choice in what programming language that we use. In those instances, one thing that can help is to rewrite code to avoid negative numbers. Obviously, that isn't always an option.
The method that I see most often in production code is to check if the result of the modulo operation is negative and, if it is, add the divisor to it. Here's a C function that does just that.
int Modulo(int X, int Y) {
int Result;
Result = X % Y;
if (Result < 0) {
Result += Y;
}
return Result;
}
This works all of the time… unless your divisor is negative.
If you're using computer languages that don't have integer division (like PHP and JavaScript), there's a more straightforward solution.
function Modulo(X, Y) {
return X - Y * Math.floor(X / Y);
}
The advantage with this method is that it works even when the divisor is negative.
Now that we have proper understanding of the nuances of integer division and modulo operations in programming languages, we can move on to applying these in converting calendar dates to linear dates. More on that to come.
Tags: Calendars, Mathematics, Software Development
Write or View Comments • Permanent Link
