HPR Episode: Doomsday Remainders
Last Episode on Conway's Doomsday Rule ends with teaser on MOD(), a
"remainder" function defined for integer values (whole numbers):
MOD(K, m) = remainder when K is divided by "modulus" m.
Examples:
a. MOD(207, 7) = MOD(207 - 140, 7) = MOD(67, 7) = 4
b. MOD(1234567, 2) = 1 because the number is odd
MOD() function found in most spreadsheet programs, but it also shows up
as an operator in some programming languages: (a % b), or (a mod b).
Other functions referenced:
DIV(K, m) = quotient in integer division
where K = m * quotient + remainder (not returned)
0 <= remainder < m
DIVMOD(K, m) = (quotient, remainder) when K is divided by m
where remainder = MOD(K, m)
quotient = DIV(K, m)
K = m * quotient + remainder
References:
1. Modular arithmetic:
Wikipedia:
https://en.wikipedia.org/wiki/Modular_arithmetic
Khan Academy:
https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/what-is-modular-arithmetic
Better Explained:
http://betterexplained.com/articles/fun-with-modular-arithmetic/
MathWorld: Proprietary Software Vendor giving it away
http://mathworld.wolfram.com/Congruence.html
2. MOD(), DIV() and DIVMOD() or equivalent operators in programming
ALGOL
https://en.wikipedia.org/wiki/ALGOL_60
Pascal
http://www.conservapedia.com/Pascal_%28programming_language%29
GNU C (stdlib.h):
http://www.gnu.org/software/libc/manual/html_node/Integer-Division.html#Integer-Division
Haskell:
http://www.haskell.org/tutorial/numbers.html
ML:
http://www.standardml.org/Basis/integer.html
Python:
2.x http://docs.python.org/2/library/functions.html#divmod
3.x http://docs.python.org/3/library/functions.html#divmod
Ruby:
http://ruby-doc.org/core-2.0/Numeric.html
Background:
Integer division applies only to integer values (dividend 'a' and
divisor 'd'), and it has two answers, rather than just a single number
as you might get from a calculator.
The two answers are called the quotient 'q' and remainder 'r'.
- Quotient is the largest number q such that (q * d) <= a.
- Remainder is the number 'r', with 0 <= r < d and a = (q*d) + r
Note: If r >= d, you could squeeze out another 'd' and add +1 to q.
Convention: If r == 0, we say that "d divides a", or "d divides a
evenly" (unnecessary in 'math talk'). Notation is "d | a".
Obvious Point: While integer division has two answers (q, r) in every
case, we have no duty to pay attention to both of them.
- Quite often, we just want the quotient and ignore the remainder.
- Surprisingly, there are times when we are only interested in 'r'.
Huh? When would we want only a remainder?
------------------------------------------
Doomsday Rule itself contains examples of all three "use cases":
http://en.wikipedia.org/wiki/Doomsday_rule
Example: Find day of week for Thursday, 20 January 1898 (in detail)
1. Anchor day of week for 1800s: Friday.
- We found this using (36524 mod 7) = 5 (or -2) for the 1600s and
1700s. The year 1600 has anchor Tuesday, so 1700 is two days
earlier (Sunday) and 1800 is two days before that (Friday).
2. In-century year "y": 1898 / 100 = (q=18, r=98), and y = r or 98
- We will use notation y = 1898 mod 100, or 98
3. Number of 12-year cycles in y: y / 12 = (q=8, r=2)
- Cycle count = q or 8, or 98 // 12 = 8 (// --> ignore fractions)
- Leftover years in next cycle = r or 2, which is 98 mod 12
4. Number of leap years in current cycle: 2 / 4 = (q=0, r=2)
- Leap years = q or 0, so 2 // 4 = 0
5. Offset within century = (8 + 2 + 0) mod 7 = +10 mod 7, or +3
6. Doomsday for 1898 = Friday + 3 days, or Monday
7. Day of Week for 20 January 1898:
Day_index = [(20 January - ref. date 10 January) + 1=Monday] mod 7
= (10 + 1) mod 7
= 4 <--- The remainder IS the answer here, too.
8. Answer is day of the week 4, or Thursday
So Doomsday gives examples of all three applications of integer division
a. Quotient and Remainder in 12-year cycle and 'leftovers' count
b. Quotient-only in step 4, to find leap years
c. Remainder-only in steps 1, 2, 5 and 7.
This show is primarily about remainder-only calculations, which use the
MOD() function or 'mod' operator. To make the obvious point, the answer
in the remainder-only integer division of (207 / 7) is (207 mod 7) = 4.
Let's agree to just call this (207 mod 7) from now on.
Claim: 'mod' is not just about days of the week, or hours of the day.
Mod is different in each implementation: spreadsheets, Python, bc
http://en.wikipedia.org/wiki/Modulus_operation
Warning for Excel Users: Mod in Excel works differently than in VBA.
a) Worksheet function MOD(K, m) follows the sign of 'm'
b) VBA for Excel operator (K Mod m) follows the sign of 'K'.
Note: "Go figure".
To be fair, VBA was developed years after Excel. It was also supported
independently by another team, and this difference between VBA (x Mod y)
and Excel MOD(X, Y) was apparently intended to provide backward
compatibility with Visual Basic 3.
VB source compatibility allowed VBA code to be migrated into Excel
Automation code in VB Projects with fewer conversion headaches.
Breaking compatibility on a basic arithmetic operation between Visual
Basic dialects would have created serious maintenance problems. It was
deemed more important to preserve VB family harmony than to make a major
change to maintain consistency with the corresponding "legacy" worksheet
function from Excel.
Python List Syntax and Subscripting:
Doomsday "dayOfTheWeek" function computed a number from 0-6 as a code
for the computed day of the week, and then mapped it to a name using a
lookup in a Python "list" object.
my_list = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday",
"Friday", "Saturday"]
How it works: my_list[0] is "Sunday", my_list[1] is "Monday", ...
up to my_list[5] is "Friday" and my_list[6] is "Saturday".
Negative subscripts walk through the list backwards from the end to the
beginning, except that the last element is my_list[-1], or "Saturday".
Positives run this way ------>
|-----------------------------------------------|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | <-- positive
|-----------------------------------------------|
| Sun | Mon | Tues | Wed | Thurs | Fri | Sat |
|-----------------------------------------------|
| 0 | -6 | -5 | -4 | -3 | -2 | -1 | <- negative and 0
|-----------------------------------------------|
<------ Negatives run this way
Diff: 0 7 7 7 7 7 7
Observe that the positive and negative subscripts are either exactly
the same (at Zero) or exactly a week apart. So they always refer to
the same day of the week in this addressing scheme.
References on Python lists, "slicing" and negative subscripts:
1. ZetCode: http://zetcode.com/lang/python/lists/
2. Python Tutorial:
http://docs.python.org/2/tutorial/introduction.html
Find "Indices can be negative"
The "bc" script correction: Leaving magic numbers like 420 behind.
If the final day of the week offset is computed from a negative number
because a reference date comes later in the year than the target date,
the 'bc' mod operator (%) will return a negative offset. A negative
index won't work nicely in a 'bc' array, as it does in Python lists.
Interim fix: Add a sufficiently large magic number to the differences,
so that the final dividend 'x' is positive when fed into (x mod 7). If
the magic number is also a multiple of 7, it will not change the final
remainder.
Suggested fix: Leave 'x' alone, and let y = (x mod 7) have whatever
sign it needs to have. Compute the offset as [ (y + 7) mod 7 ].
Case 1: y = (x mod 7) is non-negative
* So y is 0, 1, 2, 3, 4, 5, or 6
y + 7 is 7, 8, 9, 10, 11, 12, or 13 respectively
* (y + 7) mod 7 converts y from: 0 --> 0, 1 --> 1, 2 --> 2, 3 --> 3,
4 --> 4, 5 --> 5, and 6 --> 6.
Note: Very nice. It does no harm to usual case.
Case 2: y = (x mod 7) is not positive
* So y is 0, -1, -2, -3, -4, -5, or -6
y + 7 is 7, 6, 5, 4, 3, 2, or 1 respectively
(y + 7) % 7 is 0, 6, 5, 4, 3, 2, or 1
* (y + 7) mod 7 converts y from: 0 --> 0, -1 --> 6, -2 --> 5,
-3 --> 4, -4 --> 4, -5 --> 2, and -6 --> 1.
Note: Adding 7 fixes the negatives, and the (y + 7) % 7 operation
fixes the index for Sunday (7 --> 0). Sweet!
Applications in Computer Programming
1. Canonical Example: Evens and Odds are remainders (K mod 2).
a. Simplest case, because there are only two options:
K is Even: (K mod 2) is 0
K is Odd: (K mod 2) is 1.
b. Evens/Odds show up surprisingly often in programs
- Formatting output for accounting reports
- Creating printed documents in book form: left vs right pages
- Simulations that switch scenarios ("regimes") with a coin-toss
2. Programming Language Support:
a. MOD() function or (a mod b) operator of some kind is "everywhere"
b. Coercion of zero/non-zero, empty/non-empty to True/False in
"IF (condition) do-stuff" statements is in some languages.
c. Programming idiom supported by (a), (b) together is easy, clean
3. Case Study: do_Odd() versus do_Even(), with trigger value in N
Even/Odd Processing: Check for zero remainder mod 2
if ((N mod 2) == 0):
do_Even()
else:
do_Odd()
4. Case Study #2: Long-running processes, log or print status messages
* Long-running processes can be helped by optional status messages.
- On-screen messages, log entries, or both. Matter of taste.
- Turning this crap off is essential when you don't need it
* Debugging info on each iteration can be too much of a good thing
- Can log every 'M' iterations to get a sampling of results
- MOD() can help here
To show status every M iterations or records, assuming sequence # 'j'
# Stop Every M: Check for a zero remainder mod M
if ( (j mod M) == 0):
show_status()
5. Variant: Data doesn't include a sequence number 'j', so I must make
my own value. If I don't need the absolute number, I can make the
value of 'j' recycle every M iterations.
# We can introduce in-cycle offset by setting 'j' to p != 0.
j = 0
for each data_record in my_file:
do_stuff_to_data(data_record)
# Add 1 to 'j' to avoid logging topmost record in file
j = (j + 1) mod M
# Show status when 'j' is zero
# With offset 0, that's M, 2M, 3M, ...
if j == 0:
show_status()
next data_record
Cheaper: Skip the division, and set j to 0 when it grows to size M
# Insert warm-up counter and processing loop here
pass
# Set in-cycle offset here
j = 0
for each data_record in my_file:
do_stuff_to_data(data_record)
# Increment here to make 1=topmost, 2=next, etc.
j += 1
# Without mod, no danger of accidentally logging topmost record
# "Inspired" by (j mod M)
if (j >= M):
j = 0
show_status()
next data_record