Displaying all posts from 2018 September.

## Calendrical Calculations, Part 2: Mod Math

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:

$dividend mod divisor = dividend − divisor ⋅ round ⁡ ( dividend divisor )$

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?

NameOrdinal DateOrdinal Date mod 7Day of the Week
Lance203685Thursday
Lucy205590Saturday
Samuel297286Friday
Helena302271Sunday
Nicholas308556Friday
Susan310693Tuesday
Daniel314753Tuesday
Juliana373822Monday
Ana393481Sunday
Amy404666Friday
Catherine411692Monday
Anastasia413630Saturday
Emily417314Wednesday
Patricia421525Thursday
Elisa421551Sunday

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.

If you would like to comment on something that you read, by all means, leave a note here. Please note that all comments are approved before being displayed to prevent spam comments.

 Name: E-mail: Subject: Text:

## Calendrical Calculations, Part 1: Cyclical vs. Linear

By some accident of probability, I have exactly eight nieces and no nephews. The fact that they're all nieces isn't relevant to the story; it's just interesting. The fact that there are eight of them is relevant.

So, it's my job as the bachelor uncle to buy the cool toys for my nieces on their birthdays. Since there are eight of them, I'm going to need help remembering their birthdates. Yes, I know that they have calendars and apps for your phone that will tell you these sorts of things, but I want us to understand how those apps work.

First, I e-mail my sister in Mexico, Helena, and my sister-in-law across town, Susan, to get a list of all the birthdates in their families. I'm going to compile their responses into a table of some sort.

Amy 10/15/10 23.9.2007 30.3.2013 9/17/12 March 4, 1986 31.5.2015 4/2/14 3.10.1982 6.5.2002 October 6, 1955 April 14, 1956 6/22/84 5/28/15 22.5.1981 1/22/85

Yuck. The dates don't look the same. Helena lives in Mexico, so, as one would expect, she provided the dates with the day of the month first, the month next and the year last. Susan, on the other hand living in the United States, gave me the dates in the American format: the month, followed by the day of the month and then followed by the year. Helena used four-digit years while Susan gave me two-digit years. I myself entered in a few birthdates for family members that I already knew, but I spelled out the months. When I got the responses, I just threw them onto a table the same way that I got them. They need to be consistent.

Let's try putting them all in my format.

Amy October 15, 2010 September 23, 2007 March 30, 2013 September 17, 2012 March 4, 1986 May 31, 2015 April 2, 2014 October 3, 1982 May 6, 2002 October 6, 1955 April 14, 1956 June 22, 1984 May 28, 2015 May 22, 1981 January 22, 1985

Now, it's sorted alphabetically by name. Here's the thing: I need to know who's birthday is coming up next. If the list were in order by birthday, I may be able to figure this out better. Let's tell the computer to sort it that way.

Lucy April 14, 1956 April 2, 2014 January 22, 1985 June 22, 1984 March 30, 2013 March 4, 1986 May 22, 1981 May 28, 2015 May 31, 2015 May 6, 2002 October 15, 2010 October 3, 1982 October 6, 1955 September 17, 2012 September 23, 2007

That didn't turn out the way that I expected it. It sorted it alphabetically by month. Also, it didn't even sort properly within the month. Look at the month of May: Samuel, Patricia and Elisa's birthdays seem to fall in order. However, Juliana's birthday is before any of theirs, but she's listed after. That's because ‘6’ comes after ‘2’ and ‘3’ when we sort alphabetically. We need to make these numbers somehow.

At my work, when we enter in dates into the computer system, we enter a two-digit month, a two-digit day of the month and then a two-digit year. For example, today, 2018 September 16 would be entered in as “091618”. Let's try entering the dates with this method and then sorting on that.

 Susan 012285 030486 033013 040214 041456 050602 052281 052815 053115 062284 091712 092307 100382 100655 101510

Yes, this really is how we enter the dates into the computer at work, and it's a bad way to do it. At least now, they're in the order that I want. Also, Catherine's having a birthday tomorrow! I need to get her a gift tonight! Before I can do that, I need to know how old she's going to be. Of course, I could just look at the number and deduce that she'll be six, but I need to get the computer to figure that out. Actually, what will be helpful would be to sort the list in such a way where the oldest people are on top and the youngest on the bottom. To do that, I need to change the date format again.

 Lance 19551006 19560414 19810522 19821003 19840622 19850122 19860304 20020506 20070923 20101015 20120917 20130330 20140402 20150528 20150531

Okay, we have a four-digit year, two-digit month and two-digit day of the month. This is still a bad way to do it in my opinion. However, there are computer systems that use this method. MySQL uses a similar method for storing its dates. Why is this bad then?

Let's take a moment to talk about time in the platonic sense. Not only do we perceive time in cycles, we order our lives around these cycles as well. Think of how often you wake up, attend religious ceremonies, get paid, pay the rent or the mortgage, pay taxes, vote or watch the Olympics. All of these events occur in cycles. The day is probably the most fundamental of these cycles, but even the day is broken up into smaller cycles. An analogue clock is the absolute perfect way to represent this. The instant that the second hand reaches the top of the clock, a new cycle of sixty seconds begins, and the number of these cycles that have passed is represented by the minute hand (and, similarly, the hour hand). Since we perceive time in cycles, it is natural that we represent time that way in our speech and our writing.

However, it is exactly deplorable to do mathematical calculations when time is represented in cycles. (It's possible… but it's also exactly deplorable.)

When dates get represented as numbers, they need to act like numbers. For example, if I'm travelling on the highway and if I'm at mile marker 269 and if I know my destination is at mile marker 116, I can easily subtract the two numbers to know that my destination is 153 miles away. This makes sense because… that's… just how numbers work!

Suppose that I want to know how much older Patricia is than Elisa. Using the numbers on our table, we can subtract Elisa's birthday (20150531) from Patricia's birthday (20150528). Doing the math tells us that Patricia is three days older than Elisa. Perfect right?

No! Let's try that again, except, let's see how much older Lance is than Nicholas. By doing the same subtraction, we get 289,616 days—which is close to 793 years. I happen to know that Lance was twenty-eight when Nicholas was born. Why did the math work for Patricia and Elisa but not for Lance and Nicholas? It's because Patricia and Elisa were both born in the same month—May of 2015. Lance and Nicholas weren't. This system has gaps in it—literally. For instance, the difference between 20171231 and 20180101 is only one day. However, if we subtract the two numbers, we get 8,870 and not… one (you know, kind of like we should). Also, what about a date like 20171581? That's not even a date that ever existed, but what would a computer program even do if it was given that input?

We want the dates to work the same way that our mile markers worked. In order to get that to happen, we have to abandon notating our dates in cycles and put them on a linear scale like the mile markers. (I do have to point out that the mile-marker analogy breaks down as soon as we realize that the mile markers reset at the state line.)

This is the way that most software that calculates dates already works! If you're a spreadsheet person, try this: open up your spreadsheet software—Excel, LibreOffice or, if you don't have any of these, Google Sheets. Select a cell and type in today's date (or press Ctrl+;). Select another cell and type in your birthdate. Select now a third cell and create a cell to subtract your birthdate from today's date. Once you press enter, the result that you should see is the number of days old you are. Divide that by 365.2425, and you should get your age in years.

The reason this works is because each cell in a spreadsheet has a value and a format. The format that you see is the date represented in the cycles that we humans are used to (i.e., years, months, days). However, the value that's in the cell is a number. If you want to see this number, select a cell and then change the number format for the cell to ‘General’ or ‘Automatic’. (This process is different in different spreadsheet programs.) It goes the other way around. Type ‘37045’ into a cell. Now, change the number format of the cell to a date. You'll end up with 2001 June 3.

If we take that table of dates from above and put it in a spreadsheet, we'd end up with this data:

 Lance 20368 20559 29728 30227 30855 31069 31475 37382 39348 40466 41169 41363 41731 42152 42155

While that's what the spreadsheet will actually store in the background, we can give the spreadsheet instructions to format the data however we want. It will convert the dates from these linear formats into the cyclical representations that we humans deal with. How those conversions are done is a topic for another time, but these dates on a linear scale are an improvement. Remember how I said that mathematical calculations are exactly deplorable with cyclical representations? Well, now, mathematical calculations are elegant and straightforward. Need to know what date it will be a hundred days from now? Tell the spreadsheet to add the days and let it do the math for you!

If you would like to comment on something that you read, by all means, leave a note here. Please note that all comments are approved before being displayed to prevent spam comments.

 Name: E-mail: Subject: Text:

## Time is the fire in which we burn.

So, the last time that I wrote a blog post here—nearly a year and a half ago—I was talking about a new software project that I had been working on for, at the time, about six months. I had said that the project was “pretty much already done”.

That part about it being pretty much already done… was not exactly the truth. There was also another lie: the one about my starting the project six months before the last blog post. In truth, I started this project back in college. Untruths aside, I think that my software project—despite being still unfinished—is done enough that I can finally let you in on the secret.

So, context: I grew up in what could be described as an evangelical environment. Each religion seems to have its holidays—and Christianity is no exception to that rule. However, my particular brand of vodka of Christianity certainly hadn't gotten that memo. Growing up, I seem to remember three Christian holidays: Christmas, Easter and Palm Sunday—end of list. I make the joke that, despite being Pentecostals, we didn't even celebrate Pentecost. Of course, my church also celebrated Independence Day, Memorial Day or any other day set aside for nationalistic glorification with the same sincerity because it conflated nationalism and spirituality (a disturbing trend that's a topic for another time).

Anyway, despite having just three holidays, there was still this awareness that there were other holy days. Of course, you couldn't escape Saint Valentine and Saint Patrick's days. Some people reminded us that Halloween had it's origins in Christian tradition before being appropriated by… satanists or something ('cause, you know, satanists and their candy…). Around Christmas time, you neither can't escape the barrage of Christmas carols—among them, “The Twelve Days of Christmas”. This raises the question: Twelve days? Well, which twelve days are these twelve days: the twelve before December 25 or the twelve after? (Spoiler alert: It's the twelve days after.)

Attending a Christian university, there was a little more exposure to these other holidays. Once, a professor asked us students if we were attending chapel on this particular day because it was “Monday Thursday”. What the !@#\$ is “Monday Thursday”?, I thought to myself. Fortunately, that was the beginning of the Wikipedia age where, if you really want to know something, an answer was no further than the closest computer. (However, this was still before the smartphone age where answers now are no further than your pocket.)

Being a computer-science student, during my senior year, I chalked together a little one-page, PHP script that, for any year that you gave it, would spit out a liturgical calendar. It was pretty minimal; it showed just a few holidays, it marked the beginning and the end of the liturgical seasons and it showed each particular day on the calendar in its appropriate liturgical color, but that was about it. PHP has a built-in function that made calculating the date of Easter easy, so there wasn't a great deal of effort that went into it. After a bit of time, that calendar just stayed forgotten in the deep recesses of my website.

Let's jump ahead about eight years. I'm now in a new religious tradition. Specifically, it's a tradition that is overflowing with various “holy days” (which is the etymology of the word holiday). After a few months in my new church, I pulled out the old calendar that I made in college and reworked it.

By reworked, I mean I burned down the old PHP calendar script that I made and started fresh. I made a second “object-oriented” attempt that was more trouble than it was worth, so I burned that one down too and started over a second time.

Third time's a charm… as the saying says. It is still a work in progress, and I've spent countless (as in, I've literally lost count) hours working on this, and I anticipate that I'll be spending plenty more. I still don't feel that it's “ready”, but, if all goes according to plan… it'll never be ready. However, I just discovered that my calendar has started to show up in some Google searches, so I've decided that it's time to release it. Just yesterday, I registered liturgical-calendar.com and moved the calendar from this website over to its new domain.

My new website displays the liturgical calendar of the Anglican Church of North America (which itself is a work in progress). In addition (while I haven't yet built any sort of way to switch between the two—it is a work in progress after all), I also included the liturgical calendar according to the Episcopal Church's 1979 Book of Common Prayer.

I could really talk a while about the nice features that I put into it, but I will just mention a few:

One, in true linguistics-nerd fashion, the capability to have the calendar available in multiple languages was built in from the start, and, as such, I included translations into Spanish and French.

Two, the calendar provides links to other websites for scripture readings. However, Anglicans don't necessarily use ordinary Bible translations when reading the Psalms. Typically, a separate psalter is provided within each of the various versions of the Book of Common Prayer. Since I couldn't find a decent website with the psalter, I created my own website of the psalter. The psalter website still needs a lot of work, but that in itself was a monumental task for something that's kind of an afterthought.

Three, while the calendar was programmed in PHP, I also rewrote all of the functionality in JavaScript as well so that moving from page to page within the site becomes lightning quick! For this project, I actually programmed it TypeScript, a computer language from Microsoft that adds static typing to JavaScript and then compiles to JavaScript. The lack of static typing is a frustration for me in both PHP and JavaScript (among other computer languages), and I'm thrilled that tools now exist for static typing.

Lastly, while Christians in “the West” all use the Gregorian calendar for their feasts and fasts, I included functionality for the use of calendars used by Christians in “the East” such as the Julian, Coptic, Ethiopic and Revised Julian calendars. For good measure, I also threw in the Hebrew calendar too. While I'm not actually using this functionality right now, it's… there. In the future, I may expand the website to include calendars from other traditions besides just the Anglican one. However, to include this functionality, I am indebted to Edward M. Reingold and Nachum Dershowiz for their fantastic book Calendrical Calculations which contained and explained all of the mathematics that I needed to support all of these calendars (except the Revised Julian calendar which I had to create myself). When it became clear that I needed something to help me with the calculations, I read online that Reingold and Dershowiz' book was the one to use. After reading it, I recommend it for anyone seeking an understanding of calendrical calculations.

It's been a good deal of work, and it's been a great deal of fun. Going forward, I hope to continue to work on this project, and I hope that it can be of use those who have great liturgical-calendar needs! Also, I hope that this gives me more things about which to write blog posts. I encounter a bit of frustration when I see examples of software development that don't properly compute dates and times correctly. I've gotten into more than a couple of arguments at work about this. Hopefully, I can write a few blog posts on this topic in the near future to inspire good coding practices. Right now, it's a miracle that I wrote this one.