When are leap years, exactly?
Learning conditional statements through leap years
(First time here? The previous post may be helpful)
Everyone’s heard of leap years. They’re the years during which February has an extra day, the 29th, and unless you were born on February 29th, you probably don’t spend too much time thinking about them. But you do know when they occur, right? If your answer is “every four years” then I have some pedantic news for you: not quite. Most of the time in the Gregorian Calendar (the global calendar you almost certainly use), a year is a leap year if it is divisible by 4. A number x being divisible by 4 means that 4 divides evenly into x. Said another way, x is divisible by 4 if x / 4 is a whole number with no remainder; the years 1996, 2000, 2004, 2008, 2012 are all divisible by 4. There’s an exception to this definition of leap year, however. If the year is divisible by 100 and not divisible by 400, it isn’t a leap year. So 2000 is a leap year but 2100 is not.
The reasoning behind this is actually pretty mundane. If the length of a year were exactly 365.25 days, then adding a day every four years would ensure that our calendar matched the astronomy it’s based on (since 0.25 * 4 = 1). Unfortunately, the length of a year is just shy of 365.25 days, so every once in a while a year that would normally be a leap year is considered a regular year. I don’t know why the year being divisible by 100 but not 400 became the criterion but that’s just the way it is, I suppose. So while calculating if a year is a leap year is still simple, it’s not as simple as checking if it’s divisible by 4.
Let’s add an instruction to Cake that tells us if a year is a leap year. As an aside, the Gregorian Calendar wasn’t adopted until 1582, so this won’t make sense for very old years, but it’s close enough for our purposes. Here’s a description of the instruction:
- leap(year): returns whether or not year is a leap year
How would you go about writing it? The first thing to note is what kind of information the instruction returns. The “whether or not” in the description suggests that the instruction doesn’t return a number. Instead, it returns true or false. Cake uses these words exactly as you would expect. We’ll go into the details of how to manipulate them later, but for now just recognize that true and false aren’t numbers (well, technically they reduce to numbers like everything else in programming languages, but they can’t be added, subtracted, etc. like numbers and shouldn’t be treated as such).
So leap returns either true or false depending on whether the year you give it is a leap year or not. This leads to another question. What other instructions return true or false? Nothing we’ve defined yet. Let’s fix that with another instruction:
- x == y: returns true if x equals y
This instruction tests for equality. If x is the same number as y then x and y are equal. Otherwise, they’re unequal. For example, 1 == 1 is true but 2 == 3 is false. The reason this instruction is == and not = is due merely to convention — single equals signs mean something different, which we’ll get to later. In terms of PEMDAS, equality has the lowest priority. You could rewrite it PEMDASE, where the last E stands for equality. By convention, everything gets evaluated before equality.
This equality instruction is useful in a lot of different contexts, but here are two instructions that go well with it:
- if (x) then (y)
- if (x) then (y) else (z)
The first instruction is used when you may or may not want to call another instruction depending on a condition. More explicitly, x is a condition; that is, an instruction that returns true or false; y is another instruction that is computed if computing x returns true. If computing x returns false, y is ignored. The second instruction is similar but adds a second component, else. If x returns false, z is computed. To clarify, the meanings of if, then, and else are basically the same as the meanings of their English equivalents. Let’s illustrate this with an informal example in English: if it is raining today then I will bring my raincoat. This example mimics the first instruction above, the plain if then. Here’s another example: if today is a weekday then I will go to work; else, I will relax. This mimics the second instruction, if then else, in which either outcome of the condition results in an action.
Consider how useful if instructions and == instructions can be when used together:
On the surface, this code may look a bit silly. Of course 0 == 1 will never return true! But look at the other parts. Depending on whether two numbers are equal, different numbers are returned. If the instruction after if returns true then x is returned; else, y is returned. Let’s look at a more realistic example:
Remember, 3 + 4 and 4 + 3 get computed before they are compared with ==. So what is this code saying? It’s testing a fact about addition. If 3 plus 4 is the same as 4 plus 3 then Cake returns x. Otherwise, it returns y. I hope you agree that y will never be returned. (But while 3 plus 4 being the same as 4 plus 3 is intuitively obvious, proving it is not as easy. We’ll eventually get to that).
Now that we’ve seen how if then else can be used, let’s apply it to our original task: defining leap. Every leap year is divisible by 4, so let’s start with that. There’s only one problem: Cake doesn’t have a divisibility instruction. There’s no way to know if 25 is divisible by 4. You might think the answer relates to division — and you’re right — but Cake’s division operator isn’t much help. 25 / 4 returns 6.25. It’s easy for us humans to say that since 6.25 isn’t a whole number, 25 isn’t divisible by 4. The question is how do we express that through Cake? The answer is, as usual, by adding another instruction:
- x % y: return the remainder of x / y
This instruction is called modulo. Pronounced “x modulo y” or often “x mod y”, the % instruction is a very useful one you should get familiar with. As some practice, what property or idea does this code test for?
If you’re not sure, try out some examples. Replace x with actual numbers. Try small ones like 0, 1, and 2 and also big ones like 930, 1001, and 10000. What about negative numbers like -3 and -11? Can you see the pattern this code produces?
If not, please don’t worry. I’m here to teach, not test, and these ideas are not intuitive to those unaccustomed to this kind of thinking. The answer is that this code tests if x is even. If x is even, it returns true. If x is odd, it returns false. To understand this, analyze what x % 2 does: if x is even, then dividing it by 2 results in a whole number — that is, a number with no remainder or fraction next to it. Since there is no remainder, x % 2 must be 0 since % returns the remainder of x / 2. On the other hand, if x is odd, then dividing it by 2 results in a fraction; for instance, 5 / 2 = 2.5, or 2 ½. Since there is always a remainder of 1/2, any odd number modulo 2 returns 1. No matter what odd number you plug into x % 2, there is always a remainder of 1. Here’s the next question to think about: if x % 2 must return either 0 or 1, what must x % 3 return? What about x % 4, etc.? There is most certainly a pattern.
Think about what that pattern may be before reading on. When you think you’ve figured it out (or are sick of thinking about it), consider this answer: x % y must be smaller than y. Why must this be so? Take a look at this figure first:
The top part shows 8 divided by 2. Since 4 circles of 2 fit into 8, 8 divided by 2 is 4. Because the circles fit perfectly with nothing leftover, 8 mod 2 is 0. The bottom part shows 7 divided by 2. Since 3 circles of 2 fit into 7 with 1 circle leftover, 7 divided by 2 is 3.5. Since there is a block leftover (represented by pink in the figure), 7 mod 2 is 1.
Imagine how the figure of 8 divided by 3 would look; since circles are added 3 at a time until adding more would exceed 8, the number of circles leftover can’t be 3 or more — if 3 or more circles were leftover, then 3 more circles could be added. Therefore, the number of leftover circles cannot be more than 3 - 1, which is 2. So the general rule is that x % y must be smaller than y.
Let’s see if we have all the tools we need to write the leap instruction. First, we’ll deal with the simpler case of testing whether or not a number is divisible by 4:
If x is divisible by 4 then dividing it by 4 should have a remainder of 0. In this case, x % 4 must be 0. So far so good. What about the other part, where a year isn’t a leap year if it’s divisible by 100 and not 400? How about this:
While this code is certainly longer, no individual piece is actually any more complicated than what we’ve seen before. Everything in it is old material. The first part is identical to the previous code. If x is divisible by 4, then do something; else, do something else. The difference is what’s in the then and else parts. This else, located on the last line, is simple to explain: if x is not divisible by 4, then return false, since a year must be divisible by 4 to be a leap year. The then takes a bit more to explain: any time Cake has reached this then, located at the beginning of the second line, it has already been established that x is divisible by 4. Now we want to make sure that if it’s divisible by 100, it is also be divisible by 400 (this is just the original requirement reworded a bit). That’s what the code in the outer parentheses of the second line does. Let’s look at it in isolation:
If x is divisible by 100 then x % 400 is computed. If x is divisible by 400, this instruction returns true, making this whole part of the code return true. If x isn’t divisible by 400, then the code returns false. Taking a step back, if x isn’t divisible by 100 then (since we know it’s divisible by 4) it must be a leap year, so the else part returns true. In other words, if x isn’t divisible by 100, we don’t even need to check if it’s divisible by 400 — we just return true.
And that’s that! Using the full code above, leap can determine if the number you give it is a leap year or not. It might seem amazing how much goes into such a simple process. It is amazing, but the process is hardly simple, as I think this explanation demonstrates. When you look carefully, seemingly obvious questions like “is 2000 a leap year?” turn out to rely on many pieces, all of which must be understood and put together. Don’t let this discourage you, however. The flip side is that by learning how to break down a concept like “leap year” into smaller, manageable pieces, you will gain valuable skills that can be applied to much more difficult problems. We’ll get to those soon enough but next time I want to focus on rewriting leap in a more readable, intuitive way. It will, of course, require learning a few new instructions!
Image credit: Sun
