The correctness of the Sakamoto algorithm to find the day of the week

Question

I use the Sakamoto algorithm to find out the day of the week from a specific date. Can someone tell me the correctness of this algorithm? I just want it from 2000 to 2099.

For reference, the algorithm from Wikipedia .

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; } 

Answer 1

Well, you can simply say that this is correct ... Assuming the t[] array is correct, which you can only check with 12 spot checks (one for each month using any day / year).

y -= m < 3 is a good trick. He creates a “virtual year,” which begins on March 1 and ends on February 28 (or 29), adding an extra day (if any) at the end of the year; or, rather, at the end of last year. So, for example, virtual 2011 began on March 1 and ends on February 29, and virtual year 2012 begins on March 1 and ends next February 28.

By putting the added day on leap years at the end of the virtual year, the rest of the expression will be greatly simplified.

Let's look at the amount:

 (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7 

In a normal year, 365 days. This is 52 weeks plus 1 day. Thus, the day of the week shifts one day per year, in general. This is what the term y does; he adds one per day for each year.

But every four years is a leap year. They contribute an extra day every four years. Thanks to the use of virtual years, we can simply add y/4 to the amount to calculate how many leap days will happen during y years. (Note that this formula assumes that integer division is rounded down.)

But this is not entirely correct, because every 100 years is not a leap year. Therefore, we need to subtract y/100 .

Except that every 400 years again a leap year. Therefore, we must add y/400 .

Finally, we simply add the day of the month d and the offset from the table, which depends on the month (since the boundaries of the month throughout the year are pretty arbitrary).

Then take the whole thing mod 7, as this is how long a week goes by.

(If the weeks were eight days, for example, what would have changed in this formula? Well, it would obviously be the 8th. Also y should be 5*y , because 365% 8 == 5. Now the table of the month t[] needs to be configured. This is it.)

By the way, the Wikipedia expression that the calendar is “good until 9999” is completely arbitrary. This formula is good because we adhere to the Gregorian calendar for a long time, be it 10 years, 100 years, 1000 years or 1 million years.

[edit]

The above argument is essentially proof of induction. That is, assuming that the formula works for a specific (y, m, d), you prove that it works for (y + 1, m, d) and (y, m, d + 1). (Where y is the "virtual year", starting March 1.) So, the main question: does the amount change by the correct amount when moving from one year to another? With knowledge of the rules of a leap year, and with a “virtual year” having an extra day at the end of the year, this is trivial.

Answer 2

I recently wrote a blog post about this algorithm here .

The main idea of ​​the algorithm is to calculate the day of the week from December 31 of the previous year in February and January. For all other months, we will consider the day of the week from the current year on December 31. We do this twice first, we calculate the day of the week of the last month of the month preceding the current month m , then we just add d modulo seven.

December 31, 1 BC - Sunday, which is encoded as 0, Monday - 1, etc. So, we have: 0 + y + y/4 - y/100 + y/400 this with y -= m < 3 calculates the day of the week on December 31 of the current year or the previous year (depending on the month). Note: 365 % 7 == 1 this explains why we wrote y instead of 365*y . The last component d is obvious, as we begin to count the day of the week from the previous month in the past.

The last part that needs to be explained is the values ​​in the array, for the first two values ​​this is the number of days from last year December 31 to the beginning of the month % 7 . During the remainder of the months they are canceled modulo seven days from the end of the previous month to December 31 of the current year. In other words, we subtract the days by adding modulo 7, for example. (ab)%7 = (a+(7-b%7))%7 .

You can find more explanation in my blog post.

Answer 3

This may not be the complete answer, like some of the above, but just wanted to add one thing about this array: 0 3 2 5 0 3 5 1 4 6 2 4

Consider the months starting in March and ending in February, as others have said:

1. Martha
2. april may
3. June
4. July
5. august
6. september
7. October-November
8. December
9. January

February Writing from January to December from above numbering:

So, consider this as an array: int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

Now for all the elements in the array just do: (2.6*m - 0.2) mod 7 analyze the result as an integer and you will get this: 0 3 2 5 0 3 5 1 4 6 2 4

• You can find this formula here: Wikipedia

 int dayOfWeek(int d, int m, int y){ // Months Array int t[] = {11,12,1,2,3,4,5,6,7,8,9,10}; // Convert months array for (int i = 0; i < 12; i++){ int ans = t[i] * 2.6 - 0.2; t[i] = ans % 7; } // Continue Algo if(m<3) y -= 1; int day = (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7; return day; } 

this: + y/4 - y/100 + y/400 refers to a leap year. Leap Year Verification Algorithm:

1. Ideally divided by 400 → true
2. IF divides perfectly by 100, but not by 400 → False
3. Divided by 4 → True

perform checks in the above order. Maybe that's why they subtracted y / 100 and added y / 4 & g / 400. Yes, stupid logic 😅

I know that this may not be the answer, but it can help those who find it difficult to remember / understand something, yes! not all of us have a high level of IQ understanding of things, and, unfortunately, some of us also cannot remember things, laughs.

Answer 4

For the Gregorian calendar

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

Explanation:

• See the commented out array for

  t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}; 

and compare it with the calendar for the whole year (run cal 2 to create a calendar in the terminal on linux / unix), mark the start day of the week for each month.

• Each normal year is shifted by one day of the week, and a leap year by two days of the week. as (365% 7) = 1 and (366% 7) = 2

  i= y+y/4-y/100+y/400 

• But we should not count the extra day if y have a leap year for 0 and 1 month

 y-=m<3 

• but in this way we also remove the extra day from non-leap years. therefore, we fill this gap by subtracting 1 day for each month after February.

  int t[12]={0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};