Thread: is leap year function

Hi,

I've written this to calculate leap years but it's slow. Any ideas on how to improve? I've already used stuff like a ^= a to make things 0 (so therefore quicker) but maybe it can be optimised more.

Code:

#include <stdio.h>

#define COG1_TEETH    0x04
#define COG2_TEETH    0x19
#define COG3_TEETH    0x04
#define BASE          0x630
/* BASE == (4 * COG1_TEETH * COG2_TEETH * COG3_TEETH - 0x10) */
 
int il(int v);

int main(void) {
    int year;
    printf("Please enter a year\n");
    scanf("%d", &year);
    printf("%d is %s\n", year, il(year) 
                                    ? "a leap year" 
                                    : "not a leap year");
    return 0;
}
 
int il(int y) {
 
    unsigned a, b, c;
    unsigned i;
        
    if (y < BASE) return 0;
    
    a = 0;
    b = COG2_TEETH - COG1_TEETH;
    c = COG3_TEETH - (COG1_TEETH >> 2);
    i = y - BASE;
    
    while (i--) {
        if (++a == COG1_TEETH) {
            a ^= a;
            if (++b == COG2_TEETH) {
                b ^= b;
                if (++c == COG3_TEETH)
                    c ^= c;
            }
        }
    }
 
    return !b ? !a && !c : a == 0;
}

Originally Posted by vart

Code:

if year is divisible by 400 then
   is_leap_year
// snipped

I was thinking that I should test for is divisible by 4 first because that's the most common thing that will say if it's a leap year or not (before checking for century years).

Edit: You think refactoring would be better? To avoid the loop? Not sure if that will work, but I'll look into that.

Firstly, be sure that your code actually needs to be optimised. You can do that by running your program with a profiler, which will give you an idea of where your program is using its time. If it's spending only 1% of its time in your leapyear function, and 99% elsewhere, there's hardly any reason to optimise it. Similarly, if you're writing a smaller program and it terminates successfully in a few nanoseconds, you'd just be wasting your time.

If it's necessary to optimise this function, you can figure out the range you're most likely going to use (perhaps a few thousand years before the current year and a few thousand years after), then precompute the return values like so:

Code:

#include <stdio.h>

enum {
	BASE = 1584,
	THRESHOLD = 10000
};


static unsigned char tab[THRESHOLD - BASE];


int leapyear_slow(int y)
{
	return !(y % 400) || (y % 100 && !(y % 4));
}


int leapyear(int y)
{
	return y < BASE ? 0 :
	       y < THRESHOLD ? tab[y - BASE] : leapyear_slow(y);
}


void gen(void)
{
	for (int i = 0; i < sizeof tab; i++)
		tab[i] = leapyear_slow(i + BASE);
}


int main(void)
{
	const char *s[] = { "not leap year", "leap year" };
	int n;


	for (gen(); scanf("%d", &n) == 1; puts(s[leapyear(n)]))
		;
	return 0;
}

If you need a larger range, you can save space by packing CHAR_BIT return values into each character, and you can save time by computing the values before the programs interpretation, perhaps by writing the hex values to a text file then #including it into your initialiser list like so:

Code:

static unsigned char tab[THRESHOLD - BASE] = {
#include "leapyears.txt"
};

Originally Posted by oogabooga

The OP is joking here (surely).
The mods should keep an eye out.

??????

It works fine as far as I can tell. Just a bit slow.