Velocity Reviews > A better algorithm to calculate a leap year?

# A better algorithm to calculate a leap year?

mazwolfe@gmail.com
Guest
Posts: n/a

 11-05-2007
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.

Walter Roberson
Guest
Posts: n/a

 11-05-2007
In article <(E-Mail Removed). com>,
<(E-Mail Removed)> 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

Richard Heathfield
Guest
Posts: n/a

 11-05-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) 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, 200 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

John Bode
Guest
Posts: n/a

 11-05-2007
On Nov 5, 12:30 pm, (E-Mail Removed) 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
Guest
Posts: n/a

 11-05-2007
On Nov 5, 12:30 pm, (E-Mail Removed) 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).

mazwolfe@gmail.com
Guest
Posts: n/a

 11-05-2007
On Nov 5, 1:30 pm, (E-Mail Removed) 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)

Willem
Guest
Posts: n/a

 11-05-2007
(E-Mail Removed) wrote:
) On Nov 5, 1:30 pm, (E-Mail Removed) 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

user923005
Guest
Posts: n/a

 11-05-2007
On Nov 5, 10:54 am, John Bode <(E-Mail Removed)> wrote:
> On Nov 5, 12:30 pm, (E-Mail Removed) 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
*/

jxh
Guest
Posts: n/a

 11-05-2007
On Nov 5, 11:10 am, (E-Mail Removed) wrote:
> On Nov 5, 1:30 pm, (E-Mail Removed) 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

pete
Guest
Posts: n/a

 11-05-2007
John Bode wrote:
>
> On Nov 5, 12:30 pm, (E-Mail Removed) 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