In diesem Dokument werden verschiedene Zusammenhänge und Algorithmen, die bei der Berechnung von Kalenderdaten auftreten, vorgestellt. Die Darstellung der benutzten Funktionen und Algorithmen erfolgt in einer JavaScript-ähnlichen Notation. Alle Algorithmen wurden vom Autor selbst entwickelt (bis auf den Algorithmus von Gauss natürlich) und basieren nur auf Allgemeinwissen.
Letzte Änderung: 15. November 2004
Im Unterschied zu der Implementierung in den meisten Programmiersprachen
wird hier von einer richtigen Implementierung der ganzzahligen
Division, d.h. der Operatoren /
(div
) und %
(mod
), ausgegangen.
Außerdem arbeiten alle hier vorgestellten Operationen nur mit
ganzzahligen Werten und produzieren auch nur solche.
Zunächst gilt allgemein für alle p und q mit q <> 0:
p = (p / q) * q + p % q
Bei der richtigen Implementierung von /
und %
gilt weiterhin für
beliebige Werte von n:
p / q = (p + n * q) / q - n p % q = (p + n * q) % q
Das heißt aber auch, daß die 0
in keinster Weise eine ausgezeichnete
Stellung einnimmt, im Gegensatz zu den üblichen Implementierungen, bei
denen das nicht der Fall ist. Man kann also davon ausgehen, daß sich
alle Operationen vernünftig verhalten, und in der Tat ist es auch so,
wie sich immer wieder zeigt. Natürlich muß bei konkreten Berechnungen
auf den implementierungsabhängigen Wertebereich der Zahlen Rücksicht
genommen werden, im allgemeinen kann man von 32 Bit inklusive
Vorzeichen ausgehen.
Die Beliebigkeit von n kann aber auch dazu benutzt werden, um die
Implementierung der falschen Operatoren zu korrigieren, unter
Zuhilfenahme der vorzeichenlosen Varianten, die immer korrekt sind.
Diese werden jetzt mit udiv
und umod
bezeichnet, während die neu zu
definierenden und vorzeichenbehafteten Funktionen mit div
und mod
bezeichnet werden und nun aus den vorzeichenlosen Varianten abgeleitet
werden sollen.
Die folgende Fälle müssen unterschieden werden:
q > 0 und p >= 0
div(p, q) = udiv(p, q) mod(p, q) = umod(p, q)
q > 0 und p < 0
div(p, q) = -udiv(-p - 1, q) - 1 mod(p, q) = -umod(-p - 1, q) - 1 + q
q < 0
div(p, q) = div(-p, -q) mod(p, q) = -mod(-p, -q)
Die Funktion bitnot(x) = -x - 1
, die hier implizit im zweiten
Fall benutzt wird, bildet den Bereich der positiven Zahlen genau auf
den Bereich der negativen Zahlen ab. Dies gilt auch umgekehrt. Bei der
gebräuchlichen 2-er Komplementdarstellung von Zahlen geht also nichts
verloren. Anders sieht es im letzten Fall (q < 0) aus, wo sich der
Wert -2^31
darstellen läßt, der Wert von 2^31
dagegen aber
möglicherweise nicht mehr.
Es sollte darauf hingewiesen werden, daß udiv
und umod
tatsächlich
identisch sind zu div
und mod
, und daß deren Unterscheidung hier
nur benutzt wurde, um deutlich zu machen, daß die entsprechenden
Operationen ohne Vorzeichen stattfinden sollen. Davon abgesehen sind
alle angegebenen Relationen unter allen Umständen
gültig, ausgenommen ist natürlich der Fall q = 0. Aus der ersten
Beziehung des zweiten Falles folgt:
div(p, q) = -div(-p - 1, q) - 1 = -(div(-p - 1, q) + 1) = -div((q - 1) - p, q)
Damit ergibt sich beispielsweise:
n - div(p, q) = div((n + 1) * q - 1 - p, q)
Oder mittels /
anstatt div
ausgedrückt:
n - p / q = ((n + 1) * q - 1 - p) / q
Diese Äquivalenz wird in einigen der folgenden Berechnungen ausgenutzt.
Im Rest des Dokuments wird nur noch Gebrauch von /
(div
) und %
(mod
) gemacht, wobei aber immer der entsprechende korrigierte
Operator gemeint ist. Negative Werte von q kommen hier nicht vor.
Die Grundlage aller Datumsberechnungen sind Tage, wobei die Zeit
innerhalb eines Tages hier keine Rolle spielt. Der Bezugspunkt ist der
1970-01-01
. Die meisten Berechnungen gelten nur im Zeitraum vom
1900-03-01
bis zum 2100-02-28
, weil im folgenden nur die einfache
Schaltjahresregel benutzt wird.
Die folgenden Bezeichnungen werden für verschiedene Variablen benutzt:
y
1900
-2100
m
1
-12
d
1
-31
(je nach Monat)cw
1
-53
(je nach Jahr)days
1970-01-01
weeks
1970-01-01
liegtwkday
In diesem Abschnitt werden die grundlegenden Funktionen zur Berechnung von days und von y, m und d vorgestellt.
getdays(y, m, d)
1970-01-01
,
ausgehend von Jahr y, Monat m und Tag d.
Bereichsüberschreitungen werden automatisch so
behandelt, als ob das Datum entsprechend richtig angegeben worden
wäre, z.B. entspricht der Wert 2004-03-00
dem Datum
2004-02-29
.getdate(days)
1970-01-01
. Das Ergebnis
wird als Liste (y, m, d) zurückgegeben.Es gilt:
getdays(1970, 1, 1) = 0
Außerdem gilt für alle x:
getdays(y, m, d + x) = getdays(y, m, d) + x
Um die Berechnung der Funktionen zu vereinfachen, verlegt man den
Bezugspunkt auf den unmittelbar einem Schalttag folgenden Tag, also den
1. März. Dadurch erscheint ein Schalttag am Ende eines Jahres, sofern
er überhaupt vorhanden ist. Als Bezugsjahr wurde hier 1968
gewählt,
und damit ist der 1968-03-01
der Bezugspunkt und die Verschiebung von
days ergibt sich zu:
getdays(1970, 1, 1) - getdays(1968, 3, 1) = 365 + 365 - 59 = 671
Der 1. März eines Jahres y läßt sich mit der einfachen Schaltjahresregel wie folgt berechnen:
getdays(y, 3, 1) = (y - 1968) * 365 + (y - 1968) / 4 - 671 = ((y - 1968) * 1461) / 4 - 671 = ((y - 1970) * 1461 + 2 * 1461) / 4 - 671 = ((y - 1970) * 1461 + 2) / 4 + 2 * 365 - 671 = ((y - 1970) * 1461 + 2) / 4 + 59
Umgekehrt läßt sich zu einer vorgegebenen Anzahl von Tagen days das Jahr y des 1. März ermitteln, welches dem Wert von days am nächsten kommt, d.h. es soll gelten:
getdays(y, 3, 1) <= days < getdays(y + 1, 3, 1)
Damit ergibt sich weiter, wobei der Subtrahent die Anzahl der
Schalttage seit dem 1968-03-01
angibt:
y = ((days + 671) - (days + 671 + 1) / 1461) / 365 + 1968 = ((days + 671) * 1461 + 1460 - (days + 671 + 1)) / 1461 / 365 + 1968 = ((days + 671) * 1460 + 1459) / 365 / 1461 + 1968 = ((days + 671) * 4 + 3) / 1461 + 1968 = ((days - 59) * 4 + 2 * 1461 + 1) / 1461 + 1968 = ((days - 59) * 4 + 1) / 1461 + 1970
Die Anzahl der Tage t seit dem 1. März des Jahres y ergibt sich dann aus:
t = days - getdays(y, 3, 1) = days - ((((days - 59) * 4 + 1) / 1461) * 1461 + 2) / 4 - 59 = ((days - 59) * 4 + 3 - (((days - 59) * 4 + 1) / 1461) * 1461 - 2) / 4 = ((days - 59) * 4 + 1 - (days - 59) * 4 - 1 + ((days - 59) * 4 + 1) % 1461) / 4 = (((days - 59) * 4 + 1) % 1461) / 4
Der Wert von t kann nun zur Berechnung des Monats m' herangezogen
werden, wobei dessen Nummerierung bei 0
für März beginnt und bei 11
für Februar endet. Später kann dann m' zu m mit der üblichen
Zählweise umgerechnet werden. Im Zuge dessen kann dann auch das dem
Datum entsprechende Jahr y korrigiert werden.
Zufälligerweise (oder war es Absicht beim Entwurf des Kalenders?) ist die Abfolge der Monatslängen von m' sehr gut zur Berechnung geeignet:
31 30 31 30 31 31 30 31 30 31 31 28/29
Die letzte Länge ist einfach der Rest und ergibt sich automatisch aus der Jahreslänge. Das gleiche gilt für den letzten Block, wenn man den ganzen Bereich in 5-er Blöcke teilt. Ein 5-er Block hat eine Länge von 153 Tagen. Jeden 5-er Block kann man schließlich in 2-er Blocks unterteilen, die eine Länge von 61 Tagen haben.
Mit diesen Feststellungen ergibt sich also:
m' = (t / 153) * 5 + ((t % 153) / 61) * 2 + ((t % 153) % 61) / 31 = (t / 153) * 5 + (((t % 153) / 61) * 62 + (t % 153) % 61) / 31 = (t / 153) * 5 + (t % 153 + (t % 153) / 61) / 31 = (t / 153) * 5 + ((t % 153) * 62) / 31*61 = (t / 153) * 5 + ((t % 153) * 2) / 61 = ((t / 153) * 305 + (t % 153) * 2) / 61 = (t * 2 - t / 153) / 61 = (t * 305 + 152) / 61 / 153 = (t * 5 + 2) / 153
Umgekehrt läßt sich der erste Tag t0 des Monats m bzw. m' nach folgendem Schema berechnen:
m' = (m - 3) % 12 t0 = (m' / 5) * 153 + ((m' % 5) / 2) * 61 + ((m' % 5) % 2) * 31 = (m' / 5) * 153 + (m' % 5) * 31 - (m' % 5) / 2 = (m' / 5) * 153 + ((m' % 5) * 62 + 1 - (m' % 5)) / 2 = (m' / 5) * 153 + ((m' % 5) * 61 + 1) / 2 = ((m' / 5) * 306 + (m' % 5) * 61 + 1) / 2 = (m' * 61 + m' / 5 + 1) / 2 = (m' * 306 + 5) / 2 / 5 = (m' * 153 + 2) / 5
Damit ergibt sich schließlich:
t0 = (((m - 3) % 12) * 153 + 2) / 5
Der Tag d im Monat m' ließe sich aus t mit Hilfe der folgenden Relation ermitteln:
d = ((t % 153) % 61) % 31 + 1
Günstiger ist es aber, t in Relation zu t0 auszudrücken und dann diese Beziehung zu vereinfachen:
d = t - t0 + 1 = t - (m' * 153 + 2) / 5 + 1 = t - (((t * 5 + 2) / 153) * 153 + 2) / 5 + 1 = (t * 5 + 2 - ((t * 5 + 2) / 153) * 153) / 5 + 1 = ((t * 5 + 2) % 153) / 5 + 1
Mit Hilfe des gesammelten Wissens lassen sich nun die beiden Funktionen
getdate
und getdays
definieren.
getdate
Die Funktion getdate
kann wie folgt berechnet werden:
function getdate(days) { var t = (((days - 59) * 4 + 1) % 1461) / 4; var m = (t * 5 + 2) / 153 + 2; return list(((days - 59) * 4 + 1) / 1461 + 1970 + m / 12, m % 12 + 1, ((t * 5 + 2) % 153) / 5 + 1); }
Optimiert und im prozeduralen Stil sieht die Funktion getdate
so aus:
function getdate(days) { var y, m, d; d = (days - 59) * 4 + 1; y = d / 1461; d = ((d % 1461) / 4) * 5 + 2; m = d / 153 + 2; d = (d % 153) / 5 + 1; y = y + m / 12 + 1970; m = m % 12 + 1; return list(y, m, d); }
getdays
Die Funktion getdays
kann wie folgt berechnet werden:
function getdays(y, m, d) { return d + ((y - 1970 + (m - 3) / 12) * 1461 + 2) / 4 + (((m - 3) % 12) * 153 + 2) / 5 + 58; }
Optimiert und im prozeduralen Stil sieht die Funktion getdays
so aus:
function getdays(y, m, d) { m = m - 3; d = d + ((y - 1970 + m / 12) * 1461 + 2) / 4; d = d + ((m % 12) * 153 + 2) / 5 + 58; return d; }
In diesem Abschnitt werden die Algorithmen zur Berechnung von Wochen und Wochentagen sowie der Kalenderwoche vorgestellt.
Für die Nummerierung der Wochentage wkday gilt folgende Konvention:
0
1
2
3
4
5
6
Der 1970-01-01
ist bzw. war ein Donnerstag. Eine Woche hat bekanntlich 7
Tage, daher gilt:
days = weeks * 7 + wkday - 3
Daraus folgt:
weeks = (days + 3) / 7 wkday = (days + 3) % 7
Eine Kalenderwoche cw ist die um eins erhöhte Anzahl der Wochen seit der ersten Woche des entsprechenden Jahres. Die erste Woche eines Jahres ist dadurch gekennzeichnet, daß die Mehrzahl der Tage der Woche in diesem Jahr liegt und nicht im vorangegangen Jahr.
Nach der Nummerierungskonvention liegt der Donnerstag (wkday = 3) genau in der Mitte einer Woche. Also bestimmt der Donnerstag einer Woche weeks das Jahr y, zu dem diese Woche gezählt werden muß. Damit gilt:
y = getdate(weeks * 7 + 3 - 3).select(0) = getdate(weeks * 7).select(0)
Die erste Woche week0 eines Jahres y ist die Woche, in der der 4. Januar des entsprechenden Jahres liegt. Denn wenn ein Jahr mit einem Freitag, Samstag oder Sonntag beginnt (wkday > 3), dann muß diese Woche zum vorangegangenen Jahr gezählt werden und deswegen ist erst die folgende Woche die richtige. Die erste Woche schließt aber in allen Fällen den 4. Januar ein, und nur den.
Es ergibt sich also:
week0 = (getdays(y, 1, 4) + 3) / 7 = getdays(y, 1, 7) / 7
Schließlich ergibt sich die gesuchte Kalenderwoche zu:
cw = weeks - week0 + 1 = weeks - getdays(getdate(weeks * 7).select(0), 1, 7) / 7 + 1 = weeks - getdays(getdate(weeks * 7).select(0), 1, 0) / 7
Die Kalenderwoche cw läßt sich auch direkt aus einem vorgegebenen
Wert von weeks auf folgende Weise unter Zuhilfenahme der Definition
der beiden Funktionen getdate
und getdays
berechnen:
w = (weeks * 7 - 59) * 4 + 1 y = w / 1461 + ((((w % 1461) / 4) * 5 + 2) / 153 + 2) / 12 + 1970 cw = weeks - (((y - 1970 + (-2) / 12) * 1461 + 2) / 4 + (((-2) % 12) * 153 + 2) / 5 + 58) / 7 = weeks - ((y - 1970) * 1461 - 1459 + 364 * 4) / 28 = weeks - ((y - 1970) * 1461 - 3) / 28
Aufgrund der Beziehung 365 = 52 * 7 + 1
ergibt sich, daß ein Jahr,
wenn es mit einem Donnerstag anfängt, immer 53 Wochen umfaßt. Fängt ein
Schaltjahr an einem Mittwoch an, so hat es auch 53 Wochen. In allen
anderen Fällen kann ein Jahr nur 52 Wochen haben.
Mit dem Algorithmus von Gauss kann der Termin für den Ostersonntag o
eines vorgegebenen Jahres y, gültig für den Zeitraum von 1900
bis
2099
, wie folgt berechnet werden, wobei o die Anzahl der Tage seit
dem 1970-01-01
angibt:
a = y % 19 b = y % 4 c = y % 7 d = (a * 19 + 24) % 30 e = (b * 2 + c * 4 + d * 6 + 5) % 7 o = getdays(y, 3, 22) + d + e - (e == 6 && (d == 29 || d == 28 && a > 10) ? 7 : 0) = getdays(y, 3, 1) + 21 + d + e - (e == 6 && (d == 29 || d == 28 && a > 10) ? 7 : 0)
Zu zeigen wäre erst einmal, ob das immer ein Sonntag ist! Dazu müßte gelten:
(o + 3) % 7 = 6
Wenn man alle Terme entfernt, die nichts beitragen können, bleibt der folgende Teil übrig, der dann sukzessive vereinfacht werden kann:
(o + 3) % 7 = (getdays(y, 3, 1) + d + e + 3) % 7 = (getdays(y, 3, 1) + d + b * 2 + c * 4 + d * 6 + 5 + 3) % 7 = (getdays(y, 3, 1) + b * 2 + c * 4 + 1) % 7 = (getdays(y, 3, 1) + (y % 4) * 2 + y * 4 + 1) % 7 = (getdays(y, 3, 1) + y * 2 - (y / 4) * 8 + y * 4 + 1) % 7 = (getdays(y, 3, 1) - y - y / 4 + 1) % 7 = ((y - 1968) * 365 + (y - 1968) / 4 - 671 - y - y / 4 + 1) % 7 = (y - 1968 + (y - 1968) / 4 - 670 - y - y / 4) % 7 = (y - 1968 + y / 4 - 492 - 670 - y - y / 4) % 7 = (- 1968 - 492 - 670) % 7 = 6
Was zu zeigen war! Das Resultat kann nun weiterhin dazu benutzt werden,
einen Teil von e durch getdays(y, 3, 1)
auszudrücken, weil dessen
Wert ja sowieso benötigt wird. Es folgt:
(b * 2 + c * 4) % 7 = (5 - getdays(y, 3, 1)) % 7
Und schließlich ergibt sich:
a = y % 19 d = (a * 19 + 24) % 30 e = (3 - getdays(y, 3, 1) - d) % 7 o = getdays(y, 3, 1) + 21 + d + e - (e == 6 && (d == 29 || d == 28 && a > 10) ? 7 : 0)
Oder auch (mit den gleichen Werten für a und d):
e = (3 - getdays(y, 3, 22) - d) % 7 o = getdays(y, 3, 22) + d + e - (e == 6 && (d == 29 || d == 28 && a > 10) ? 7 : 0)
Damit läßt sich weiter ableiten:
e = (3 - getdays(y, 3, 22) - d) % 7 = 6 - (getdays(y, 3, 22) + d - 3 - 1) % 7 = 6 - (getdays(y, 3, 22) + d + 3) % 7
Dies ergibt dann:
getdays(y, 3, 22) + d + e = getdays(y, 3, 22) + d + 6 - (getdays(y, 3, 22) + d + 3) % 7 = 3 + ((getdays(y, 3, 22) + d + 3) / 7) * 7
Daraus ist unmittelbar ersichtlich, daß Ostern immer auf einen Sonntag
fällt. Übrig bleibt jetzt noch die Behandlung des Subtrahenten, der zur
Korrektur in speziellen Fällen dient und der immer entweder 0
oder
7
ist:
e == 6 && (d == 29 || d == 28 && a > 10) ? 7 : 0
Die Auflistung aller möglichen Werte d(a) mit a = 0
..18
ergibt:
24 13 2 21 10 29 18 7 26 15 4 23 12 1 20 9 28 17 6
Die Werte d = 29 und d = 28 kommen tatsächlich jeweils genau einmal vor und d = 28 ergibt sich bei a = 16, also ist a > 10. Damit läßt sich die Korrektur vereinfachen zu:
e == 6 && d >= 28 ? 7 : 0
Nun sollen noch einmal alle Ausdrücke, die zur Berechnung des Ostersonntags benötigt werden, zusammengefaßt dargestellt werden:
d = ((y % 19) * 19 + 24) % 30 f = getdays(y, 3, 22) + d + 3 o = 3 + f - f % 7 - (f % 7 == 0 && d >= 28 ? 7 : 0)
Der Ausdruck in der letzten Zeile läßt sich noch etwas variieren:
o = 3 + f - (f % 7 == 0 ? d >= 28 ? 7 : 0 : f % 7) = 3 + f - (d >= 28 ? (f - 1) % 7 + 1 : f % 7)
Die nützlichste und damit interessanteste Variation überhaupt entsteht,
indem man die beiden Vorkommen von 1
durch d / 28
ersetzt und
damit die Fallunterscheidung eliminiert:
o = 3 + (f - d / 28) - (f - d / 28) % 7 = 3 + ((f - d / 28) / 7) * 7
Und jetzt alles noch einmal zusammengefaßt:
d = ((y % 19) * 19 + 24) % 30 o = ((getdays(y, 3, 22) + d - d / 28 + 3) / 7) * 7 + 3
Unter Ausnutzung der Definition von getdays
ergibt sich
schließlich:
d = ((y % 19) * 19 + 24) % 30 o = ((((y - 1970) * 1461 + 2) / 4 + d - d / 28 + 6) / 7) * 7 + 80
Die folgenden Kalenderdaten lassen sich nun aus dem Ostersonntag ermitteln:
Das konkrete Datum (y, m, d) eines solchen Termins kann dann
letztendlich mit Hilfe der Funktion getdate
berechnet
werden.
Copyright (C) 2004 Alexander Krebs <aleks_at_aksware_dot_de>. Alle Rechte vorbehalten.