Feeds:
Posts
Comments

Posts Tagged ‘Leap Year’

Perhaps one of the least exciting things to happen in 2008 was the failure of the 30GB Microsft Zune yesterday. But springing back into life certainly is the most interesting thing I’ve read this year!

If you have no idea what I’m talking about read this. It concerns an algorithm to calculate the number of days and years that have passed since 1980, which attempts to take leap years into account. The problem is that the algorithm enters an infinite loop on the last day of a leap year, which is why 30GB Zunes broke yesterday on 31st December 2008, but miraculously started working again today on 1st January 2009.

Now I know that quite a few people have posted their fixes on Reddit, but I wanted to write my own. Here it is in a neat little program that runs on its own. ¬†Once you’ve compiled it, you can run it as: –

./days_years g|b days

Where g is the good (correct) algorithm implemented by yours truly, and b is the bad (erroneous) algorithm implemented by Freescale/Microsoft.

days is the number of days that have elapsed since 1980. Entering 10593 will recreate the 31st December 2008 scenario.

I decided to implement a recursive algorithm to show that we can prove it will always halt. Proving its correctness is probably a good idea for something described as Real-time clock (RTC) routines! It could be done by hand as an induction or using a tool!

However, if I was in charge of programming this routine I would probably scrap the algorithm completely and hard-code all the leap years between 1980 and 2050. After all, no one is going to be using their Zune after that length of time.

There are only 18 leap years, which are the exceptions – so why worry about algorithms and termination clauses?

Read Full Post »