## Tomohiko Sakamoto’s Day-Of-Week Algorithm

### June 17, 2016

Here is Sakamoto’s algorithm for calculating the day of the week, taken from the comment that introduces the code:

Jan 1st 1 AD is a Monday in Gregorian calendar.

So Jan 0th 1 AD is a Sunday [It does not exist technically].Every 4 years we have a leap year. But xy00 cannot be a leap unless xy divides 4 with reminder 0.

y/4 – y/100 + y/400 : this gives the number of leap years from 1AD to the given year. As each year has 365 days (divdes 7 with reminder 1), unless it is a leap year or the date is in Jan or Feb, the day of a given date changes by 1 each year. In other case it increases by 2.

y -= m So y + y/4 – y/100 + y/400 gives the day of Jan 0th (Dec 31st of prev year) of the year. (This gives the reminder with 7 of the number of days passed before the given year began.)

Array t: Number of days passed before the month ‘m+1’ begins.

So t[m-1]+d is the number of days passed in year ‘y’ upto the given date.

(y + y/4 – y/100 + y/400 + t[m-1] + d) % 7 is reminder of the number of days from Jan 0 1AD to the given date which will be the day (0=Sunday,6=Saturday).

int dow(int y, int m, int d) { static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}; y -= m < 3; return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7; }

Another description is given here.

Your task is to write a program that implements the day-of-week algorithm shown above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

A Haskell version, with a variant (dow’) that provides a little more type safety.

Here’s a solution in x86 assembly.

/* dow.s */

.section .data

t:

.long 0,3,2,5,0,3,5,1,4,6,2,4

.section .text

.globl dow

.type dow,@function

# int dow(y, m, d);

dow:

# Save old base pointer

pushl %ebp

movl %esp, %ebp

# Create a local variable for

# the result.

# result: -4(%ebp)

subl $4, %esp

# Arguments:

# y: 8(%ebp)

# m: 12(%ebp)

# d: 16(%ebp)

# %ebp Offsets:

.equ result, -4

.equ y, 8

.equ m, 12

.equ d, 16

# if (m < 3) –y;

cmpl $3, m(%ebp)

jge proceed

decl y(%ebp)

proceed:

# result = y

movl y(%ebp), %ecx

movl %ecx, result(%ebp)

# result += y/4

movl $0, %edx

movl y(%ebp), %eax

movl $4, %ecx

divl %ecx

addl %eax, result(%ebp)

# result -= y/100

movl $0, %edx

movl y(%ebp), %eax

movl $100, %ecx

divl %ecx

subl %eax, result(%ebp)

# result += y/400

movl $0, %edx

movl y(%ebp), %eax

movl $400, %ecx

divl %ecx

addl %eax, result(%ebp)

# result += t[m-1]

movl m(%ebp), %ecx

decl %ecx

movl t(,%ecx,4), %ecx

addl %ecx, result(%ebp)

# result += d

movl d(%ebp), %ecx

addl %ecx, result(%ebp)

# result = result % 7

movl $0, %edx

movl result(%ebp), %eax

movl $7, %ecx

divl %ecx

movl %edx, result(%ebp)

# Save result

movl result(%ebp), %eax

# Restore old base pointer

movl %ebp, %esp

popl %ebp

ret

Here’s a C program that calls the day-of-week function.

Here’s example usage.

language=”asm” didn’t work for formatting my last post. Here’s the assembly code formatted with language=”text”.