Kalender im Kopf (Linux-Magazin, Dezember 2007)

Gehirnakrobaten rechnen gerne vor Publikum aus, auf welchen Wochentag ein zugerufenes Datum fällt. Dies ist keineswegs Hexerei, auch Otto Normalrechner kann dies mit etwas Übung ausführen. Ob das schon im letzten Jahrhundert bekannte Verfahren zur Schnellberechnung auch wirklich stimmt, prüft das heutige Skript mit aktueller Perl-Technologie.

Neulich las ich im Zug zur Arbeit das Buch ``Mind Performance Hacks'' [2] und stieß auf ``Hack'' Nummer 43, der zeigt, wie man mit etwas Übung den Wochentag zu jedem beliebigen Datum im Kopf ausrechnen kann. Das Verfahren geht zurück auf Lewis Carroll, den Autor des Romans ``Alice im Wunderland''. Man berechnet der Reihe nach vier Werte: Den Jahreswert, den Monatswert, den Tageswert und einen vierten Wert zur Anpassung. Man addiert diese Werte anschließend, bestimmt den Restwert nach einer Division durch 7 und erhält verblüffenderweise den gewünschten Wochentag als Zahl zwischen 0 (Sonntag) und 6 (Samstag).

Als Beispiel wird der Wochentag des Entstehungsdatums dieser Kolumne (4.10.2007), ermittelt. Der Jahreswert bestimmt sich aus der Formel

    (YY + (YY div 4)) mod 7

wobei YY die zweistellige Jahreszahl ist, also 07 für 2007. Der div-Operator führt eine Division ohne Restwert aus, 7 div 4 ist 1, da 7 geteilt durch 4 den Wert 1 ergibt und der Rest von 3 wegfällt. Das Ergebnis wird modulo 7 genommen, und 1 modulo 7 ergibt 1. Der Jahreswert ist also 1.

Mnemotechnik

Zum Monatswert: Der ermittelt sich aus Tabelle 1, die man mit einigen später erläuterten mnemotechnischen Tricks im Kopf behalten muss. Der Oktober hat laut Tabelle 1 den Monatswert 0. Der Tageswert ist einfach der Tag des Datums, am 4. Oktober also der Wert 4.

    Tabelle 1:
    0 Januar
    3 Februar
    3 März
    6 April 
    1 Mai
    4 Juni
    6 Juli
    2 August
    5 September
    0 Oktober
    3 November
    5 Dezember

Der vierte Wert für die Kopfrechnung ergibt sich aus Tabelle 2, die für Jahreszahlen im 21. Jahrhundert (2000-2099) den Wert 6 angibt. Die Tabelle braucht man sich nicht ganz zu merken, es genügt, die Werte für 2000 (6) und 1900 (0) im Kopf zu behalten. In Schaltjahren wäre vom gefundenen Wert noch eins abzuziehen, wenn das gesuchte Datum im Januar oder Februar liegt. Da aber 2007 kein Schaltjahr ist, entfällt dies glücklicherweise.

    Tabelle 2:
    1700 4
    1800 2
    1900 0
    2000 6
    2100 4
    2200 2
    2300 0

Die vier gefundenen Werte sind also 1 (Jahreswert), 0 (Monatswert), 4 (Tageswert) und 6 (Anpassung). Addiert man diese auf (Summe 11) und nimmt das Ergebnis modulo 7, ergibt sich der Wert 4. Ein Blick in Tabelle 3 mit den Wochentagen offenbart, dass -- Trommelwirbel -- der 4.10.2007 auf einen Donnerstag fällt, und das ist richtig!

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

Probe aufs Exempel

Jetzt stellt sich natürlich die Frage, ob diese Berechnung auch tatsächlich für jedes beliebige Datum zum richtigen Wochentag führt. Das Skript in Listing mindcal schraubt sich deswegen vom 1.1.1700 an durch sämtliche Tage der Neuzeit, über die Entdeckung Amerikas zum Goldrausch, durch den ersten und den zweiten Weltkrieg, bis in die heutige Zeit und auch noch weiter in die Zukunft, bis zum Raumschiff Enterprise in der nächsten Generation mit Jean-Luc Picard auf dem Kommandosessel im 24. Jahrhundert.

Das Skript definiert in Zeile 29 die Funktion wday_mindcal(), die das vierstellige Jahr, den Monat und den Tag eines Datums entgegennimmt, nach den oben erläuterten Regeln die Jahres/Monats/Tages/Anpassungszahlen errechnet und die notwendigen Operationen ausführt, um die Wochentagsnummer zu ermitteln.

Die Monatszahlen stehen im Array @MONTH, von Januar bis Dezember. Da Arrays nicht von 1 sondern von 0 an durchnumeriert sind, ist vom gesuchten Monat erst 1 abzuziehen, bevor man unter dem so erhaltenen Index in den Array hineingreift. Die Anpassungszahlen für die verschiedenen Jahrhunderte stehen im Hash %ADJ. Die Zeilen 8 und 9 füllen den Hash, in dem sie ihm eine Liste zuweisen, die abwechselnd Jahrhundertzahlen und die jeweils zugehörigen Anpassungswerte enthält.

Die Vergleichswerte errechnet das CPAN-Modul DateTime, das tagweise vom 1.1.1700 bis zum 31.12.2399 hochzählt und bei jedem Schleifendurchgang Tag, Monat und Jahr liefert. Die Endlosschleife ab Zeile 17 ist nicht wirklich endlos, denn Zeile 25 bricht den Reigen ab, falls das Jahr des aktuellen Datums 2399 überschreitet. Ist die Schleife noch nicht am Ende, addiert die Methode add() des DateTime-Objektes unten einen Tag zum aktuellen Datum und eine weitere Schleifenrunde nimmt ihren Anfang.

CPAN zum Vergleich

DateTime verfügt natürlich ebenfalls über eine Wochentagsfunktion wday(), die allerdings die Tage von 1 (Montag) bis 7 (Sonntag) durchnumeriert. mindcal hängt also noch schnell eine Modulo-7-Operation an, damit aus der Sonntag-7 eine 0 wird und man die Ergebnisse einfach mit den von wday_mindcal() gelieferten Werten von 0 (Sonntag) bis 6 (Samstag) vergleichen kann.

Die restlose Division div implementiert das Skript einfach durch das in Zeile 33 aktivierte Pragma use integer. Ist dieser Modus gesetzt, rechnet Perl nicht mehr mit Fließkommazahlen sondern runden Integern, sodass 17/4 zum Beispiel eine glatte 4 ergibt.

Ob ein Jahr ein Schaltjahr ist, ermittelt die Funktion leap_year() ab Zeile 51. Ist es durch 4 teilbar, ist es ein Schaltjahr, es sei denn, es ist durch 100 teilbar. Ist es durch 400 teilbar ist es wiederum ein Schaltjahr. Diese Logik ist natürlich auch in DateTime enthalten, aber schließlich soll das Skript den Kopfrechner simulieren.

Die Vergleiche führt die vom CPAN-Modul Test::More exportierte Funktion is() aus. Sie nimmt drei Parameter entgegen, den Ist-Wert des Kopfrechners in mindcal, den Sollwert von DateTime und einen Kommentar, der aus einem stringifizierten und damit lesbaren DateTime-Objekt besteht. Mit no_plan hinter der use-Anweisung von Test::More stellt das Skript klar, dass die Anzahl der auszuführenden Tests unbekannt ist. Abbildung 1 zeigt die Ausgabe von mindcal. Da niemand Lust hat, sich 250.000 vorbeirasende Ausgaben anzusehen, fasst das Modul Test::Harness die Ergebnisse einer solchen Testsuite übersichtlich zusammen. Der Aufruf

    perl -MTest::Harness -e'runtests("mindcal")'

lässt das Skript mindcal ablaufen und gibt genau acht, welche Tests ok liefern und welche not ok. Am Ende erscheint eine schöne Zusammenfassung, wie in Abbildung 2 gezeigt. Dem aufmerksamen Leser wird nicht entgangen sein, dass der Kommandozeilenaufruf in Abbildung 2 etwas anders als oben gezeigt ist. Test::Harness hat die unangenehme Marotte, bei mehr als 100.000 Tests auf STDERR herumzunörgeln, und der in Abbildung 2 gezeigte Aufruf lasst diese Meldungen über den __WARN__-Signalhandler in ein schwarzes Loch sausen. Ergebnis: Der alte Fuchs Lewis Carroll hatte tatsächlich recht, alle 255.669 Tests laufen fehlerlos durch.

Abbildung 1: Test::More druckt die Ergebnisse der Einzeltests.

Abbildung 2: Test::Harness fasst die Ergebnisse zusammen.

Mnemonische Tricks

Hier noch eine Gedächtnishilfe zum leichteren Einprägen der Monatszahlen. Von Januar bis Dezember ergeben sie aneinandergereiht 033614625035. Diese Monsterzahl merke ich mir in Dreiergruppen: 033-614-625-035 und folgendem Spruch: ``Nach der Einleitung mit 033 kommt 614, ähnlich wie die Kreiszahl 3.14, nur eben mit 6 am Anfang, weil vorher schon zweimal 3 dran war. Das folgende 625 fängt ebenfalls mit 6 an und ist 25**2, also die Fläche eines Quadrats! Das ist doch eine schöne Abwechslung zum vorhergehenden Kreis. Und am Ende steht 035, zwei mehr als die Einleitung mit 033.''

Die Dreiergruppen stelle ich mir optisch vor und kann deswegen für Juli zum Beispiel schnell an den Anfang der zweiten Jahreshälfte springen, wo die dem Juli zugeordnete Monatszahl 6 steht.

Üben, üben, üben

Die Ermittlung der Jahreszahl kann sich besonders bei den letzten Jahren des letzten Jahrhunderts etwas in die Länge ziehen. Zum Beispiel 1995: 95 geteilt durch 4 ist 23 plus ein paar Zerquetschte, die unter den Tisch fallen. 95 plus 23 ist dann 118, Modulo 7 ist das 6. Klappt das mit dem Kopfrechnen noch nicht so schnell, kann man sich zum Üben darauf beschränken, nur Datumsangaben in einem bestimmten (oder dem aktuellen) Jahr vom Publikum zuzulassen. Dann rechnet man die Jahreszahl im voraus aus und merkt sie sich. Für 2007 ist sie 1.

Tabelle 4 zeigt noch einige Rechenbeispiele zum Üben. Zu beachten ist, dass 2004 ein Schaltjahr ist, was bei einem Datum im Januar/Februar zu einem Punktabzug bei der Anpassung führt, bei anderen Monaten jedoch nicht.

    Tabelle 4:
    Datum       Jahreszahl Monatszahl Tageszahl Anpassung Wochentag
    01.01.1970  3          0           1        0         4 (Donnerstag)
    14.07.1995  6          6          14        0         5 (Freitag)
    11.09.2001  1          5          11        6         2 (Dienstag)
    01.02.2004  5          3           1        5         0 (Sonntag)
    01.03.2004  5          3           1        6         1 (Montag)
    04.10.2007  1          0           4        6         4 (Donnerstag)

Wer den Bogen raus hat, kann seine Rechenkünste einem bass erstaunten Publikum vorführen. Zunächst im kleinen Kreis bei Freunden, dann bei Parties und schließlich in ausverkauften Sporthallen!

Listing 1: mindcal

    01 #!/usr/bin/perl
    02 use strict;
    03 use warnings;
    04 use Test::More qw(no_plan);
    05 use DateTime;
    06 
    07 my @MONTH = qw(0 3 3 6 1 4 6 2 5 0 3 5);
    08 my %ADJ   = qw(1700 4 1800 2 1900 0 2000 6 
    09                2100 4 2200 2 2300 0);
    10 
    11 my $dt = DateTime->new(
    12     year  => 1700,
    13     month => 1,
    14     day   => 1,
    15 );
    16 
    17 while(1) {
    18   my $calc = wday_mindcal(
    19          $dt->year, $dt->month, $dt->day);
    20 
    21   is($calc, $dt->wday() % 7, "$dt");
    22 
    23   $dt->add(days => 1);
    24 
    25   last if $dt->year() > 2399;
    26 }
    27 
    28 ###########################################
    29 sub wday_mindcal {
    30 ###########################################
    31     my($year, $month, $day) = @_;
    32 
    33     use integer;
    34 
    35     my $year2 = $year % 100;
    36     my $cent  = $year / 100;
    37     my $y     = ($year2 + ($year2 / 4)) % 7;
    38 
    39     my $m     = $MONTH[$month-1];
    40     my $d     = $day;
    41 
    42     my $adj   = $ADJ{$cent * 100};
    43 
    44     $adj-- if leap_year($year) and
    45               $month <= 2;
    46 
    47     return( ($y+$m+$d+$adj) % 7 );
    48 }
    49 
    50 ###########################################
    51 sub leap_year {
    52 ###########################################
    53     my($year) = @_;
    54 
    55     return 0 if $year % 4;
    56     return 1 if $year % 100;
    57     return 0 if $year % 400;
    58     return 1;
    59 }

Infos

[1]
Listings zu diesem Artikel: ftp://www.linux-magazin.de/pub/listings/magazin/2007/12/Perl

[2]
``Mind Performance Hacks'', Ron Hale-Evans, 2007, O'Reilly

[3]
``Lewis Carroll's Algorithm for finding the day of the week for any given date'', http://www.cs.usyd.edu.au/~key/pp/TUTORIALS/1b/carroll.txt

Michael Schilli

arbeitet als Software-Engineer bei Yahoo! in Sunnyvale, Kalifornien. Er hat "Goto Perl 5" (deutsch) und "Perl Power" (englisch) für Addison-Wesley geschrieben und ist unter mschilli@perlmeister.com zu erreichen. Seine Homepage: http://perlmeister.com.