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

### June 17, 2016

Sakamoto’s algorithm is identical to Zeller’s Congruence, which we studied in a previous exercise, with the straight-line formula precomputed in the t array. Here’s our implementation:

```(define (day-of-week year month day)
(let ((t '#(0 3 2 5 0 3 5 1 4 6 2 4))
(year (if (< month 3) (- year 1) year)))
(vector-ref '#(Sun Mon Tue Wed Thu Fri Sat)
(modulo (+ year (quotient year 4)
(- (quotient year 100)) (quotient year 400)
(vector-ref t (- month 1)) day) 7))))```

And here are some examples:

```> (day-of-week 2016 2 28)
Sun
> (day-of-week 2016 2 29)
Mon
> (day-of-week 2016 3 1)
Tue
> (day-of-week 2016 6 17)
Fri```

You can run the program at http://ideone.com/4CCiub.

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
```