Corrección del algoritmo de Sakamoto para encontrar el día de la semana

Estoy usando el algoritmo de Sakamoto para averiguar el día de la semana a partir de una fecha determinada. ¿Alguien puede decirme la exactitud de este algoritmo? Solo quiero esto del 2000 al 2099.

El algoritmo de Wikipedia se da como referencia.

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

Bueno, puedes decir simplemente que es correcto … Suponiendo que la matriz t[] sea ​​correcta, que puedes verificar con solo 12 controles puntuales (uno por cada mes usando cualquier día / año).

El y -= m < 3 es un buen truco. Crea un "año virtual" que comienza el 1 de marzo y finaliza el 28 de febrero (o 29), poniendo el día adicional (si corresponde) al final del año; o más bien, al final del año anterior . Entonces, por ejemplo, el año virtual 2011 comenzó el 1 de marzo y finalizará el 29 de febrero, mientras que el año virtual 2012 comenzará el 1 de marzo y finalizará el 28 de febrero siguiente.

Al poner el día adicional para los años bisiestos al final del año virtual, el rest de la expresión se simplifica enormemente.

Veamos la sum:

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

Hay 365 días en un año normal. Eso es 52 semanas más 1 día. Entonces, el día de la semana cambia un día por año, en general. Eso es lo que el término está contribuyendo; agrega uno al día por cada año.

Pero cada cuatro años es un año bisiesto. Esos contribuyen un día extra cada cuatro años. Gracias al uso de años virtuales, solo podemos agregar y/4 a la sum para contar cuántos días bisiestos suceden en años. (Tenga en cuenta que esta fórmula supone redondeos de división enteros).

Pero eso no es del todo correcto, porque cada 100 años no es un año bisiesto. Entonces tenemos que restar y/100 .

Excepto que cada 400 años es un año bisiesto de nuevo. Entonces tenemos que agregar y/400 .

Finalmente, solo agregamos el día del mes d y un desplazamiento de una tabla que depende del mes (porque los límites del mes dentro del año son bastante arbitrarios).

Luego tome todo el mod 7 ya que ese es el tiempo de una semana.

(Si las semanas fueron ocho días, por ejemplo, ¿qué cambiaría en esta fórmula? Bueno, obviamente sería el mod 8, también. Y el y debería ser 5*y , porque 365% 8 == 5. También la tabla mensual t[] necesitaría ajustes. Eso es todo.

Incidentalmente, la statement de Wikipedia de que el calendario es "bueno hasta el 9999" es totalmente arbitrario. Esta fórmula es válida por el tiempo que nos apeguemos al calendario gregoriano , ya sean 10 años, 100 años, 1000 años o 1 millón de años.

[editar]

El argumento anterior es esencialmente una prueba por inducción. Es decir, suponiendo que la fórmula funcione para un particular (y, m, d), demuestras que funciona para (y + 1, m, d) y (y, m, d + 1). (Donde y es un "año virtual" que comienza el 1 de marzo). Entonces, la pregunta clave es, ¿cambia la sum en la cantidad correcta a medida que se pasa de un año al siguiente? Con el conocimiento de las reglas del año bisiesto, y con el "año virtual" teniendo el día adicional al final del año, lo hace trivialmente.

Recientemente escribí una publicación de blog sobre este algoritmo aquí .

La idea básica detrás del algoritmo es para febrero y enero contar el día de la semana a partir del 31 de diciembre del año anterior . Para todos los demás meses contaremos el día de la semana del año actual 31 Dic. Hacemos esto en dos pasos, primero calculamos el día de la semana del último día del mes anterior al mes actual m luego solo agregamos el módulo d siete.

31 Dec 1 AC es domingo que está codificado como 0, lunes es 1 etc. Así que tenemos: 0 + y + y/4 - y/100 + y/400 esto con y -= m < 3 computa el día de la semana de 31 Dec del año actual o del año anterior (según el mes). Nota: 365 % 7 == 1 esto explica por qué escribimos y lugar de 365*y . El último componente d es obvio ya que comenzamos a contar el día de la semana del mes anterior el último día.

La última parte que debe explicarse son los valores en el conjunto, para los dos primeros valores, estos son el número de días desde el año pasado 31 de diciembre hasta el inicio del mes % 7 . Para el rest de los meses, se niegan modulo siete días desde finales del mes anterior hasta el 31 de diciembre del año en curso. En otras palabras, restamos días por módulo de adición 7, por ejemplo, (ab)%7 = (a+(7-b%7))%7 .

Puede encontrar más explicaciones en mi blog.