# A better algorithm to calculate a leap year?

Discussion in 'C Programming' started by mazwolfe@gmail.com, Nov 5, 2007.

1. ### Guest

I'm new here, so excuse me if my style is incorrect. Can anyone come
up with a better method for this calculation?

Code:
int is_leap(int year)
{
switch (year % 19) {
case 0: case 3: case 6: case 8:
case 11: case 14: case 17: return 1;
default: return 0;
}
}

This is part of a calendar program.

, Nov 5, 2007

2. ### Walter RobersonGuest

In article <>,
<> wrote:
>I'm new here, so excuse me if my style is incorrect. Can anyone come
>up with a better method for this calculation?

>Code:
>int is_leap(int year)
>{
> switch (year % 19) {
> case 0: case 3: case 6: case 8:
> case 11: case 14: case 17: return 1;
> default: return 0;
> }
>}

1900 % 19 == 0 but 1900 was not a leap year (special case)
1903 % 19 == 3 but 1903 was not a leap year.
1906 % 19 == 6 but 1906 was not a leap year.
1911 % 19 == 11 but 1911 was not a leap year.
1914 % 19 == 14 but 1914 was not a leap year.
1917 % 19 == 17 but 1917 was not a leap year.
2000 % 19 == 5 but 2000 *was* a leap year.
2004 % 19 == 9 but 2004 *was* a leap year.

It isn't a simple case of having to subtract an base year
to get to the start of the cycle:
you have a leap year at year 0 of the cycle, and another at
year +3 (not year +4), another at year +6, then
one just 2 years later at year +8. Clearly this is wrong.
--
"Any sufficiently advanced bug is indistinguishable from a feature."
-- Rich Kulawiec

Walter Roberson, Nov 5, 2007

3. ### Richard HeathfieldGuest

said:

> I'm new here, so excuse me if my style is incorrect. Can anyone come
> up with a better method for this calculation?
>
> Code:
> int is_leap(int year)
> {
> switch (year % 19) {
> case 0: case 3: case 6: case 8:
> case 11: case 14: case 17: return 1;
> default: return 0;
> }
> }
>
> This is part of a calendar program.

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.

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.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield, Nov 5, 2007
4. ### John BodeGuest

On Nov 5, 12:30 pm, wrote:
> I'm new here, so excuse me if my style is incorrect. Can anyone come
> up with a better method for this calculation?
>
> Code:
> int is_leap(int year)
> {
> switch (year % 19) {
> case 0: case 3: case 6: case 8:
> case 11: case 14: case 17: return 1;
> default: return 0;
> }
>
> }
>
> This is part of a calendar program.

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).

John Bode, Nov 5, 2007
5. ### John BodeGuest

On Nov 5, 12:30 pm, wrote:
> I'm new here, so excuse me if my style is incorrect. Can anyone come
> up with a better method for this calculation?
>
> Code:
> int is_leap(int year)
> {
> switch (year % 19) {
> case 0: case 3: case 6: case 8:
> case 11: case 14: case 17: return 1;
> default: return 0;
> }
>
> }
>
> This is part of a calendar program.

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).

John Bode, Nov 5, 2007
6. ### Guest

On Nov 5, 1:30 pm, wrote:
> I'm new here, so excuse me if my style is incorrect. Can anyone come
> up with a better method for this calculation?

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
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)

, Nov 5, 2007
7. ### WillemGuest

wrote:
) On Nov 5, 1:30 pm, wrote:
)> I'm new here, so excuse me if my style is incorrect. Can anyone come
)> up with a better method for this calculation?
)
) 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
) 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.

Nice one

In any case, what would you feel is a 'better' algorithm ?
Faster ? Less code ?
What you wrote seems pretty clear and robust to me.

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

Willem, Nov 5, 2007
8. ### user923005Guest

On Nov 5, 10:54 am, John Bode <> wrote:
> On Nov 5, 12:30 pm, wrote:
>
> > I'm new here, so excuse me if my style is incorrect. Can anyone come
> > up with a better method for this calculation?

>
> > Code:
> > int is_leap(int year)
> > {
> > switch (year % 19) {
> > case 0: case 3: case 6: case 8:
> > case 11: case 14: case 17: return 1;
> > default: return 0;
> > }

>
> > }

>
> > This is part of a calendar program.

>
> 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).

/***
Using Mike Lee's Driver (modified a bit by DRC):
------------------------------------------------
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);
}

static unsigned is_a_leap_year2(unsigned y)
{
return !(y % 4u) && ((y % 100u) || !(y % 400u));
}

static unsigned is_a_leap_year3(unsigned y)
{
return !(y & 3u) && ((y % 100u) || !(y % 400u));
}

// Kirby
static unsigned is_a_leap_year4(unsigned y)
{
return y & 3u ? 0u : y % 25u ? 1u : y / 25u & 12u ? 0u : 1u;
}
// Hu
static unsigned is_a_leap_year5(unsigned y)
{
return (y & 3u) ? 0u : (y % 25u) ? 1u : (y & 15u) ? 0u : 1u;
}
static void test_leap(const char *name, leap_func f)
{
unsigned i,
year;
clock_t start,
end;
unsigned long leap_count = 0;
start = clock();
for (i = 0; i < ITERATIONS; i++) {
for (year = START_YEAR; year <= END_YEAR; year++)
leap_count += f(year);
}
end = clock();
leap_count /= ITERATIONS;
printf("%s leap_count=%lu %.2f seconds\n", name, leap_count,
(double) (end - start) / (double) CLOCKS_PER_SEC);
}
int main(void)
{
printf("START_YEAR=%d END_YEAR=%d ITERATIONS=%d\n", START_YEAR,
END_YEAR,
ITERATIONS);
test_leap("is_a_leap_year1", is_a_leap_year1);
test_leap("is_a_leap_year2", is_a_leap_year2);
test_leap("is_a_leap_year3", is_a_leap_year3);
test_leap("is_a_leap_year4", is_a_leap_year4);
test_leap("is_a_leap_year5", is_a_leap_year5);
return 0;
}
/*
After profile guided optimization, methods 2-5
are all about the same speed, and the "standard"
method is shown to be slower than the others.

Hardware 2.2GHz AMD, compiler MSVC++ 2005 with PGO.

C:\tmp\isleap\Release>isleap
START_YEAR=1582 END_YEAR=4000 ITERATIONS=100000
is_a_leap_year1 leap_count=587 1.92 seconds
is_a_leap_year2 leap_count=587 1.11 seconds
is_a_leap_year3 leap_count=587 1.09 seconds
is_a_leap_year4 leap_count=587 1.11 seconds
is_a_leap_year5 leap_count=587 1.09 seconds

C:\tmp\isleap\Release>isleap
START_YEAR=1582 END_YEAR=4000 ITERATIONS=100000
is_a_leap_year1 leap_count=587 1.92 seconds
is_a_leap_year2 leap_count=587 1.09 seconds
is_a_leap_year3 leap_count=587 1.13 seconds
is_a_leap_year4 leap_count=587 1.09 seconds
is_a_leap_year5 leap_count=587 1.11 seconds

C:\tmp\isleap\Release>isleap
START_YEAR=1582 END_YEAR=4000 ITERATIONS=100000
is_a_leap_year1 leap_count=587 1.92 seconds
is_a_leap_year2 leap_count=587 1.11 seconds
is_a_leap_year3 leap_count=587 1.09 seconds
is_a_leap_year4 leap_count=587 1.11 seconds
is_a_leap_year5 leap_count=587 1.09 seconds

C:\tmp\isleap\Release>isleap
START_YEAR=1582 END_YEAR=4000 ITERATIONS=100000
is_a_leap_year1 leap_count=587 1.92 seconds
is_a_leap_year2 leap_count=587 1.11 seconds
is_a_leap_year3 leap_count=587 1.11 seconds
is_a_leap_year4 leap_count=587 1.09 seconds
is_a_leap_year5 leap_count=587 1.09 seconds

C:\tmp\isleap\Release>isleap
START_YEAR=1582 END_YEAR=4000 ITERATIONS=100000
is_a_leap_year1 leap_count=587 1.92 seconds
is_a_leap_year2 leap_count=587 1.09 seconds
is_a_leap_year3 leap_count=587 1.11 seconds
is_a_leap_year4 leap_count=587 1.11 seconds
is_a_leap_year5 leap_count=587 1.09 seconds
*/

user923005, Nov 5, 2007
9. ### jxhGuest

On Nov 5, 11:10 am, wrote:
> On Nov 5, 1:30 pm, wrote:
> > I'm new here, so excuse me if my style is incorrect. Can
> > anyone come up with a better method for this calculation?

> 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 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.

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

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.

-- James

jxh, Nov 5, 2007
10. ### peteGuest

John Bode wrote:
>
> On Nov 5, 12:30 pm, wrote:
> > I'm new here, so excuse me if my style is incorrect. Can anyone come
> > up with a better method for this calculation?
> >
> > Code:
> > int is_leap(int year)
> > {
> > switch (year % 19) {
> > case 0: case 3: case 6: case 8:
> > case 11: case 14: case 17: return 1;
> > default: return 0;
> > }
> >
> > }
> >
> > This is part of a calendar program.

>
> 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).

K&R2 has an equivalent expression on page 111.

--
pete

pete, Nov 5, 2007
11. ### Eric SosmanGuest

wrote On 11/05/07 13:30,:
> I'm new here, so excuse me if my style is incorrect. Can anyone come
> up with a better method for this calculation?
>
> Code:
> int is_leap(int year)
> {
> switch (year % 19) {
> case 0: case 3: case 6: case 8:
> case 11: case 14: case 17: return 1;
> default: return 0;
> }
> }

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 ];
}

Whether this is better depends on how you define
"better." The tabular version may be more compact;
the switched version is easier to read.

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:

1) Make the `year' argument an `unsigned int', so
negative values can never appear.

2) Insert an explicit test for negative `year', and
take some appropriate action (error message?) if
you get one.

3) Replace `year % 19' with `(year % 19 + 19) % 19',
or with `(year %= 19 < 0) ? year + 19 : year'.

(There are other ways, but these seem to cover the major
themes.)

--

Eric Sosman, Nov 5, 2007
12. ### user923005Guest

On Nov 5, 1:15 pm, jxh <> wrote:
> On Nov 5, 11:10 am, wrote:
>
> > On Nov 5, 1:30 pm, wrote:
> > > I'm new here, so excuse me if my style is incorrect. Can
> > > anyone come up with a better method for this calculation?

> > 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 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.

>
> int is_leap(int year)
> {
> return (0x00024949U & (1U << year%19)) != 0;
>
> }
>
> 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.
>
> -- James

which aligns with GMT perfectly):
http://individual.utoronto.ca/kalendis/hebrew/rect.htm#leap

user923005, Nov 5, 2007
13. ### peteGuest

Richard Heathfield wrote:
>
> said:
>
> > I'm new here, so excuse me if my style is incorrect. Can anyone come
> > up with a better method for this calculation?
> >
> > Code:
> > int is_leap(int year)
> > {
> > switch (year % 19) {
> > case 0: case 3: case 6: case 8:
> > case 11: case 14: case 17: return 1;
> > default: return 0;
> > }
> > }
> >
> > This is part of a calendar program.

>
> 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 parentheses in the return statement
make no difference in the results.

--
pete

pete, Nov 5, 2007
14. ### user923005Guest

On Nov 5, 1:40 pm, pete <> wrote:
> Richard Heathfield wrote:
>
> > said:

>
> > > I'm new here, so excuse me if my style is incorrect. Can anyone come
> > > up with a better method for this calculation?

>
> > > Code:
> > > int is_leap(int year)
> > > {
> > > switch (year % 19) {
> > > case 0: case 3: case 6: case 8:
> > > case 11: case 14: case 17: return 1;
> > > default: return 0;
> > > }
> > > }

>
> > > This is part of a calendar program.

>
> > 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 parentheses in the return statement
> make no difference in the results.

True, but they are useful as a sort of comment for people who are
unsure about precedence. For sure, the code generated will not be any
worse.

P.S.
There are gobs of Hebrew calendars on Sourceforge such as:
http://sourceforge.net/project/showfiles.php?group_id=63109

user923005, Nov 5, 2007
15. ### Christopher Benson-ManicaGuest

[comp.lang.c] Richard Heathfield <> wrote:

> 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.

--
C. Benson Manica | I appreciate all corrections, polite or otherwise.
cbmanica(at)gmail.com |
----------------------| I do not currently read any posts posted through
sdf.lonestar.org | Google groups, due to rampant unchecked spam.

Christopher Benson-Manica, Nov 5, 2007
16. ### Ben PfaffGuest

user923005 <> writes:

> On Nov 5, 1:40 pm, pete <> wrote:
>> Richard Heathfield wrote:
>> > 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 parentheses in the return statement
>> make no difference in the results.

>
> True, but they are useful as a sort of comment for people who are

The parentheses are not redundant--deleting them changes how the
expression parses. The precedence of && and || simply doesn't
matter in this case.
--
"I don't have C&V for that handy, but I've got Dan Pop."
--E. Gibbons

Ben Pfaff, Nov 5, 2007
17. ### Rob KendrickGuest

On Mon, 05 Nov 2007 21:55:58 +0000, Christopher Benson-Manica wrote:

> [comp.lang.c] Richard Heathfield <> wrote:
>
>> 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.

B.

Rob Kendrick, Nov 5, 2007
18. ### peteGuest

user923005 wrote:
>
> On Nov 5, 1:40 pm, pete <> wrote:
> > Richard Heathfield wrote:
> >
> > > said:

> >
> > > > I'm new here, so excuse me if my style is incorrect.
> > > > Can anyone come
> > > > up with a better method for this calculation?

> >
> > > > Code:
> > > > int is_leap(int year)
> > > > {
> > > > switch (year % 19) {
> > > > case 0: case 3: case 6: case 8:
> > > > case 11: case 14: case 17: return 1;
> > > > default: return 0;
> > > > }
> > > > }

> >
> > > > This is part of a calendar program.

> >
> > > 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 parentheses in the return statement
> > make no difference in the results.

>
> True, but they are useful as a sort of comment for people who are
> unsure about precedence. For sure, the code generated will not be any
> worse.

Those parentheses impose new precedence,
rather than emphasize the natural precedence of && and ||.

Part of what I was getting at, was that these expressions

year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)
(year % 4 == 0 && year % 100 != 0) || year % 400 == 0

have the same value.

--
pete

pete, Nov 5, 2007
19. ### Keith ThompsonGuest

writes:
> I'm new here, so excuse me if my style is incorrect. Can anyone come
> up with a better method for this calculation?
>
> Code:
> int is_leap(int year)
> {
> switch (year % 19) {
> case 0: case 3: case 6: case 8:
> case 11: case 14: case 17: return 1;
> default: return 0;
> }
> }
>
> This is part of a calendar program.

You mentioned later that this is for a Jewish calendar. I'm not
familiar with the rules; does it really have 7 leap years every 19
years?

Assuming the algorithm is correct, the code looks decent. You should
think about the behavior for negative years; it may not be an issue,
but you should think about it.

Another possibility would be a table lookup, something like:

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

Or you could use a bit array.

Either looks about equally good to me. In your code, I'd probably
line up the "case" keywords:

case 0: case 3: case 6: case 8:
case 11: case 14: case 17:
return 1;
default:
return 0;

or perhaps put one "case" on each line.

Given the regularity of the pattern, I suspect there's a fairly simple
integer arithmetic expression that avoids enumerating all 19 cases, or
all 7 cases, but I'm too lazy to figure it out, and for something this
small it wouldn't be a great improvement.

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, Nov 5, 2007
20. ### Guest

Keith Thompson wrote:
> writes:
> > I'm new here, so excuse me if my style is incorrect. Can anyone come
> > up with a better method for this calculation?
> >
> > Code:
> > int is_leap(int year)
> > {
> > switch (year % 19) {
> > case 0: case 3: case 6: case 8:
> > case 11: case 14: case 17: return 1;
> > default: return 0;
> > }
> > }
> >
> > This is part of a calendar program.

>
> You mentioned later that this is for a Jewish calendar. I'm not
> familiar with the rules; does it really have 7 leap years every 19
> years?

The months of the Hebrew calendar are lunar months, of either 29 or 30
days. Originally the length was determined by observation of the moon,
but eventually the average length was set to 29 days 12 hours 44
minutes and 3+1/3 seconds, the value that was published by Ptolemy in
the Almagest as the period of the Lunar month. It's about 3/5 second
longer than the current astronomical month. The solar year contains
more than 12 and less than 13 lunar months. The Hebrew calendar deals
with this by inserting an extra intercalary month in the years
identified by the above algorithm. These aren't really leap years as
the term is understood in the Gregorian calendar system. The Hebrew
calendar's year comes out to about 6 minutes and 25+25/57 seconds
longer than the current astronomical solar year.

All of this is from Wikipedia, with all of the usual caveats. However,
it is consistent with what I remember from more traditionally reliable
sources.

> Assuming the algorithm is correct, the code looks decent. You should
> think about the behavior for negative years; it may not be an issue,
> but you should think about it.

The world was supposedly created at or shortly before the start of the
first year of the Jewish calendar; it's possible that the people who
actually use it have little or no use for negative year values.

, Nov 5, 2007