Berechnung von Kalenderdaten

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.

Inhaltsverzeichnis

Letzte Änderung: 15. November 2004


1. Vorbemerkungen zur ganzzahligen Division

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.

1.1 Die richtigen Operatoren

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.

1.2 Korrektur der falschen Operatoren

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:

  1. q > 0 und p >= 0

    div(p, q) = udiv(p, q)
    mod(p, q) = umod(p, q)
    
  2. q > 0 und p < 0

    div(p, q) = -udiv(-p - 1, q) - 1
    mod(p, q) = -umod(-p - 1, q) - 1 + q
    
  3. 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.

1.3 Weitere Regeln

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.


2. Allgemeine Definitionen

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
Jahr, meistens im Bereich 1900-2100
m
Monat im Jahr, 1-basiert im Bereich 1-12
d
Tag im Monat, 1-basiert im Bereich 1-31 (je nach Monat)
cw
Kalenderwoche, 1-basiert im Bereich 1-53 (je nach Jahr)
days
Anzahl der Tage seit dem 1970-01-01
weeks
Anzahl der Wochen seit der Woche, in der der 1970-01-01 liegt
wkday
Wochentag, siehe Wochentagsdefinition

3. Grundlegende Funktionen

In diesem Abschnitt werden die grundlegenden Funktionen zur Berechnung von days und von y, m und d vorgestellt.

getdays(y, m, d)
Berechnet die Anzahl der Tage days seit dem 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)
Berechnet das Jahr y, den Monat m und den Tag d, ausgehend von der Anzahl der Tage days seit dem 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

3.1 Berechnungsgrundlagen

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

3.1.1 Jahreszahl

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

3.1.2 Monat im Jahr

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

3.1.3 Tag im Monat

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.

3.2 Funktion 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);
}

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

4. Wochen und Wochentage

In diesem Abschnitt werden die Algorithmen zur Berechnung von Wochen und Wochentagen sowie der Kalenderwoche vorgestellt.

4.1 Wochentagsdefinition

Für die Nummerierung der Wochentage wkday gilt folgende Konvention:

0
Montag
1
Dienstag
2
Mittwoch
3
Donnerstag
4
Freitag
5
Samstag
6
Sonntag

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

4.2 Kalenderwoche

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

4.3 Anmerkung zur Wochenanzahl

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.


5. Berechnung des Ostersonntags

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:

o-46
Aschermittwoch
o+00
Ostersonntag
o+39
Christi Himmelfahrt (Donnerstag)
o+49
Pfingstsonntag
o+60
Fronleichnam (Donnerstag)

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.