Methods for Accelerating Conway's Doomsday Algorithm
updated arXiv version of this document:
http://arxiv.org/abs/1006.3913
and part 2
http://arxiv.org/abs/1010.0765
Abstract
We propose a simplification of a key component in the Doomsday Algorithm for calculating the day-of-the-week of any given date. In particular, we propose to replace the calculation of the required term:
floor(x/12) + x mod 12 + floor((x mod 12)/4)
with
2 y + 3(y mod 2) + z + leap
where
x is an input two-digit year;
y is the tens digit of x;
z is the ones digit of x;
leap is the number of leap years in the y decade less than or equal to x excluding the start of the decade;
We argue that this simplification makes the algorithm simpler and easier to calculate mentally.
Introduction
The Doomsday rule is an algorithm for calculating the day of the week for any given calendar date. It was invented by John Horton Conway in 1982. It was designed to be simple enough that, with practice, one can do the calculation in his head without paper or pencil and come up with an answer in just a few seconds. Conway himself was able to do the algorithm calculations in his head in about 2 seconds [1].
For brevity, we won't discuss the full algorithm here. Instead we refer the readers to excellent writeups [2][3] that describe the algorithm in full detail. We will, however, summarize key components of the algorithm to point out some important definitions and nomenclature.
The Doomsday algorithm's input is a calendar date of the form MM/DD/YYYY where MM is the month, DD is the day, and YYYY is the year. YYYY can further be broken down to its constituent century CC and year within the century YY. The output of the algorithm is a number between 0 to 6 that corresponds to each of the 7 days fo the week.
The key equation of the Doomsday rule can be described a sum (modulo 7) of three terms:
day_of_the_week = [doomscentury + doomsyear + doomsmonth ] mod 7
where:
doomscentury(CC) is a function of the input date's century
doomsyear(YY) is a function of the input date's 2-digit year within a century
doomsmonth(MM,DD) is a function of the input date's calendar month and day.
In this paper, we only really care about the doomsyear term. We will only gloss over the doomsmonth and doomscentury terms. The doomsmonth term is what takes advantage of the fact that April 4, June 6, August 8, October 10, and December 12 all fall on the same day of the week for any calendar year. The doomscentury term accounts for the quirk in the Gregorian calendar system where years that are divisible by 100 are not leap years except when they are divisible by 400. We will not attempt to simplify or discuss further the doomscentury and doomsmonth terms for the rest of this paper.
The doomsyear term is given by Conway [4] as:
floor(x/12) + x mod 12 + floor((x mod 12)/4)
where x is the input date's 2-digit year within a century.
The addition is always modulo 7, so the resulting doomsyear term is a number between 0 and 6, inclusive.
Related Work
In practice, calculating the doomsyear term is a bottleneck of the Doomsday algorithm. Aside from having to do divisions by 12 and 4, one has to keep in memory 3 numbers to add. The term given by Conway is actually already an acceleration method for the term
x + floor(x/4)
which, in practice, is difficult to calculate for two-digit input numbers mentally [2] especially if followed by a required modulo 7 operator. Several people have suggested acceleration methods for the doomsyear term. Conway himself offered a lookup table acceleration for it [3][5]. His acceleration method is arguably the fastest but it requires the memorization of 18 numbers and extra rules for handling leap years. In 2008, Mike Walters [6] came up with a simpliflication of the doomsyear term that involves addition of multiples of 11, a division by 2, and a negation modulo 7 operator. Bob Goddard [7] made improvements to this method in 2009. Our proposed acceleration method is just as simple as Mike Walters' and Bob Goddard's method. In addition, our proposed acceleration method is amenable to a table-lookup memorization similar to Conway’s lookup table acceleration.
Simplified Formula
Let us break down the two-digit year x into its constituent digits y and z, where y is the tens digit, and z is ones digit. That is,
http://arxiv.org/abs/1006.3913
and part 2
http://arxiv.org/abs/1010.0765
Abstract
We propose a simplification of a key component in the Doomsday Algorithm for calculating the day-of-the-week of any given date. In particular, we propose to replace the calculation of the required term:
floor(x/12) + x mod 12 + floor((x mod 12)/4)
with
2 y + 3(y mod 2) + z + leap
where
x is an input two-digit year;
y is the tens digit of x;
z is the ones digit of x;
leap is the number of leap years in the y decade less than or equal to x excluding the start of the decade;
We argue that this simplification makes the algorithm simpler and easier to calculate mentally.
Introduction
The Doomsday rule is an algorithm for calculating the day of the week for any given calendar date. It was invented by John Horton Conway in 1982. It was designed to be simple enough that, with practice, one can do the calculation in his head without paper or pencil and come up with an answer in just a few seconds. Conway himself was able to do the algorithm calculations in his head in about 2 seconds [1].
For brevity, we won't discuss the full algorithm here. Instead we refer the readers to excellent writeups [2][3] that describe the algorithm in full detail. We will, however, summarize key components of the algorithm to point out some important definitions and nomenclature.
The Doomsday algorithm's input is a calendar date of the form MM/DD/YYYY where MM is the month, DD is the day, and YYYY is the year. YYYY can further be broken down to its constituent century CC and year within the century YY. The output of the algorithm is a number between 0 to 6 that corresponds to each of the 7 days fo the week.
The key equation of the Doomsday rule can be described a sum (modulo 7) of three terms:
day_of_the_week = [doomscentury + doomsyear + doomsmonth ] mod 7
where:
doomscentury(CC) is a function of the input date's century
doomsyear(YY) is a function of the input date's 2-digit year within a century
doomsmonth(MM,DD) is a function of the input date's calendar month and day.
In this paper, we only really care about the doomsyear term. We will only gloss over the doomsmonth and doomscentury terms. The doomsmonth term is what takes advantage of the fact that April 4, June 6, August 8, October 10, and December 12 all fall on the same day of the week for any calendar year. The doomscentury term accounts for the quirk in the Gregorian calendar system where years that are divisible by 100 are not leap years except when they are divisible by 400. We will not attempt to simplify or discuss further the doomscentury and doomsmonth terms for the rest of this paper.
The doomsyear term is given by Conway [4] as:
floor(x/12) + x mod 12 + floor((x mod 12)/4)
where x is the input date's 2-digit year within a century.
The addition is always modulo 7, so the resulting doomsyear term is a number between 0 and 6, inclusive.
Related Work
In practice, calculating the doomsyear term is a bottleneck of the Doomsday algorithm. Aside from having to do divisions by 12 and 4, one has to keep in memory 3 numbers to add. The term given by Conway is actually already an acceleration method for the term
x + floor(x/4)
which, in practice, is difficult to calculate for two-digit input numbers mentally [2] especially if followed by a required modulo 7 operator. Several people have suggested acceleration methods for the doomsyear term. Conway himself offered a lookup table acceleration for it [3][5]. His acceleration method is arguably the fastest but it requires the memorization of 18 numbers and extra rules for handling leap years. In 2008, Mike Walters [6] came up with a simpliflication of the doomsyear term that involves addition of multiples of 11, a division by 2, and a negation modulo 7 operator. Bob Goddard [7] made improvements to this method in 2009. Our proposed acceleration method is just as simple as Mike Walters' and Bob Goddard's method. In addition, our proposed acceleration method is amenable to a table-lookup memorization similar to Conway’s lookup table acceleration.
Simplified Formula
Let us break down the two-digit year x into its constituent digits y and z, where y is the tens digit, and z is ones digit. That is,
y = floor(x/10)
z = x mod 10
For example, if x = 74, then y= 7 and z = 4. If x = 88, then y= 8 and z= 8.
Having defined y and z in terms of x, we propose the replacement doomsyear function as
doomsyear(y,z) = 2 y + 3 (y mod 2) + z + leap
We define an extra variable called leap as the number of leap years between the start of the y decade and the z year. If the start of a decade is a leap year, we don't count it. But if the year z is a leap year, we do include it. For example, if x = 88, the decade starts at 80 and we have leap = 2 because 84 and 88 are leap years. If x=74, the decade starts at 70 and we have leap = 1 because 72 is a leap year. In general, the variable leap can only have three values: 0 , or 1, or 2. There can't be more than 2 leap years after the start of a decade. Remember, we never include the start of the decade in our leap count.
z = x mod 10
For example, if x = 74, then y= 7 and z = 4. If x = 88, then y= 8 and z= 8.
Having defined y and z in terms of x, we propose the replacement doomsyear function as
doomsyear(y,z) = 2 y + 3 (y mod 2) + z + leap
We define an extra variable called leap as the number of leap years between the start of the y decade and the z year. If the start of a decade is a leap year, we don't count it. But if the year z is a leap year, we do include it. For example, if x = 88, the decade starts at 80 and we have leap = 2 because 84 and 88 are leap years. If x=74, the decade starts at 70 and we have leap = 1 because 72 is a leap year. In general, the variable leap can only have three values: 0 , or 1, or 2. There can't be more than 2 leap years after the start of a decade. Remember, we never include the start of the decade in our leap count.
In summary, our proposed method for calculating doomsyear breaks the 2-digit input year into its constituent digits; and does simple arithmetic on these digits. Afterwards, there is the addition of a leap year correction term. Our method essentially requires only 3 additions and a multiplication by 2. Moreover, since the input is broken down to single digit numbers, the calculations done only involve small numbers and are easy to do mentally. In fact, our doomsyear arithmetic only involves positive integers in between 0 to 31. This range of numbers happens to be the “calendar range” which probably cannot be avoided in the calculations of any calendar algorithm.
There are no explicit divisions or subtractions in our doomsyear formula. However, there are implicit divisions and subtractions needed when one is figuring out the leap year correction term and when one is doing a modulo 7 operation afterwards. Nevertheless, all doomsyear acceleration methods require these implicit divisions and subtractions!
Examples
Let's calculate the doomsyear term for these years:
1) 1974: y = 7, z = 4
leap = 1 because 1972 is a leap year
doomsyear = 2*7 + 3*1 + 4 + leap = 14 + 3 + 4 + 1 = 22 = 1 (mod 7)
2) 2040: y = 4, z= 0
leap = 0
doomsyear = 2*4 + 3*0 + 0 + leap = 8 + 0 + 0 + 0 = 1 (mod 7)
3) 2010: y = 1, z = 0
leap = 0
doomsyear = 2*1 + 3*1 + 0 + leap = 2 + 3 + 0 + 0 = 5 (mod 7)
4) 1988: y = 8, z= 8
leap = 2 because 1984 and 1988 are leap years
doomsyear = 2*8 + 3*0 + 8 + leap = 16 + 0 + 8 + 2 = 26 = 5 (mod 7)
5) 2007: y = 0, z= 7
leap = 1 because 2004 is a leap year
doomsyear = 2*0 + 3*0 + 7 + leap = 0 + 0 + 7 + 1 = 8 = 1 (mod 7)
6) 1998: y = 9, z=8
leap = 2 because 1992 and 1996 are leap years
doomsyear = 2*9 + 3*1 + 8 + leap = 18 + 3 + 8 + 2 = 31 = 3 (mod 7)
Tips and Tricks
Memorization and Lookup Tables
Let’s define the decade anchor to be the “(2y + 3 (y mod 2))” subexpression of the doomsyear term. This subexpression only depends on the y decade of the input year.
decade_anchor(y) = ( 2 y + 3 (y mod 2) ) mod 7
By virtue of memorizing the decade anchor for each decade, one can significantly speed-up the calculation of the doomsyear term. This memorization is, of course, optional. Here is the table to memorize:
If one memorizes this simple table of 10 numbers, one can avoid calculating the decade anchor “2y + 3 (y mod 2)” component of the doomsyear formula. The doomsyear formula is thus:
doomsyear(y,z) = decade_anchor(y) + z + leap
An important mnemonic that can aid in memorizing this table involves the observation of its clamping effect. That is, for the starting and ending decades of the 00’s and the 90’s, the decade anchor is 0. Thus, one only really needs to memorize 8 numbers when using this decade anchor lookup table acceleration trick.
Look Before You Leap
There are several tricks to make the calculation of the leap term easier. Let’s look at a table of possible values for the leap term depending on the digit year z:
One can easily see that for digit years 0 and 1, the leap value is always 0. Likewise, for the digit years 8 and 9, the leap value is always 2; and for the digit years 4 and 5, the leap value is always 1. So, we only really need to do leap year calculations when the digit year is 2, 3, 6, or 7. Furthermore, if one checks whether the decade is odd or even, leap year determination can be totally avoided at the expense of more memorization.
Lucky Number 7
Another tip for the calculation of the doomsyear term involves the observation that 7 = 0 in modulo 7 arithmetic. So the z term in the doomsyear formula can be dropped altogether for the years 07, 17, 27, 37, 47 etc.
Conclusion We presented an acceleration method for calculating the doomsyear term of the Doomsday rule. Our method is simple because it only involves additions and a multiplication by 2. Furthermore, we provided further tips and tricks that can give additional speed to our method. In the appendix section of this paper, we show that our acceleration method method is similar in form to Conway’s lookup table acceleration method, but requires less memorization.
References:
[1] Mark Alpert, ”Not Just Fun and Games”, Scientific American, April 1999.
[2] Wikipedia contributors, ”Doomsday Rule”, Wikipedia, The Free Encyclopedia.
[3] Rudy Limeback, “Doomsday Algorithm”,
http://rudy.ca/doomsday.html
[4] Richard Guy, John Horton Conway, Elwyn Berlekamp : "Winning Ways: For Your Mathematical Plays, Volume. 2: Games in Particular", Academic Press, London, 1982
[5] Sidney Graham, “Doomsday Rule”,
http://www.cst.cmich.edu/users/graha1sw/Pub/Doomsday/DoomsdayIntro.html
[6] Mike Walters, “An Easier Doomsday Algorithm”, Blogspot blog
http://easydoomsday.blogspot.com/
[7] Bob Goddard, “First Sunday Doomsday Algorithm”, Blogspot blog
http://firstsundaydoomsday.blogspot.com/
Appendix 1: Some Doomsyear Properties
Let us look at table 3 once again and observe some properties of the doomsyear term.
Property#1 Non-Leap-Year Increment
We can see from table 3 that the doomsyear increases by 1 for every non-leap year. This follows from the fact that 365 = 1 (mod 7); and the day of the week increases by one after each non-leap year.
Property#2 Leap-Year Increment
We can also see from table 3 that the doomsyear increases by 2 for every leap year. This follows from the fact that 366 = 2 (mod 7); and the day of the week increases by two after each leap year.
Property#3 Periodicity
The days of the week repeat with a period of 7. The leap years within a century repeat with a period of 4. It is no surprise that doomsyear values repeat every 28 years. 28 is, of course, the least common multiple of 7 and 4.
Property#4 Quasi-periodicity
We can observe from table 3 that the doomsyear value almost repeats a count of 0 to 6 every 5 or 6 years except for regular jumps occuring every leap year.We can call this property as quasi-periodicity.
Appendix 2: Conway’s Look-up Table Acceleration Method
John Horton Conway devised an acceleration method to avoid explicit calculation of the doomsyear term. In practice, Conway’s method is probably the fastest acceleration method for such, but it involves memorizing 18 numbers and some non-intuitive rules. In this section, we will describe Conway’s look-up table method. In the next section, we will compare and contrast our method with Conway’s acceleration method.
Conway’s lookup table method requires memorizing the years of the century where the doomsyear value is zero. Let us call these numbers as zero-anchor years. These are:
0, 6, 11.5, 17, 23, 28, 34, 39.5, 45
51, 56, 62, 67.5, 73, 79, 84, 90, 95.5
There’s actually the added complication of the half-numbers: 11.5, 39.5, 67.5 and 95.5. These half-numbers mean that the preceding year has doomsyear value 6 and the succeeding year has doomsyear value 1. For example, doomsyear(11) = 6, and doomsyear(12) = 1; doomsyear(67) = 6, and doomsyear(68) = 1. These half-numbers occur because of the increment-by-2 property of doomsyear values during leap years. In effect, a doomsyear of value 0 got skipped in the half-number locations.
The gist of Conway’s acceleration method is to find the nearest zero-anchor year to your input year. Afterwards, subtract the zero-anchor year from your input year and add a leap year correction to get the doomsyear value For this section, we will restrict the zero-anchor to be the less than your input year. It is actually possible to select a zero-anchor greater than your input year, but it requires remembering some additional rules when dealing with leap years and half-numbers. This is tricky and error-prone, so we will not cover it.
Here are the steps of Conway’s acceleration method:
Examples
Let's calculate the doomsyear term for these years:
1) 1974: y = 7, z = 4
leap = 1 because 1972 is a leap year
doomsyear = 2*7 + 3*1 + 4 + leap = 14 + 3 + 4 + 1 = 22 = 1 (mod 7)
2) 2040: y = 4, z= 0
leap = 0
doomsyear = 2*4 + 3*0 + 0 + leap = 8 + 0 + 0 + 0 = 1 (mod 7)
3) 2010: y = 1, z = 0
leap = 0
doomsyear = 2*1 + 3*1 + 0 + leap = 2 + 3 + 0 + 0 = 5 (mod 7)
4) 1988: y = 8, z= 8
leap = 2 because 1984 and 1988 are leap years
doomsyear = 2*8 + 3*0 + 8 + leap = 16 + 0 + 8 + 2 = 26 = 5 (mod 7)
5) 2007: y = 0, z= 7
leap = 1 because 2004 is a leap year
doomsyear = 2*0 + 3*0 + 7 + leap = 0 + 0 + 7 + 1 = 8 = 1 (mod 7)
6) 1998: y = 9, z=8
leap = 2 because 1992 and 1996 are leap years
doomsyear = 2*9 + 3*1 + 8 + leap = 18 + 3 + 8 + 2 = 31 = 3 (mod 7)
Tips and Tricks
Memorization and Lookup Tables
Let’s define the decade anchor to be the “(2y + 3 (y mod 2))” subexpression of the doomsyear term. This subexpression only depends on the y decade of the input year.
decade_anchor(y) = ( 2 y + 3 (y mod 2) ) mod 7
By virtue of memorizing the decade anchor for each decade, one can significantly speed-up the calculation of the doomsyear term. This memorization is, of course, optional. Here is the table to memorize:
If one memorizes this simple table of 10 numbers, one can avoid calculating the decade anchor “2y + 3 (y mod 2)” component of the doomsyear formula. The doomsyear formula is thus:
doomsyear(y,z) = decade_anchor(y) + z + leap
An important mnemonic that can aid in memorizing this table involves the observation of its clamping effect. That is, for the starting and ending decades of the 00’s and the 90’s, the decade anchor is 0. Thus, one only really needs to memorize 8 numbers when using this decade anchor lookup table acceleration trick.
Look Before You Leap
There are several tricks to make the calculation of the leap term easier. Let’s look at a table of possible values for the leap term depending on the digit year z:
One can easily see that for digit years 0 and 1, the leap value is always 0. Likewise, for the digit years 8 and 9, the leap value is always 2; and for the digit years 4 and 5, the leap value is always 1. So, we only really need to do leap year calculations when the digit year is 2, 3, 6, or 7. Furthermore, if one checks whether the decade is odd or even, leap year determination can be totally avoided at the expense of more memorization.
Lucky Number 7
Another tip for the calculation of the doomsyear term involves the observation that 7 = 0 in modulo 7 arithmetic. So the z term in the doomsyear formula can be dropped altogether for the years 07, 17, 27, 37, 47 etc.
Conclusion We presented an acceleration method for calculating the doomsyear term of the Doomsday rule. Our method is simple because it only involves additions and a multiplication by 2. Furthermore, we provided further tips and tricks that can give additional speed to our method. In the appendix section of this paper, we show that our acceleration method method is similar in form to Conway’s lookup table acceleration method, but requires less memorization.
References:
[1] Mark Alpert, ”Not Just Fun and Games”, Scientific American, April 1999.
[2] Wikipedia contributors, ”Doomsday Rule”, Wikipedia, The Free Encyclopedia.
[3] Rudy Limeback, “Doomsday Algorithm”,
http://rudy.ca/doomsday.html
[4] Richard Guy, John Horton Conway, Elwyn Berlekamp : "Winning Ways: For Your Mathematical Plays, Volume. 2: Games in Particular", Academic Press, London, 1982
[5] Sidney Graham, “Doomsday Rule”,
http://www.cst.cmich.edu/users/graha1sw/Pub/Doomsday/DoomsdayIntro.html
[6] Mike Walters, “An Easier Doomsday Algorithm”, Blogspot blog
http://easydoomsday.blogspot.com/
[7] Bob Goddard, “First Sunday Doomsday Algorithm”, Blogspot blog
http://firstsundaydoomsday.blogspot.com/
Appendix 1: Some Doomsyear Properties
Let us look at table 3 once again and observe some properties of the doomsyear term.
Property#1 Non-Leap-Year Increment
We can see from table 3 that the doomsyear increases by 1 for every non-leap year. This follows from the fact that 365 = 1 (mod 7); and the day of the week increases by one after each non-leap year.
Property#2 Leap-Year Increment
We can also see from table 3 that the doomsyear increases by 2 for every leap year. This follows from the fact that 366 = 2 (mod 7); and the day of the week increases by two after each leap year.
Property#3 Periodicity
The days of the week repeat with a period of 7. The leap years within a century repeat with a period of 4. It is no surprise that doomsyear values repeat every 28 years. 28 is, of course, the least common multiple of 7 and 4.
Property#4 Quasi-periodicity
We can observe from table 3 that the doomsyear value almost repeats a count of 0 to 6 every 5 or 6 years except for regular jumps occuring every leap year.We can call this property as quasi-periodicity.
Appendix 2: Conway’s Look-up Table Acceleration Method
John Horton Conway devised an acceleration method to avoid explicit calculation of the doomsyear term. In practice, Conway’s method is probably the fastest acceleration method for such, but it involves memorizing 18 numbers and some non-intuitive rules. In this section, we will describe Conway’s look-up table method. In the next section, we will compare and contrast our method with Conway’s acceleration method.
Conway’s lookup table method requires memorizing the years of the century where the doomsyear value is zero. Let us call these numbers as zero-anchor years. These are:
0, 6, 11.5, 17, 23, 28, 34, 39.5, 45
51, 56, 62, 67.5, 73, 79, 84, 90, 95.5
There’s actually the added complication of the half-numbers: 11.5, 39.5, 67.5 and 95.5. These half-numbers mean that the preceding year has doomsyear value 6 and the succeeding year has doomsyear value 1. For example, doomsyear(11) = 6, and doomsyear(12) = 1; doomsyear(67) = 6, and doomsyear(68) = 1. These half-numbers occur because of the increment-by-2 property of doomsyear values during leap years. In effect, a doomsyear of value 0 got skipped in the half-number locations.
The gist of Conway’s acceleration method is to find the nearest zero-anchor year to your input year. Afterwards, subtract the zero-anchor year from your input year and add a leap year correction to get the doomsyear value For this section, we will restrict the zero-anchor to be the less than your input year. It is actually possible to select a zero-anchor greater than your input year, but it requires remembering some additional rules when dealing with leap years and half-numbers. This is tricky and error-prone, so we will not cover it.
Here are the steps of Conway’s acceleration method:
1) Select the nearest zero-anchor year less than your input year.
2) Let z0 be the difference between your input year and the selected zero-anchor. Ignore fractional values of half-numbers in zero-anchor years. That is, treat 11.5, 39.5, 67.5, and 95.5 as 11, 39, 67, and 95 respectively in calculating the difference
3) Count the number of leap years between the zero-anchor and your input year. If the zero-anchor year is a leap year, do not include it. On the other hand, if your input year is a leap year, include it in the leap count. Let us denote this count of leap years as leap0
4) Add z0 and leap0 to get the doomsyear value. If the selected zero-anchor is a half-number, subtract 1 from the sum. We denote this as the anchor adjustment term needed for half-number zero-anchors.
To sum it all up, Conway’s acceleration method can be described by the equation:
doomsyear = anchor_adjustment + z0 + leap0
Note that the anchor_anjustment term is almost always zero except for half-number years where it has a value of –1.
Examples:
1) 1974:
zero-anchor is 1973
z0 = 1974 – 1973 = 1
leap0 = 0
doomsyear = 1 + 0 = 1
2) 2040:
zero-anchor is 2039.5
z0 = 2040 – 2039 = 1
leap0 =1 because 2040 is a leap year
doomsyear = -1 + 1 + 1 = 1
3) 2010:
zero-anchor is 2006
z0 = 2010 – 2006 = 4
leap0 = 1 because 2008 is a leap year
doomsyear = 4 + 1 = 5
4) 1988:
zero-anchor is 1984
z0 = 1988 – 1984 = 4
leap0 = 1 because 1988 is a leap year. Remember, we don’t count the zero-anchor
doomsyear = 4 + 1 = 5
5) 2007:
zero-anchor is 2006
z0 = 2007 – 2006 = 1
leap0 = 0
doomsyear = 1 + 0 = 1
6) 1998:
zero-anchor is 1995.5
z0 = 1998 – 1995 = 3
leap0 = 1 because 1996 is a leap year
doomsyear = -1 + 3 + 1 = 3
7) 1914:
zero-anchor is 1911.5
z0 = 1914– 1911 = 3
leap0 = 1 because 1912is a leap year
doomsyear = -1 + 3 + 1 = 3
8) 1972:
zero-anchor is 1967.5
z0 = 1972 – 1967 = 5
leap0 = 2 because 1968 and 1972 are leap years
doomsyear = -1 + 5 + 2 = 6
Appendix 3: A Comparison of Our Acceleration Method with Conway’s
As we mentioned in the tips and tricks section, our method is amenable to lookup table acceleration. In fact, we claim that after this lookup table acceleration, our method is very similar to Conway’s acceleration method. Let us compare and contrast the doomsyear equation for our method and Conway’s method. These are:
doomsyear(y,z) = decade_anchor(y) + z + leap
and
doomsyear(x) = anchor_adjustment(x) + z0 + leap0
respectively. We have carefully named different terms of the equations to highlight the similarities between both equations. Let us list down these similarities.
1) Both equations are the sum of 3 terms. Each of these terms correspond with a counterpart in the other method.
2) Both equations use memorization of an anchor year for the speedup. In our method, the starting year of the decade serves as the anchor. In Conway’s method, years with doomsyear value of zero are used as the anchor.
3) Both equations use z as the number of years between the input year and the anchor year.
4) Both equations contain a leap count correction term that counts the number of leap years between the anchor year and the input year.
We now list down differences between the 2 equations and mention some advantages of our method over Conway’s method.
1) In our method, z is not computed. It is part of the input. In Conway’s method, z0 has to be calculated by subtracting the zero-anchor year from the input year.
2) In our method, one has to memorize 10 digits for the anchoring. In Conway’s method, one has to memorize 18 numbers for the anchoring.
3) In our method, the leap count correction term follows a regular pattern for a given decade and is amenable to another speedup via memorization.
4) In our method, one can always fall back to using the “2y + 3 (y mod 2)” calculation if entries in the lookup table are forgotten.
2) Let z0 be the difference between your input year and the selected zero-anchor. Ignore fractional values of half-numbers in zero-anchor years. That is, treat 11.5, 39.5, 67.5, and 95.5 as 11, 39, 67, and 95 respectively in calculating the difference
3) Count the number of leap years between the zero-anchor and your input year. If the zero-anchor year is a leap year, do not include it. On the other hand, if your input year is a leap year, include it in the leap count. Let us denote this count of leap years as leap0
4) Add z0 and leap0 to get the doomsyear value. If the selected zero-anchor is a half-number, subtract 1 from the sum. We denote this as the anchor adjustment term needed for half-number zero-anchors.
To sum it all up, Conway’s acceleration method can be described by the equation:
doomsyear = anchor_adjustment + z0 + leap0
Note that the anchor_anjustment term is almost always zero except for half-number years where it has a value of –1.
Examples:
1) 1974:
zero-anchor is 1973
z0 = 1974 – 1973 = 1
leap0 = 0
doomsyear = 1 + 0 = 1
2) 2040:
zero-anchor is 2039.5
z0 = 2040 – 2039 = 1
leap0 =1 because 2040 is a leap year
doomsyear = -1 + 1 + 1 = 1
3) 2010:
zero-anchor is 2006
z0 = 2010 – 2006 = 4
leap0 = 1 because 2008 is a leap year
doomsyear = 4 + 1 = 5
4) 1988:
zero-anchor is 1984
z0 = 1988 – 1984 = 4
leap0 = 1 because 1988 is a leap year. Remember, we don’t count the zero-anchor
doomsyear = 4 + 1 = 5
5) 2007:
zero-anchor is 2006
z0 = 2007 – 2006 = 1
leap0 = 0
doomsyear = 1 + 0 = 1
6) 1998:
zero-anchor is 1995.5
z0 = 1998 – 1995 = 3
leap0 = 1 because 1996 is a leap year
doomsyear = -1 + 3 + 1 = 3
7) 1914:
zero-anchor is 1911.5
z0 = 1914– 1911 = 3
leap0 = 1 because 1912is a leap year
doomsyear = -1 + 3 + 1 = 3
8) 1972:
zero-anchor is 1967.5
z0 = 1972 – 1967 = 5
leap0 = 2 because 1968 and 1972 are leap years
doomsyear = -1 + 5 + 2 = 6
Appendix 3: A Comparison of Our Acceleration Method with Conway’s
As we mentioned in the tips and tricks section, our method is amenable to lookup table acceleration. In fact, we claim that after this lookup table acceleration, our method is very similar to Conway’s acceleration method. Let us compare and contrast the doomsyear equation for our method and Conway’s method. These are:
doomsyear(y,z) = decade_anchor(y) + z + leap
and
doomsyear(x) = anchor_adjustment(x) + z0 + leap0
respectively. We have carefully named different terms of the equations to highlight the similarities between both equations. Let us list down these similarities.
1) Both equations are the sum of 3 terms. Each of these terms correspond with a counterpart in the other method.
2) Both equations use memorization of an anchor year for the speedup. In our method, the starting year of the decade serves as the anchor. In Conway’s method, years with doomsyear value of zero are used as the anchor.
3) Both equations use z as the number of years between the input year and the anchor year.
4) Both equations contain a leap count correction term that counts the number of leap years between the anchor year and the input year.
We now list down differences between the 2 equations and mention some advantages of our method over Conway’s method.
1) In our method, z is not computed. It is part of the input. In Conway’s method, z0 has to be calculated by subtracting the zero-anchor year from the input year.
2) In our method, one has to memorize 10 digits for the anchoring. In Conway’s method, one has to memorize 18 numbers for the anchoring.
3) In our method, the leap count correction term follows a regular pattern for a given decade and is amenable to another speedup via memorization.
4) In our method, one can always fall back to using the “2y + 3 (y mod 2)” calculation if entries in the lookup table are forgotten.
Comments
Post a Comment