Date arithmetic and Zune bug
Terje Mathisen
hung on Dec 31st, due to not being able to handle day number 366 of a
leap year, and started thinking about some discussions we've had here
over the years about the fastests/tightest/most elegant ways to convert
between year-month-day and day number.
The code I wrote to handle this problem was written in Jan 2000, then we
had another discussion in 2005, at which time one of the IBM regulars
(probably Hack?) pointed me at an IBM report which used very similar ideas.
Anyway, my code from 2005 uses about 10-15 regular instructions, plus
two unsigned multiplications, to do ymd2days, so about 10-20 clock cycles:
/* #define USE_UNSIGNED_MASK */
#ifdef USE_UNSIGNED_SHIFT
typedef unsigned mask_t;
# define INC_IF_MASK(x,mask) ((x) += (mask) & 1)
# define DEC_IF_MASK(x,mask) ((x) -= (mask) & 1)
#else
typedef int mask_t;
# define INC_IF_MASK(x,mask) ((x) -= (mask))
# define DEC_IF_MASK(x,mask) ((x) += (mask))
#endif
/* These operations are valid for any date after 1584,
* according to the Gregorian (modern) calendar
*/
#define STARTYEAR 1200 /* Must be divisible by 400! */
/* Table to simplify conversions between mm-dd and day_in_year */
static short daysToMonth[13] =
{-1,30,60,91,121,152,183,213,244,274,305,336,366};
unsigned ymd2days(unsigned y, unsigned m, unsigned d)
{
unsigned days, y100;
/* Start by setting March = month zero: */
mask_t mask = (mask_t) (m -= 3);
/* Mask will now be in the (mask_t) -2 to 9 range, a shift by 4 is
enough to make it -1 or 0: */
mask >>= 4;
DEC_IF_MASK(y, mask); /* Decrement year if jan/feb */
m += (mask & 12); /* and increment the month: The
year starts in March! */
y -= STARTYEAR;
y100 = y / 100; /* Centuries for leap year calc */
days = y * 365 + (y >> 2) - y100 + (y100 >> 2);
days += (unsigned) daysToMonth[m] + d;
return days;
}
The reverse conversion is the fun one: It turns out that the fastest
method is to guess the year, then correct it if off by one. :-)
The code below will work on any platform which provides unsigned
integers with at least 29 bits of precision, but it will be slightly
faster with 30+ bit twos-complement signed ints.
void days2ymd(unsigned days, unsigned *yy, unsigned *mm, unsigned *dd)
{
unsigned y400, y100, y, m, d, gd;
mask_t mask;
/* Start by subtracting any full 400-year cycles: */
y400 = days / 146097;
days -= y400 * 146097;
#if 0
/* Very good approximation to the number of years, will be wrong
* (too high) 257 times
* in a 400-year cycle, i.e. in 0.18% of all calls.
*/
/* A good compiler will replace this with a scaled reciprocal MUL! */
y = (days + 1) * 400 / 146096;
#else
/* Useful and faster approximation to the number of years, will be
* wrong (too high) 910 times
* in a 400-year cycle, i.e. in 0.62% of all calls.
*
* Requires unsigned values with up to 29 significant bits!
*/
y = (days * 2871 + 1983) >> 20;
/* y = (days * 22967 + 59235) >> 23; */
/* peter (at) horizon.com suggested this! */
#endif
/* Calculate # of centuries:
* Since y will be in the 0 to 400 range, the following
* approximation can be used instead of a division by 100:
* y100 = y / 100; ~ (y * 41) >> 12;
*/
y100 = (y * 41) >> 12;
/* # of days in those full years */
gd = y * 365 /* Normal years */
+ (y >> 2) /* + leap years every 4 years */
- y100 /* - missing century leap years */
+ (y100 >> 2); /* + every 400 years */
/* test for the small chance of a wrong year: */
if (gd > days) {
y--; /* y will be in the [0-399] range! */
y100 = (y * 41) >> 12;
/* The 400-year correction can be skipped! */
gd = y * 365 + (y >> 2) - y100 /* + (y100 >> 2) */;
}
/* Calculate the offset into the current year: */
days -= gd;
/* Correct for starting date and 400-year cycles: */
y += STARTYEAR + y400 * 400;
#if 1
/* Make a FAST guess at the current month, can be too low: */
m = days >> 5;
mask = (mask_t) daysToMonth[m+1] - (mask_t) days;
/* mask will be in the -18 to 18 range, use shift by 5: */
mask >>= 5;
/* If the guess was wrong then the mask will be -1, otherwise 0: */
/* Increment month if needed */
INC_IF_MASK(m, mask);
/* The remainder is the day of the month */
d = days - (unsigned) daysToMonth[m];
/* Correct for the March 1 starting point: */
mask = (mask_t) (9 - m) >> 4;
m += 3;
INC_IF_MASK(y, mask);
m -= (unsigned) (mask & 12);
#else
/* Based on code from an IBM report: Slightly slower, but
* uses no table lookups!
*/
m = ((days + 31) * 1071);
d = (((m & 0x7fff) * 62669) >> 26) + 1;
m >>= 15;
mask = (mask_t) (10 - m) >> 4;
m += 2;
INC_IF_MASK(y, mask);
m -= (unsigned) (mask & 12);
#endif
*yy = y; *mm = m; *dd = d;
}
This second function uses four integer multiplications, one of them is a
reciprocal to avoid division, the rest are all shifts/adds/subs etc.
Running time is on the order of 30-70 cycles, depending upon the speed
of integer muls.
Terje
--
- <Terje.M...@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"
Rob Warnock
+---------------
| I read with disbelief about how most of Microsoft's 30 GB Zune players
| hung on Dec 31st, due to not being able to handle day number 366 of a
+---------------
It's worse that you think. ;-} ;-} See the latest issue of RISKS
for the actual failing code:
http://catless.ncl.ac.uk/Risks/25.50.html#subj2.2
Zounds! Zinger: Zune Zapped Zealously with Zero-tolerance
David Magda <dma...@ee.ryerson.ca>
Thu, 1 Jan 2009 15:26:18 -0500
...
The issue is an infinite loop:
> while (days > 365) {
> if (IsLeapYear(year)) {
> if (days > 366) {
> days -= 366;
> year += 1;
> }
> } else {
> days -= 365;
> year += 1;
> }
> }
...
http://www.zuneboards.com/forums/349447-post1.html
I suspect it was trying to do something like this, only it missed:
while (days > (IsLeapYear(year) ? 366 : 365)) {
days -= (IsLeapYear(year) ? 366 : 365);
year += 1;
}
-Rob
p.s. Yes, I know, "IsLeapYear()" is probably expensive, so the
speed demons among us will probably want to rewrite it like this: ;-}
while (days > (year_length = (IsLeapYear(year) ? 366 : 365))) {
days -= year_length;
year += 1;
}
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Terje Mathisen
> Terje Mathisen <terje.m...@hda.hydro.com> wrote:
> +---------------
> | I read with disbelief about how most of Microsoft's 30 GB Zune players
> | hung on Dec 31st, due to not being able to handle day number 366 of a
> | leap year...
> +---------------
>
> It's worse that you think. ;-} ;-} See the latest issue of RISKS
No, it isn't.
> for the actual failing code:
I first found a link to the full driver code, and knowing there was a
date bug, it took me less than a minute to locate the error below.
> The issue is an infinite loop:
>
> > while (days > 365) {
> > if (IsLeapYear(year)) {
> > if (days > 366) {
> > days -= 366;
> > year += 1;
> > }
> > } else {
> > days -= 365;
> > year += 1;
> > }
> > }
> p.s. Yes, I know, "IsLeapYear()" is probably expensive, so the
> speed demons among us will probably want to rewrite it like this: ;-}
>
> while (days > (year_length = (IsLeapYear(year) ? 366 : 365))) {
> days -= year_length;
> year += 1;
> }
The point is that the fully correct version, that handles all possible
dates until we run out of bits in integers, runs _faster_ than even the
rewritten version, since the loop has to iterate at least 28 times!
I just reran a benchmark of the functions I posted: Doing the
conversions both forwards and back, plus a post-conversion check that
all generated dates are legal, and that the input date was equal to the
output:
It took about 42 ns/iteration on my laptop, which means about 90 clock
cycles, of which maximum 70 can have been used for the days2ymd() call.
28++ iterations of a loop which includes an inline IsLeapYear() call has
to take significantly more time!
Paul Gotch
> I read with disbelief about how most of Microsoft's 30 GB Zune players
> hung on Dec 31st
It should be noted that this appears to be a bug in some versions of
the Freescale iMX31 Board Support Package for Windows CE. Obviously
from the consumer's point of view it make little difference if it is
MS's or Freescale's bug.
-p
--
"Unix is user friendly, it's just picky about who its friends are."
- Anonymous
--------------------------------------------------------------------
Ken Hagan
<terje.m...@hda.hydro.com> wrote:
> I read with disbelief about how most of Microsoft's 30 GB Zune players
> hung on Dec 31st, due to not being able to handle day number 366 of a
> leap year
Disbelief? You jest, sir. Leap year problems are easy to pose but the
historical evidence is that both programmers and QA testers find them
almost impossible to handle. My impression is that far more software
failed on 29:Feb:2000 than did 8 weeks previously, which is quite
stunning when you consider that the requirement here was for a no-op.
Anne & Lynn Wheeler
> Disbelief? You jest, sir. Leap year problems are easy to pose but the
> historical evidence is that both programmers and QA testers find them
> almost impossible to handle. My impression is that far more software
> failed on 29:Feb:2000 than did 8 weeks previously, which is quite
> stunning when you consider that the requirement here was for a no-op.
there was y2k discussion thread in the early 80s (talking about the
impending century problem) ... and there were instances of other kinds
of failures in processing dates ... frequent failures involve leap yrs;
one of the entries extracted here (including problem in airline
reservation system that happened on 29feb72 and a problem in how dates
are handled for shuttle missions):
http://www.garlic.com/~lynn/99.html#email841207
in these old threads:
http://www.garlic.com/~lynn/99.html#24 BA Solves Y2K (Was: Re: Chinese Solve Y2K)
http://www.garlic.com/~lynn/99.html#233 Computer of the century
--
40+yrs virtualization experience (since Jan68), online at home since Mar70
Gavin Scott
> Disbelief? You jest, sir. Leap year problems are easy to pose but the
> historical evidence is that both programmers and QA testers find them
> almost impossible to handle.
Of course date-sensitive bugs are the worst sort, since they're
generally impossible to detect through testing unless you test at
exactly the right time, and worse, they tend to strike your entire
customer base on the same day, often with very little warning (one
learns to pay more attention to calls from New Zealand).
I wonder how many products now have, as part of their QA, a machine
running with a clock set some time in the future, say 1-3 months
ahead, for the express purpose of finding this sort of thing.
A related class of bugs that's also hard to test for are the "system
fails after being up for exactly N days", but these at least have a
simple temporary workaround and don't strike everyone at once.
G.
Andrew Reilly
> I read with disbelief about how most of Microsoft's 30 GB Zune players
> hung on Dec 31st, due to not being able to handle day number 366 of a
> leap year, and started thinking about some discussions we've had here
> over the years about the fastests/tightest/most elegant ways to convert
> between year-month-day and day number.
The thing that I find curious about these sorts of incident is what
business of devices like the Zune is the date, anyway? I suppose that
they have some kind of convenience clock function, like my iPod, but I'm
sure most users wouldn't care if they just didn't.
There were lots of industrial/control/embedded devices that were held up
as potential y2k catastrophe initiators, back then, that had no business
knowing what the date was, IMO. None of the audio gear that I've built
ever did, except for that one that was sitting inside an industrial
Windows PC. I suppose the Zune is a bit like that...
Cheers,
--
Andrew
Rob Warnock
| > p.s. Yes, I know, "IsLeapYear()" is probably expensive, so the
| > speed demons among us will probably want to rewrite it like this: ;-}
| >
| > while (days > (year_length = (IsLeapYear(year) ? 366 : 365))) {
| > days -= year_length;
| > year += 1;
| > }
|
| The point is that the fully correct version, that handles all possible
| dates until we run out of bits in integers, runs _faster_ than even the
| rewritten version, since the loop has to iterate at least 28 times!
Yes, of course. For the record, I was *not* arguing with your
fully correct version or its performance, only noting that even a
minimally-correct [though obviously slow] version is (1) one-third
the size of the broken one, (2) slightly faster, (3) *much* easier
both to write and to read later, and (4) trivial. To say it another
way, "What *WERE* they thinking?!?" [Ans: Probably weren't.]
+---------------
| I just reran a benchmark of the functions I posted: ...
| It took about 42 ns/iteration on my laptop, which means about 90 clock
| cycles, of which maximum 70 can have been used for the days2ymd() call.
+---------------
Neat!
-Rob
Anne & Lynn Wheeler
re:
http://www.garlic.com/~lynn/2009.html#16 Date arithmetic and Zune bug
for a little other topic drift (leap "seconds" rather than "year"):
'Leap Second' Snafu Affects Oracle Clusterware
http://www.pcworld.com/article/156453/leap_second_snafu_affects_oracle_clusterware.html
back circa 1970 ... i spent 3months with a number of other people
discussing what to do about "leap seconds" (that and what does the
"start of the century" mean ... i.e. did the century start in 1900 or
1901?) ... this was for the 370 TOD clock.
H. Peter Anvin
> I read with disbelief about how most of Microsoft's 30 GB Zune players
> hung on Dec 31st, due to not being able to handle day number 366 of a
> leap year, and started thinking about some discussions we've had here
> over the years about the fastests/tightest/most elegant ways to convert
> between year-month-day and day number.
>
> The code I wrote to handle this problem was written in Jan 2000, then we
> had another discussion in 2005, at which time one of the IBM regulars
> (probably Hack?) pointed me at an IBM report which used very similar ideas.
>
> Anyway, my code from 2005 uses about 10-15 regular instructions, plus
> two unsigned multiplications, to do ymd2days, so about 10-20 clock cycles:
[... code ...]
Yes, a good hint one is doing it wrong is when you spot a loop in date
code. It's just plain broken.
> This second function uses four integer multiplications, one of them is a
> reciprocal to avoid division, the rest are all shifts/adds/subs etc.
This is, of course, good if you have to do a *lot* of these conversions
(or you're writing a library, in which case you have to assume so), but
otherwise I'd suggest leaving the divisions in to make the code more
understandable to lower-level programmers.
One important bit about anything dealing with Gregorian dates is the
observation Christian Zeller did well over a century ago: the math gets
a lot cleaner if you treat January and February as months 13 and 14 of
(year-1). March was, in fact, historically the first month, as
evidenced by our names for months 9 to 12: "September" ("seventh month")
to "December" ("tenth month")...
-hpa
Ken Hagan
> ... March was, in fact, historically the first month, as
> evidenced by our names for months 9 to 12: "September" ("seventh month")
> to "December" ("tenth month")...
...and by the fact that the leap day was originally placed at the very
end of the year (where any sane person would put it) but wasn't moved
to December in the Gregorian reform, presumably for reasons of backwards
compatibility. :)
Rob Warnock
| One important bit about anything dealing with Gregorian dates is the
| observation Christian Zeller did well over a century ago: the math gets
| a lot cleaner if you treat January and February as months 13 and 14 of
| (year-1). March was, in fact, historically the first month, as
| evidenced by our names for months 9 to 12: "September" ("seventh month")
| to "December" ("tenth month")...
Eric Naggum's classic paper on the subject [known mostly among the Lisp
community, but applicable & readily accessible to a general audience]:
http://naggum.no/lugm-time.html
The Long, Painful History of Time
Erik Naggum, Naggum Software
Oslo, Norway
1999-10-11
suggests doing something very similar:
...
The Roman tradition of starting the year in the month of March
has also been lost. Most agrarian societies were far more
interested in the onset of spring than in the winter solstice,
even though various deities were naturally celebrated when the
sun returned. ...but Julius Caesar decided to move the Roman
calendar back two months... far more important was the decision
to retain the leap day in February. In the old calendar, the
leap day was added at the end of the year, as makes perfect
sense, when the month was already short, but now it is squeezed
into the middle of the first quarter, complicating all sorts of
calculations, and affecting how much people work. In the old
days, the leap day was used as an extra day for the various
fertility festivities.
[If one starts the year on March 1st] the simplicity of the scheme
is quite amazing: a 400-year cycle not only starts 2000-03-01
(as it did 1600-03-01), it contains an even number of weeks: 20,871.
This means that we can make do with a single 400-year calculation
for all time within the Gregorian calendar with respect to days of
week, leap days, etc.
...
The LOCAL-TIME Concept
...
Because we are [in 1999] very close to the beginning of the next
400-year leap-year cycle, thanks to Pope Gregory, day 0 is defined
to be 2000-03-01, which much less arbitrary than other systems,
but not obviously so. Each 400-year cycle contains 146,097 days,
so an arbitrary decision was made to limit the day to a maximal
negative value of -146,097, or 1600-03-01. This can be changed
at the peril of accurately representing days that do not belong
to the calendar used at the time.
...
[Because bignum arithmetic is expensive] The LOCAL-TIME concept
therefore represents time as three disjoint fixnums [relatively
small tagged integers that consume only one machine word, including
a few bits of type tag]:
1. the number of days since (or until, when negative) 2000-03-01
2. the number of seconds since the start of the day in
Coordinated Universal Time
3. the number of milliseconds since the start of the second.
All numbers have origin 0. Only the number of days may be negative.
...[more details about why this makes sense, how conversions and
date/time calculations (including intervals) are done in the system]...
Note: Even if you don't care for his proposed system, the paper is
a delightful tour of calendric history which touches on the influences
of geography, politics, science, and general historical randomness. ;-}
nm...@cam.ac.uk
Rob Warnock <rp...@rpw3.org> wrote:
>
>Eric Naggum's classic paper on the subject [known mostly among the Lisp
>community, but applicable & readily accessible to a general audience]:
>
>
> has also been lost. Most agrarian societies were far more
> interested in the onset of spring than in the winter solstice,
> even though various deities were naturally celebrated when the
> sun returned. ...
Well, he may address the point, but that statement is grossly
misleading in isolation.
The reason that the winter solstice was the primary seasonal
festival, has survived Christianity more-or-less unchanged and is
much more important (even today) in northern Europe than elsewhere
is FAR more likely to be due to how close we live to the Arctic
circle. All of the other agrarian societies came from closer to
the equator, often much closer.
I am pretty surprised that a Norwegian missed that aspect!
Regards,
Nick Maclaren.
Muzaffer Kal
> [If one starts the year on March 1st] the simplicity of the scheme
> is quite amazing: a 400-year cycle not only starts 2000-03-01
> (as it did 1600-03-01), it contains an even number of weeks: 20,871.
Is 20,871 supposed to be the number of weeks? If so, I'm not sure if
the latter portion of the above statement is correct.
Muzaffer Kal
DSPIA INC.
ASIC/FPGA Design Services
http://www.dspia.com
Terje Mathisen
> Terje Mathisen wrote:
>> I read with disbelief about how most of Microsoft's 30 GB Zune players
>> hung on Dec 31st, due to not being able to handle day number 366 of a
>> leap year, and started thinking about some discussions we've had here
>> over the years about the fastests/tightest/most elegant ways to convert
>> between year-month-day and day number.
>>
>> The code I wrote to handle this problem was written in Jan 2000, then we
>> had another discussion in 2005, at which time one of the IBM regulars
>> (probably Hack?) pointed me at an IBM report which used very similar
ideas.
>>
>> Anyway, my code from 2005 uses about 10-15 regular instructions, plus
>> two unsigned multiplications, to do ymd2days, so about 10-20 clock
cycles:
>
> [... code ...]
>
> Yes, a good hint one is doing it wrong is when you spot a loop in date
> code. It's just plain broken.
>
>> This second function uses four integer multiplications, one of them is a
>> reciprocal to avoid division, the rest are all shifts/adds/subs etc.
>
> This is, of course, good if you have to do a *lot* of these conversions
> (or you're writing a library, in which case you have to assume so), but
> otherwise I'd suggest leaving the divisions in to make the code more
> understandable to lower-level programmers.
Sorry: It is written as a constant division, but I have verified (by
code inspection) that pretty much all modern compilers, for x86, Power,
Sparc, Alpha, ARM will convert that into a reciprocal division.
>
> One important bit about anything dealing with Gregorian dates is the
> observation Christian Zeller did well over a century ago: the math gets
> a lot cleaner if you treat January and February as months 13 and 14 of
> (year-1). March was, in fact, historically the first month, as
> evidenced by our names for months 9 to 12: "September" ("seventh month")
> to "December" ("tenth month")...
<BG>
My STARTDATE is #define'd as March 1st, 1200 (or any other year
divisible by 400).
I number the months from 0 to 11 starting with March, then correct at
the end. Here's the conversion logic:
/* Correct for the March 1 starting point: */
mask = (mask_t) (9 - m) >> 4; // -1 if (m == 10 || m == 11)
m += 3;
INC_IF_MASK(y, mask);
m -= (unsigned) (mask & 12);
Terje
Terje Mathisen
> The reason that the winter solstice was the primary seasonal
> festival, has survived Christianity more-or-less unchanged and is
> much more important (even today) in northern Europe than elsewhere
> is FAR more likely to be due to how close we live to the Arctic
> circle. All of the other agrarian societies came from closer to
> the equator, often much closer.
>
> I am pretty surprised that a Norwegian missed that aspect!
I don't think he missed it that badly, it is common knowledge that after
Olaf Trygvasson (later St Olaf) converted the country from the old Norse
gods to Christianity, the new priests simply subsumed the old Juleblot,
celebrated around winter solstice, into the Christmas celebration.
Here in Norway (as well as the rest of Scandinavia afaik) we still call
it 'Jul' and 'Julefeiring (Jul celebration)', and the days are named
Julaften (Jul evening) for the 24th, then 1 and 2 Juledag (1st and 2nd
day of Jul), going all the way till either the 13th or 20th day of Jul
when the festivities are officially over.
Jesus' birth, Christianity etc isn't mentioned at all in the naming of
the period.
Terje Mathisen
> On Wed, 07 Jan 2009 06:10:03 -0600, rp...@rpw3.org (Rob Warnock) wrote:
>> [If one starts the year on March 1st] the simplicity of the scheme
>> is quite amazing: a 400-year cycle not only starts 2000-03-01
>> (as it did 1600-03-01), it contains an even number of weeks: 20,871.
>
> Is 20,871 supposed to be the number of weeks? If so, I'm not sure if
> the latter portion of the above statement is correct.
146097 : 7 = 20871, so this is correct.
It does mean that you can discard the number of initial 400-year cycles
when using the day number to calculate the day of week.
OTOH, I much prefer to put the zero point at 1200-03-01, or even
earlier, since this means that all Gregorian dates will have a positive
day number, something which makes the conversion algorithms more easily
portable across all cpu architectures, including those without two's
complement integer arithmetic.
nm...@cam.ac.uk
Terje Mathisen <terje.m...@hda.hydro.com> wrote:
>nm...@cam.ac.uk wrote:
>> The reason that the winter solstice was the primary seasonal
>> festival, has survived Christianity more-or-less unchanged and is
>> much more important (even today) in northern Europe than elsewhere
>> is FAR more likely to be due to how close we live to the Arctic
>> circle. All of the other agrarian societies came from closer to
>> the equator, often much closer.
>>
>> I am pretty surprised that a Norwegian missed that aspect!
>
>I don't think he missed it that badly, it is common knowledge that after
>Olaf Trygvasson (later St Olaf) converted the country from the old Norse
>gods to Christianity, the new priests simply subsumed the old Juleblot,
>celebrated around winter solstice, into the Christmas celebration.
Yes, of course, but I was referring to the relative importance of
the winter solstice and 'spring' - specifically with respect to
when the year starts.
Where we live, the feeling "Thank God, at least the days are getting
longer" is dominant, and must have been more so in the days of
candles. In places closer to the equator, the gloom of winter is
FAR less marked, and consequentially the solstice is less important.
Regards,
Nick Maclaren.
Kai Harrekilde-Petersen
> nm...@cam.ac.uk wrote:
>> The reason that the winter solstice was the primary seasonal
>> festival, has survived Christianity more-or-less unchanged and is
>> much more important (even today) in northern Europe than elsewhere
>> is FAR more likely to be due to how close we live to the Arctic
>> circle. All of the other agrarian societies came from closer to
>> the equator, often much closer.
>>
>> I am pretty surprised that a Norwegian missed that aspect!
>
> I don't think he missed it that badly, it is common knowledge that
> after Olaf Trygvasson (later St Olaf) converted the country from the
> old Norse gods to Christianity, the new priests simply subsumed the
> old Juleblot, celebrated around winter solstice, into the Christmas
> celebration.
>
> Here in Norway (as well as the rest of Scandinavia afaik) we still
> call it 'Jul' and 'Julefeiring (Jul celebration)', and the days are
> named Julaften (Jul evening) for the 24th, then 1 and 2 Juledag (1st
> and 2nd day of Jul), going all the way till either the 13th or 20th
> day of Jul when the festivities are officially over.
Yup (although spelling varies slightly). Even the english have
'Yuletide' - adapted from the Danish vikings ;-)
Kai
--
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>
Joe Pfeiffer
> Muzaffer Kal wrote:
>> On Wed, 07 Jan 2009 06:10:03 -0600, rp...@rpw3.org (Rob Warnock) wrote:
>>> [If one starts the year on March 1st] the simplicity of the scheme
>>> is quite amazing: a 400-year cycle not only starts 2000-03-01
>>> (as it did 1600-03-01), it contains an even number of weeks: 20,871.
>>
>> Is 20,871 supposed to be the number of weeks? If so, I'm not sure if
>> the latter portion of the above statement is correct.
>
> 146097 : 7 = 20871, so this is correct.
>
> It does mean that you can discard the number of initial 400-year
> cycles when using the day number to calculate the day of week.
Though I believe that makes it an integral number of weeks, not an
even number.
Kai Harrekilde-Petersen
> Where we live, the feeling "Thank God, at least the days are getting
> longer" is dominant, and must have been more so in the days of
> candles. In places closer to the equator, the gloom of winter is
> FAR less marked, and consequentially the solstice is less important.
And you near live Cambridge? =8-|
Its' quite marked how just the ~500km from Copenhagen to Oslo and
again Oslo - Trondheim changes the amount of daylight both in the
winter and the summer.
nm...@cam.ac.uk
Kai Harrekilde-Petersen <k...@harrekilde.dk> wrote:
>Terje Mathisen <terje.m...@hda.hydro.com> writes:
>>
>>> The reason that the winter solstice was the primary seasonal
>>> festival, has survived Christianity more-or-less unchanged and is
>>> much more important (even today) in northern Europe than elsewhere
>>> is FAR more likely to be due to how close we live to the Arctic
>>> circle. All of the other agrarian societies came from closer to
>>> the equator, often much closer.
>>
>> call it 'Jul' and 'Julefeiring (Jul celebration)', and the days are
>> named Julaften (Jul evening) for the 24th, then 1 and 2 Juledag (1st
>> and 2nd day of Jul), going all the way till either the 13th or 20th
>> day of Jul when the festivities are officially over.
>
>Yup (although spelling varies slightly). Even the english have
>'Yuletide' - adapted from the Danish vikings ;-)
Yes. As many people have pointed out, the English festival of
Christmas has never had anything to do with Christianity, and
is merely a renamed festival of Yule. That is what I meant by
"surviving Christianity" - it is the only one of the major
seasonal festivals that remains in anything approximating its
original state.
We don't know for certain that Yule was introduced into Europe by
the Germanic peoples, and was not originally a Celtic festival,
as far as I know. Given the importance of Hogmanay, my personal
guess is the latter.
Regards,
Nick Maclaren.
nm...@cam.ac.uk
Kai Harrekilde-Petersen <k...@harrekilde.dk> wrote:
>nm...@cam.ac.uk writes:
>
>> Where we live, the feeling "Thank God, at least the days are getting
>> longer" is dominant, and must have been more so in the days of
>> candles. In places closer to the equator, the gloom of winter is
>> FAR less marked, and consequentially the solstice is less important.
>
>And you near live Cambridge? =8-|
>
>Its' quite marked how just the ~500km from Copenhagen to Oslo and
>again Oslo - Trondheim changes the amount of daylight both in the
>winter and the summer.
Quite. Britain's winters are gloomier than you might expect from
the latitude, so Cambridge and Copenhagen are probably comparable
in that respect. But, before the rise of northern Europe, the
northernmost 'civilisation' was centred at 42 degrees north!
Regards,
Nick Maclaren.
Bernd Paysan
> On Wed, 07 Jan 2009 06:10:03 -0600, rp...@rpw3.org (Rob Warnock) wrote:
>> [If one starts the year on March 1st] the simplicity of the scheme
>> is quite amazing: a 400-year cycle not only starts 2000-03-01
>> (as it did 1600-03-01), it contains an even number of weeks: 20,871.
>
> Is 20,871 supposed to be the number of weeks? If so, I'm not sure if
> the latter portion of the above statement is correct.
A 400-year cycle, no matter when you start and end it, contains exactly
20871 weeks or 146097 days. Starting it on 1600-3-1 simplifies the leap
year calculation slightly. Starting it on March 1st simplifies the month
calculation. Even though Augustus screwed up the original scheme, where a
division by 30.5 gave the correct month, he didn't screw up too badly. Now
a division by 30.6 gives the correct month (rounding still tricky, but with
the right offset, it works). There are 153 days from 3-1 to 8-1, and
another 153 days from 8-1 to 1-1 next year. The remaining 59 or 60 days
follow the same pattern: First month 31 days, next month less, so that
scheme works again.
So how to calculate the current year-month-day?
* year=floor(day/146097)*400 gives your base cycle start, day=day%146097
will be used further. (day+2)%7 gives day-of-the-week. First day of the
week is Monday (if your week starts on another day, change the offset).
* year+=min(floor(day/36524),3)*100 gives the century (you can't have a
century 4 here, it's just the hangover leap year in y2k); of course we keep
the rest day=day%36524 for further calculation (add 365 if the division
actually gave 4).
* year+=floor(day/1461)*4 breaks things down further, we keep day=day%1461.
* year+=min(floor(day/365),3) gives the current year, again we keep the
remainder day=day%365 as above (if min triggers, add 365).
* month=floor((day+31)*5/153). We keep floor(remainder/5) as day of the
month.
* Finally, we make the necessary corrections: month+=2, if month>12, year++,
month-=12.
No table necessary. I tested this with a fairly short Forth program:
\ convert day since 0-3-1 to ymd
: /mod3 ( n1 n2 -- r q )
dup >r /mod dup 4 = IF drop r@ + 3 THEN rdrop ;
: day2dow ( day -- dow )
2 + 7 mod ;
: day2ymd ( day -- y m d )
146097 /mod 400 * swap
36524 /mod3 100 * rot + swap
1461 /mod 4 * rot + swap
365 /mod3 rot + swap
31 + 5 153 */mod swap 5 /
>r 2 + dup 12 > IF 12 - swap 1+ swap THEN
r> 1+ ;
: ymd2day ( y m d -- day ) -rot
2 - dup 0<= IF 12 + swap 1- swap THEN
153 5 */ 31 - swap
4 /mod swap 365 * swap
25 /mod swap 1461 * swap
4 /mod swap 36524 * swap
146097 * + + + + + ;
With floored division, this works even fine with negative numbers, just
remember that the year 0 really is 1BC. It is fairly trivial to extend this
little program to work correctly even before the October 15th, 1582 (or
whenever the switch happend according to the current locale).
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
Muzaffer Kal
<terje.m...@hda.hydro.com> wrote:
>Muzaffer Kal wrote:
>> On Wed, 07 Jan 2009 06:10:03 -0600, rp...@rpw3.org (Rob Warnock) wrote:
>>> [If one starts the year on March 1st] the simplicity of the scheme
>>> is quite amazing: a 400-year cycle not only starts 2000-03-01
>>> (as it did 1600-03-01), it contains an even number of weeks: 20,871.
>>
>> Is 20,871 supposed to be the number of weeks? If so, I'm not sure if
>> the latter portion of the above statement is correct.
>
>146097 : 7 = 20871, so this is correct.
Ah, so he meant an integral number of weeks. As a programmer I am
always suspect when it comes to counting but even I know that any
number which ends in 1 (in a even numbered base of course) is an odd
number :-)
Muzaffer Kal
wrote:
>Muzaffer Kal wrote:
>
>> On Wed, 07 Jan 2009 06:10:03 -0600, rp...@rpw3.org (Rob Warnock) wrote:
>>> [If one starts the year on March 1st] the simplicity of the scheme
>>> is quite amazing: a 400-year cycle not only starts 2000-03-01
>>> (as it did 1600-03-01), it contains an even number of weeks: 20,871.
>>
>> Is 20,871 supposed to be the number of weeks? If so, I'm not sure if
>> the latter portion of the above statement is correct.
>
>A 400-year cycle, no matter when you start and end it, contains exactly
>20871 weeks or 146097 days.
Thanks for the detailed explanation (which is certainly appreciated)
but mine was much more a pedantic comment: The right word seems to be
integral, not even, ie 20871 is certainly not an even number.
Mike Hore
>
> Where we live, the feeling "Thank God, at least the days are getting
> longer" is dominant, and must have been more so in the days of
> candles. In places closer to the equator, the gloom of winter is
> FAR less marked, and consequentially the solstice is less important.
That's for sure... (Darwin, 12 deg S).
Here we say "...at least now we might get a bit of rain!" :-)
Cheers, Mike.
---------------------------------------------------------------
Mike Hore mike_h...@OVE.invalid.aapt.net.au
---------------------------------------------------------------
Terje Mathisen
>> cycles when using the day number to calculate the day of week.
>
> Though I believe that makes it an integral number of weeks, not an
> even number.
Aha!
Being Norwegian, he's using 'even' as a synonym for our term meaning
'goes into without any remainder'. I know that I would be likely to use
'even' in the same sense, even if the result of the division happens to
be an odd number. :-)
Terje Mathisen
> So how to calculate the current year-month-day?
>
> * year=floor(day/146097)*400 gives your base cycle start, day=day%146097
> will be used further.
Nearly all modern systems work much faster if you calculate this as:
y400 = day / 146097;
day -= y400 * 146097;
I.e. for any kind of constant div/mod operation, if you do the division
first and then back-multiply and subtract, modern compilers are capable
of converting the division into a reciprocal multiplication.
[lots of snips...]
> * year+=min(floor(day/36524),3)*100 gives the century (you can't have a
> * year+=floor(day/1461)*4 breaks things down further, we keep day=day%1461.
> * year+=min(floor(day/365),3) gives the current year, again we keep the
> * month=floor((day+31)*5/153). We keep floor(remainder/5) as day of the
The month/day calculation works but is significantly slower than a
12-entry table, and on many systems it might even need more code space. :-)
My guess is that your (classical) version of the day2ymd() calculation
takes nearly an order of magnitude (5-10) longer than the version I
posted: You are doing a total of 8 full div/mod operations whereas my
code only needed the one initial stage to determine the y400 cycle.
> * Finally, we make the necessary corrections: month+=2, if month>12, year++,
> month-=12.
> With floored division, this works even fine with negative numbers, just
Floored division cannot be depended upon (at least not in C, I guess
Forth is different?), so having a base year in 1200 or previous is safer.
ken...@cix.compulink.co.uk
rp...@rpw3.org (Rob Warnock) wrote:
> .but Julius Caesar decided to move the Roman
> calendar back two months... far more important was the decision
> to retain the leap day in February. In the old calendar, the
> leap day was added at the end of the year, as makes perfect
> sense, when the month was already short,
The problem with that is Julius originated the calendar we use today.
Before the Julian calendar Rome used a lunar one with corrections to the
solar cycle at the whim of Priests. Julius set up the Calendar with
months of 30 and 31 days. February was shortened when Augustus decided
to rename one month and wanted it at 31 days. The year still started in
April that was not changed until the Gregorian calendar was introduced.
Hence the UK financial year still running from April to March.
In the old Roman days the year was roughly 360 days long with the extra
days being used for fest ivies. These may or may not have been in
February it depended on the whims of the priests and how they calculated
the difference between a thirteen month lunar year and a twelve month
solar year.
Ken Young
Ken Hagan
> The year still started in
> April that was not changed until the Gregorian calendar was introduced.
> Hence the UK financial year still running from April to March.
Perversely enough, I think the financial year (if not the civil new year)
started on the equinox, and when a dozen days were skipped in 1752, the
start of the financial year ended up in early April so that the annual
interest on deposits held during 1752 would not have to be paid out too
soon.
Joe Pfeiffer
> Joe Pfeiffer wrote:
>> Terje Mathisen <terje.m...@hda.hydro.com> writes:
>>> It does mean that you can discard the number of initial 400-year
>>> cycles when using the day number to calculate the day of week.
>>
>> Though I believe that makes it an integral number of weeks, not an
>> even number.
>
> Aha!
>
> Being Norwegian, he's using 'even' as a synonym for our term meaning
> goes into without any remainder'. I know that I would be likely to use
> even' in the same sense, even if the result of the division happens to
> be an odd number. :-)
It wasn't until a couple hours after I posted that I realized that
when he said "even" he meant what "evenly divisible".
Ain't English wonderful? :)
Bernd Paysan
> Bernd Paysan wrote:
>> So how to calculate the current year-month-day?
>>
>> * year=floor(day/146097)*400 gives your base cycle start, day=day%146097
>> will be used further.
>
> Nearly all modern systems work much faster if you calculate this as:
>
> y400 = day / 146097;
> day -= y400 * 146097;
>
> I.e. for any kind of constant div/mod operation, if you do the division
> first and then back-multiply and subtract, modern compilers are capable
> of converting the division into a reciprocal multiplication.
For this kind of application (Zune, processor with a divstep and mulstep
instruction) instruction, /mod is faster. You may not have direct access to
it through C, because the compiler is not able to combine day/146097 and
day%146097 into one division with modulus.
Multiplication on this kind of hardware is not faster than division, and
when there's no barrel shifter, even a shift is costly.
There's another opportunity with processors with divstep: Change the divider
as you divide, and eliminate the /mod3 (it's just two further divsteps with
a slightly different quotient, the way divstep not-handles overflow
eliminates the final adjustment). This reduces the five /mod to three.
> [lots of snips...]
>> * year+=min(floor(day/36524),3)*100 gives the century (you can't have a
>> * year+=floor(day/1461)*4 breaks things down further, we keep
>> day=day%1461. * year+=min(floor(day/365),3) gives the current year, again
>> we keep the * month=floor((day+31)*5/153). We keep floor(remainder/5) as
>> day of the
>
> The month/day calculation works but is significantly slower than a
> 12-entry table, and on many systems it might even need more code space.
> :-)
What surprised me is that you actually *can* do an arithmetic calculation of
the months, and don't need a table ;-).
BTW: You can do the complete day2ymd calculation table driven. Guess the
year by dividing by about 365.25 (with the appropriate reciprocal
multiplication; for 32 bit, 11759200 gives reasonable results), and store
for all the years you actually want to deal with (for a throw-away device
like a Zune, 20 years starting with the year you compile the firmware are
more than sufficient; the people at Microsoft were already surprised by the
high number of those early Zunes still in use ;-) the number of days since
the beginning of the epoc. Correct, and then do your table-driven month
calculation. This should be quite faster than your code, and consumes even
less code space.
One multiplication, one shift right by 5, two table lookups, two conditional
jumps.
> My guess is that your (classical) version of the day2ymd() calculation
> takes nearly an order of magnitude (5-10) longer than the version I
> posted: You are doing a total of 8 full div/mod operations whereas my
> code only needed the one initial stage to determine the y400 cycle.
Of course on a modern processor with barrel shifter and parallel
multiplication, your code easily outperforms mine.
>> * Finally, we make the necessary corrections: month+=2, if month>12,
>> year++, month-=12.
>
>> With floored division, this works even fine with negative numbers, just
>
> Floored division cannot be depended upon (at least not in C, I guess
> Forth is different?), so having a base year in 1200 or previous is safer.
In Forth you can count on a floored division primitive, fm/mod. On a divstep
based processor, do it yourself ;-).
Boon
> On Mon, 05 Jan 2009 12:05:45 +0100, Terje Mathisen wrote:
>
>> I read with disbelief about how most of Microsoft's 30 GB Zune players
>> hung on Dec 31st, due to not being able to handle day number 366 of a
>> leap year, and started thinking about some discussions we've had here
>> over the years about the fastests/tightest/most elegant ways to convert
>> between year-month-day and day number.
>
> The thing that I find curious about these sorts of incident is what
> business of devices like the Zune is the date, anyway? I suppose that
> they have some kind of convenience clock function, like my iPod, but I'm
> sure most users wouldn't care if they just didn't.
Date-based Digital Restrictions Management ?
e.g. this file can be only be read between 2008-01-01 and 2008-12-31
If this is the case, then serves them right !
Wilco Dijkstra
"Bernd Paysan" <bernd....@gmx.de> wrote in message news:pgnh36-...@vimes.paysan.nom...
> Terje Mathisen wrote:
>
>> Bernd Paysan wrote:
>>> So how to calculate the current year-month-day?
>>>
>>> * year=floor(day/146097)*400 gives your base cycle start, day=day%146097
>>> will be used further.
>>
>> Nearly all modern systems work much faster if you calculate this as:
>>
>> y400 = day / 146097;
>> day -= y400 * 146097;
>>
>> I.e. for any kind of constant div/mod operation, if you do the division
>> first and then back-multiply and subtract, modern compilers are capable
>> of converting the division into a reciprocal multiplication.
Compilers are quite capable of doing this transformation automatically -
a modulo by constant is done as a division plus multiply and subtract.
> For this kind of application (Zune, processor with a divstep and mulstep
> instruction) instruction, /mod is faster. You may not have direct access to
> it through C, because the compiler is not able to combine day/146097 and
> day%146097 into one division with modulus.
Actually Zune uses an ARM11, ie. no divide or multiplication step instructions.
Non-constant division and modulo are typically done using a library call, and
ARM compilers combine division and modulo on identical expressions into
one library call. ARM cores that support hardware division (but not modulo)
emit modulo as a divide plus a multiply and subtract, so again division and
modulo are optimized.
Wilco
Terje Mathisen
> "Bernd Paysan" <bernd....@gmx.de> wrote in message news:pgnh36-...@vimes.paysan.nom...
>> Terje Mathisen wrote:
>>> y400 = day / 146097;
>>> day -= y400 * 146097;
>>>
>>> I.e. for any kind of constant div/mod operation, if you do the division
>>> first and then back-multiply and subtract, modern compilers are capable
>>> of converting the division into a reciprocal multiplication.
>
> Compilers are quite capable of doing this transformation automatically -
> a modulo by constant is done as a division plus multiply and subtract.
Microsoft C previous to the 2005 version generated significantly fster
code when I wrote it as above, i.e. first div, then back-mult and sub
for the modulo result.
Yesterday I brought that old 2001 code into VS 2005, and compiled for x64:
(y % 400) did indeed result in a reciprocal mul, shift, back-multiply
and subtract.
> Non-constant division and modulo are typically done using a library call, and
> ARM compilers combine division and modulo on identical expressions into
> one library call. ARM cores that support hardware division (but not modulo)
> emit modulo as a divide plus a multiply and subtract, so again division and
> modulo are optimized.
Seems like a reasonable approach.
Chris Morgan
> Yes. As many people have pointed out, the English festival of
> Christmas has never had anything to do with Christianity, and
> is merely a renamed festival of Yule. That is what I meant by
> "surviving Christianity" - it is the only one of the major
> seasonal festivals that remains in anything approximating its
> original state.
>
> We don't know for certain that Yule was introduced into Europe by
> the Germanic peoples, and was not originally a Celtic festival,
> as far as I know. Given the importance of Hogmanay, my personal
> guess is the latter.
The Christians did expand the amount of nice music we enjoy at
Christmas/Yuletide, so I'm grateful for that.
I'm an atheist but I have always loved Christmas. Not the weird stuff
about the baby in the manger, but the music, the pine tree smell,
cards, mince pies, candles etc
Chris
--
Chris Morgan
"Post posting of policy changes by the boss will result in
real rule revisions that are irreversible"
- anonymous correspondent
Bernd Paysan
> The Christians did expand the amount of nice music we enjoy at
> Christmas/Yuletide, so I'm grateful for that.
People did it. Most of the current Christmas "traditions" are only a few
centuries old.
> I'm an atheist but I have always loved Christmas. Not the weird stuff
> about the baby in the manger, but the music, the pine tree smell,
> cards, mince pies, candles etc
I'm an atheist, too, and I've a quite relaxed attitude towards festivals.
During the last year, I had some fun explaining a student in Asia our
culture, by describing each festival as it came along (and I got a
description of their festivals back in exchange). The key point that
religion isn't relevant was in mid September: just after the mid-autumn
festival, I described Oktoberfest. It was instantly clear to the student,
that this is the autumn counterpart to Carnival, just as the mid-autumn
festival is the seasonal counterpart to Chinese New Year. However,
Oktoberfest is a tradition with a completely different origin. No religion
involved at all, and it's a local festival, special to Munich (but there
are many other similar, but smaller festivals around late September in
Germany).
My conclusion is that people want seasonal festivals, and find places for
them. If some religious control freaks want to control what people
celebrate, people push their festival into that framework. If not, they
find other ways. Sometimes, an opportunity opens (like 200 years ago for
the Oktoberfest), and is "filled", giving a reason why to celebrate a
festival. The most funny thing is that after my friend pointed out the
supposed (and - from the behavior of people - obvious) relation between
Oktoberfest and Carnival, I did some more research, and found that there is
indeed one: The strong beer brewed for the fast after Carnival can be
stored up without cooling to the new brewing season, which starts in
October. The remaining beer is consumed just before the new brewing season
starts - at the end of September. The resulting behavior during these
festivals is a consequence of the drinks ;-). Not that this makes any
sense in the age of the refrigerator, but it did so in the past.
In the end, all the religious context just falls apart. People don't brew
strong beer for the fast before Easter, but because that's the only way to
make it last across warm weather in summer. And they don't celebrate a
festival at end of September, because some popular king got laid, but to
make room for fresh beer. The origin of Christmas and Ester has been
traced back to non-christian origin, as well; with volatile "traditions"
that don't last for more than a few centuries. And Carnival? Well, if you
have seen Carnival in south German, you doubt that it ever had any
christian ties at all ;-).
nm...@cam.ac.uk
Bernd Paysan <bernd....@gmx.de> wrote:
>Chris Morgan wrote:
>> The Christians did expand the amount of nice music we enjoy at
>> Christmas/Yuletide, so I'm grateful for that.
>
>People did it. Most of the current Christmas "traditions" are only a few
>centuries old.
Actually, many of them are either more recent (i.e. under two centuries
old) or several millennia old (i.e. pre-Christian), at least in the UK.
Of course, some of our Victorian traditions were imported (sometimes
via Prince Albert) from somewhat older continental ones :-)
But the feasting, (now rare) Yule log, evergreen decorations, tree
etc. are all pre-Christian.
Regards,
Nick Maclaren.
Brian Inglis
<ly...@garlic.com> wrote:
>re:
>http://www.garlic.com/~lynn/2009.html#16 Date arithmetic and Zune bug
>
>for a little other topic drift (leap "seconds" rather than "year"):
>
>'Leap Second' Snafu Affects Oracle Clusterware
>http://www.pcworld.com/article/156453/leap_second_snafu_affects_oracle_clusterware.html
>
>back circa 1970 ... i spent 3months with a number of other people
>discussing what to do about "leap seconds" (that and what does the
>"start of the century" mean ... i.e. did the century start in 1900 or
>1901?) ... this was for the 370 TOD clock.
TZ list just announced a Bug in TZ code <hvoSnB.A.MuF.FlOeJB@lecserver>
where the zoneinfo compiler zic has a problem caused by leapseconds
breaking the assumed period of the zone transitions.
Suggested fix is to generate 400 years of transition times following the
last announced leapsecond.
The US push to have the ITU (what do they have to do with defining
time?) drop leapseconds from UTC (thought that was defined in
international law), and add a leaphour in about 600 years when we're all
dead in another timezone, is not likely to improve matters.
--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada
Brian....@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply