## 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.

Pages: 1 2

### 3 Responses to “Tomohiko Sakamoto’s Day-Of-Week Algorithm”

1. Globules said

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

```import Data.Vector

t :: Vector Int
t = fromList [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4];

-- Given a year, month (1-12) and day of month return the day of the week (0-6).
dow :: Int -> Int -> Int -> Int
dow y m d =
let y' = if m < 3 then y - 1 else y
in (y' + y' `div` 4 - y' `div` 100 + y' `div` 400 + t ! (m-1) + d) `mod` 7

-- A slightly more typesafe variant.

data Month = Jan | Feb | Mar | Apr | May | Jun |
Jul | Aug | Sep | Oct | Nov | Dec
deriving (Enum, Show)

data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
deriving (Enum, Show)

-- Given a year, month and day of month return the day of the week.
dow' :: Int -> Month -> Int -> Day
dow' y m d = toEnum \$ dow y (fromEnum m + 1) d

main :: IO ()
main = do
print \$ dow  2016   6 18
print \$ dow' 2016 Jun 18
```
```\$ ./dow
6
Sat
```
2. Daniel said

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
# 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
# result += t[m-1]
movl m(%ebp), %ecx
decl %ecx
movl t(,%ecx,4), %ecx
# result += d
movl d(%ebp), %ecx
# 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.

```/* main.c */

#include <stdio.h>
#include <stdlib.h>

int dow(int y, int m, int d);

int main(int argc, char* argv[]) {
if (argc != 4) {
fprintf(stderr, "3 arguments are required (year, month, day)\n");
return 1;
}
int year = atoi(argv);
int month = atoi(argv);
int day = atoi(argv);
int day_of_week = dow(year, month, day);
printf("%d\n", day_of_week);
return 0;
}
```

Here’s example usage.

```\$ as --32 -o dow.o dow.s
\$ gcc -m32 -o main main.c dow.o
\$ ./main 2017 8 28
1
\$ ./main 2017 8 2
3
\$ ./main 2017 8 27
0
```
3. Daniel said

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

```/* 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
# 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
# result += t[m-1]
movl m(%ebp), %ecx
decl %ecx
movl t(,%ecx,4), %ecx
# result += d
movl d(%ebp), %ecx
# 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
```