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

    /* 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[1]);
      int month = atoi(argv[2]);
      int day = atoi(argv[3]);
      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
      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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: