A better algorithm to calculate a leap year?

[Tor Rustad]

Richard Heathfield wrote:

[Q: To leap or not to leap?]

Here's a better method:

int really_is_leap(int year)
{
return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
}

This one has the merit of actually giving the right results.

The Gregorian Calendar is not used everywhere in the world, even in the
Catholic countries, it was not used before

assert(year > 1582);

The Protestantic countries was far more skeptical, and didn't like to be
dictated by the Pope. Anyway, Germany, Switzerland and Denmark-Norway
finally followed in

assert(year > 1700);

As usual, the Brits was slow (btw they might switch to euro some day!),
so for the British Empire we have

assert(year > 1752);

at least you beat Sweden/Finland to it by a year. ;-) However, the
Swedes did this their own way, and instead of loosing many days at once,
they dropped 10+ leap years afterwards.

etc. etc.

Test your function, and see how it works on years that you know to be leap
years (eg 1976, 2000, 2004, 2008) and years you know not to be leap years
(2001, 2002, 2003, 2005).

Then switch to a working algorithm.

As an example to us all, in 1983, Stanley Rabinowitz made this
*masterpiece* of a maintainer response to a VAX/VMS leap-year bug report:

http://rudy.ca/lycomplaint.html

 

[Jean-Marc Bourguet]

int really_is_leap(int year)
{
return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
}

This one has the merit of actually giving the right results.

How about for year 0?

There wasn't a year 0. The year after 1 BC was 1 AD.

There is a year 0 in the Gregorian calendar, but few people use it for
dates before its first adoption. There is no year 0 in the "Julian"
calendar which is more commonly used for giving date at this period even if
it wasn't in use with that origin. I seem to remember that taking into
account leap years as observed in that period is funny, you need to get a
table because the rules where not followed.

See http://emr.cs.iit.edu/home/reingold/calendar-book/second-edition/.
This reference could also of use for the OP.

A+

 

[Dik T. Winter]

>
> Try this:
>
> return (year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0));
>
> I think that's the correct formula (evenly divisible by 400, or evenly
> divisible by 4 and not evenly divisible by 100).

Depends on the calendar you are using. The %4 rule etc. is valid for the
Gregorian calendar. I think the %19 rule above is valid for the Muslim
calendar.

 

[gw7rib]

int really_is_leap(int year)
{
return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
}
This one has the merit of actually giving the right results.

How about for year 0?

Strangely enough, a couple of my programs use 0 as a wildcard, ie
meaning any year, and in those cases I want the number of days in
February to be returned as 29, because some years do have 29 days in
February. So the above formula can be used without a special
modification.

Paul.

 

[Nick Keighley]

The Gregorian Calendar is not used everywhere in the world, even in the
Catholic countries, it was not used before

assert(year > 1582);

The Protestantic countries was far more skeptical, and didn't like to be
dictated by the Pope. Anyway, Germany, Switzerland and Denmark-Norway
finally followed in

assert(year > 1700);

As usual, the Brits was slow (btw they might switch to euro some day!),
so for the British Empire we have

assert(year > 1752);

at least you beat Sweden/Finland to it by a year. ;-) However, the
Swedes did this their own way, and instead of loosing many days at once,
they dropped 10+ leap years afterwards.

etc. etc.

I believe the Russians didn't change until 1917

 

[Dik T. Winter]

This is not entirely correct. They wanted to do that but failed to do it
after the first dropping. This was corrected in 1712 by adding a 30rd of
February, when they came back again to the Julian calendar.

> I believe the Russians didn't change until 1917

And in Greece it was only adopted in 1923.

 

[Barry Schwarz]

Sorry, should have noted. This is to generate a Jewish calendar (This
is the year 5768, and therefore a leap year with an extra month thrown
in mid-March to mid-April, which is why Easter is 3 weeks later this

It may explain why Passover is three weeks later (actually less than
2.5) but it has nothing to do with Easter.

year than it was last year). The numbers in the code are correct. I
was wondering if there was any better algorithm. Thanks to all who
responded, and apologies for the misunderstanding.

-- Marty (a newbie, starting off on the wrong foot)

Remove del for email

 

[Barry Schwarz]

OK, if people want to test this for themselves it looks like the code
should be more robust in terms of "clever" optimisers. Try the
following
which sums and prints the number of leap years found:
***/
#include <stdio.h>
#include <time.h>
#define START_YEAR 1582
#define END_YEAR 4000
#define ITERATIONS 100000

typedef unsigned (*leap_func)(unsigned);

static unsigned is_a_leap_year1(unsigned y)
{
return (y % 400u == 0u) ? 1 : (y % 100u == 0u) ? 0u : (y % 4u ==
0u);

Two of the three possible return values are signed and 1 is unsigned.
Did you have something special in mind when you specified the u after
the second "?" and not for any of the other return values?

}

Remove del for email

 

[user923005]

Two of the three possible return values are signed and 1 is unsigned.
Did you have something special in mind when you specified the u after
the second "?" and not for any of the other return values?

Error on my part. I converted some old code that had signed int for
all data types.
Since Gregorian dates never have negative years, I changed to
unsigned.
My intention was to change all elements of the calculations to
unsigned type to avoid any conversion costs.
I forgot a couple in that function.

 

[James Kuyper]

user923005 wrote:
....

Since Gregorian dates never have negative years, I changed to
unsigned.

The traditional proleptic Gregorian calendar uses positive year numbers
and "BC", but the proleptic Gregorian calendar used in ISO 8601 assigns
a year number of 0 to 1BC, and negative year numbers to earlier dates.
It's up to you whether you want to support this, but ISO 8601 is, as
it's name implies, an International Standard. If you want to support the
traditional proleptic calendar, you should provide some way of
indicating BC dates.

 

[Amandil]

It may explain why Passover is three weeks later (actually less than
2.5) but it has nothing to do with Easter.

Correction noted. Passover started last year on April 3, this year it
starts on April 20. My comment about Easter was so that those who
couldn't care less about Passover might also respond. However, I do
believe that Easter is (nearly) always the Sunday after Passover, and
therefore is the same 2.5 - 3 weeks later in Jewish leap years.

I appreciate all the responses, and I'd like to comment on some of
them.

int is_leap(int year)
{
return (0x00024949U & (1U << year%19)) != 0;

}

-- James

Thanks. From reading the assembly output of GCC I saw the same
optimization, but could not understand it. I now do. Also I think this
is the better of the two suggestions that I received.

Although, I would recommend renaming the function to something that
won't cause confusion if the application is ever combined with code
that also deals with Gregorian.

If I do (and I intend to) add the Gregorian calendar to my program,
I'll probably call the function secular_leap() or something.

From Eric Sosman, I saw:
The principal alternative (which I haven't seen
anyone mention yet) would be to use a table:

int is_leap(int year)
{
static const int answer[19] = {
1, 0, 0, 1, 0, 0, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0 };
return answer[ year % 19 ];
}

I actually did think of that. This method is, I believe, the fastest
and the easiest to implement in a macro. However, I personal felt that
a 76-byte table was a waste of space.

Both versions can misbehave if `year' is negative:
The remainder `-3 % 19' can be either -3 or 16 under
C89 rules; under C99 rules the result is -3. Negative
years may be nonsensical given the application, but the
principle of coding defensively suggests you should be
wary. Three possibilities occur to me:

<snip>

Actually, when the year is first entered by the user (command line or
prompt) I make sure the year is within the range 1-6000, year 1 being
(as someone else noted) the year of Creation (according to the Jewish
count, of course). In any case, the calendar as calculated was only
instituted in the 3rd or 4th century and is only to last (at most)
until the year 6000 (2240 C.E.). Prior to the calendar, the sages of
the time decided each year what the calendar should look like... but
that's already going off topic, so I'll finish with that.
Again, thanks to all, and apologies for those who were mislead.

-- Marty (Do I still have newbie status?)

 

[Dik T. Winter]

> Correction noted. Passover started last year on April 3, this year it
> starts on April 20. My comment about Easter was so that those who
> couldn't care less about Passover might also respond. However, I do
> believe that Easter is (nearly) always the Sunday after Passover, and
> therefore is the same 2.5 - 3 weeks later in Jewish leap years.

This is only approximately. Jewish passover is always on Nissan 14.
Christian Easter is on the first sunday *after* the first full moon
on or after the vernal equinox, where both the full moon and the vernal
equinox are based on calculations. But the calculations are different
between the Western Christian branches and the Eastern Christian branches,
so they agree only in about one third of the cases. The rule you observed
that Western Easter is almost always on the Sunday after Passover is right
(the rules are basically the same with a nineteen-year cycle), but your
statement that so it is 2.5 to 3 weeks later in Jewish leap years is
wrong. In the period 2000-2020 (5760-5780) there is only one year when
that is not the case: 2005 (5765), when Passover falls four weeks after
Easter (Passover 24th April, Easter 27th March). The reason for that small
discrepancy is that in the Easter calculations almost the same nineteen year
cycle is used as is used in the Jewish calendar. So there occurs a
difference when the Jewish calendar does have a leap year (with an added
month) while the Christian Easter calendar does *not* have a leap year (so
has no added month). The discrepance between Western and Eastern Easter
is because the Easter (lunar) calendar is calculated differently. For
this reason in 2002 Western Easter was on 31th March and Eastern Easter on
5th May the other huge differences until 2020 occur in 2005, 2008, 2013 and
2016; I suspect a discrepancy in the Metonic cycles of nineteen years used,
in other years they are either on the same day or the Eastern Easter is one
week later than the Western one.

(Yes, by now I know how to type Easter blind ;-). And by now you do not
want information about calendars in this newsgroup anymore...)

>
> Thanks. From reading the assembly output of GCC I saw the same
> optimization, but could not understand it. I now do. Also I think this
> is the better of the two suggestions that I received.

If the compiler can do the optimisation, why should you do it? When you
do it in your code you only obfuscate your code, and make debuggin a
problem.

 

[Keith Thompson]

From Eric Sosman, I saw:
The principal alternative (which I haven't seen
anyone mention yet) would be to use a table:

int is_leap(int year)
{
static const int answer[19] = {
1, 0, 0, 1, 0, 0, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0 };
return answer[ year % 19 ];
}

I actually did think of that. This method is, I believe, the fastest
and the easiest to implement in a macro. However, I personal felt that
a 76-byte table was a waste of space.

Making the table an array of char rather than of int would reduce its
size to 19 bytes.

 

[Eric Sosman]

Keith Thompson wrote On 11/07/07 22:09,:

From Eric Sosman, I saw:

The principal alternative (which I haven't seen
anyone mention yet) would be to use a table:

int is_leap(int year)
{
static const int answer[19] = {
1, 0, 0, 1, 0, 0, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0 };
return answer[ year % 19 ];
}

I actually did think of that. This method is, I believe, the fastest
and the easiest to implement in a macro. However, I personal felt that
a 76-byte table was a waste of space.

Making the table an array of char rather than of int would reduce its
size to 19 bytes.

... or for even greater compaction (and obfuscation),
make it an integer constant:

int is_leap(int year) {
return (149833 >> (year % 19)) & 1;
}

 

[user923005]

Keith Thompson wrote On 11/07/07 22:09,:

[...]

From Eric Sosman, I saw:
The principal alternative (which I haven't seen
anyone mention yet) would be to use a table:
int is_leap(int year)
{
static const int answer[19] = {
1, 0, 0, 1, 0, 0, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0 };
return answer[ year % 19 ];
}
I actually did think of that. This method is, I believe, the fastest
and the easiest to implement in a macro. However, I personal felt that
a 76-byte table was a waste of space.

Making the table an array of char rather than of int would reduce its
size to 19 bytes.

... or for even greater compaction (and obfuscation),
make it an integer constant:

int is_leap(int year) {
return (149833 >> (year % 19)) & 1;
}

If there were a way to note numbers as binary in C, then there would
be no obfuscation at all since:
100100100101001001 (Base 2) = 149833 (Base 10)

Maybe something like:
0b
as a prefix would be nice.

 

[Barry Schwarz]

Correction noted. Passover started last year on April 3, this year it
starts on April 20. My comment about Easter was so that those who
couldn't care less about Passover might also respond. However, I do
believe that Easter is (nearly) always the Sunday after Passover, and
therefore is the same 2.5 - 3 weeks later in Jewish leap years.

In 2006 Easter was April 16. In 2007 it was April 8. In 2008 it will
be March 23.

I'm just wondering what "Easter is 3 weeks later this year than it was
last year" in your explanation refers to.

While Easter should follow Passover, since the Last Supper was
reportedly a Seder, in 2008 it is almost a month before Passover which
starts April 19.


Remove del for email

 

[jxh]

If the compiler can do the optimisation, why should you do it?
When you do it in your code you only obfuscate your code, and
make debuggin a problem.

I agree with Dik (that's pronounced "deek" right?), if the
compiler is really converting your case statement into this
code for you, you should leave the code as a case statement.

Also, Eric's formulation is slightly more compact and in my
opinion a little clearer, except for the use of decimal to
express the constant (I find it easier to convert hex to
binary by hand when the need arises). In proper code, the
function should contain a comment explaining where the
constant came from.

-- James

 

[Willem]

jxh wrote:
) I agree with Dik (that's pronounced "deek" right?),

Nope, it's pronounced 'Dick'.
As in 'Penis van Lesbian'.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Eric Sosman]

jxh wrote On 11/08/07 20:38,:

[...]
Also, Eric's formulation is slightly more compact and in my
opinion a little clearer, except for the use of decimal to
express the constant (I find it easier to convert hex to
binary by hand when the need arises). [...]

Can't a guy have a little fun now and then? I was
planning to write 'MII', but decided there were too many
implementation-defined aspects to risk on c.l.c. ;-)

 

[Charlie Gordon]

Keith Thompson wrote On 11/07/07 22:09,:

From Eric Sosman, I saw:

The principal alternative (which I haven't seen
anyone mention yet) would be to use a table:

int is_leap(int year)
{
static const int answer[19] = {
1, 0, 0, 1, 0, 0, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0 };
return answer[ year % 19 ];
}

I actually did think of that. This method is, I believe, the fastest
and the easiest to implement in a macro. However, I personal felt that
a 76-byte table was a waste of space.

Making the table an array of char rather than of int would reduce its
size to 19 bytes.

... or for even greater compaction (and obfuscation),
make it an integer constant:

int is_leap(int year) {
return (149833 >> (year % 19)) & 1;
}

Very elegant! But such conciseness requires an explanatory comment for the
magic value.