title: Why is gmtime implemented this way?
body: <p>I happened across the source for Minix's gmtime function. I was interested in the bit that calculated the year number from days since epoch. Here are the guts of that bit:</p>
  
  <p><a href="http://www.raspberryginger.com/jbailey/minix/html/gmtime_8c-source.html" rel="noreferrer">http://www.raspberryginger.com/jbailey/minix/html/gmtime_8c-source.html</a></p>
  
  <p><a href="http://www.raspberryginger.com/jbailey/minix/html/loc__time_8h-source.html" rel="noreferrer">http://www.raspberryginger.com/jbailey/minix/html/loc__time_8h-source.html</a></p>
  
  <pre><code>#define EPOCH_YR 1970
  #define LEAPYEAR(year) (!((year) % 4) &amp;&amp; (((year) % 100) || !((year) % 400)))
  #define YEARSIZE(year) (LEAPYEAR(year) ? 366 : 365)
  
  int year = EPOCH_YR;
  
  while (dayno &gt;= YEARSIZE(year)) {
      dayno -= YEARSIZE(year);
      year++;
  }
  </code></pre>
  
  <p>It looks like the algorithm is O(n), where n is the distance from the epoch. Additionally, it seems that LEAPYEAR must be calculated separately for each year &ndash; dozens of times for current dates and many more for dates far in the future. I had the following algorithm for doing the same thing (in this case from the ISO-9601 epoch (Year 0 = 1 BC) rather than UNIX epoch):</p>
  
  <pre><code>#define CYCLE_1   365
  #define CYCLE_4   (CYCLE_1   *  4 + 1)
  #define CYCLE_100 (CYCLE_4   * 25 - 1)
  #define CYCLE_400 (CYCLE_100 *  4 + 1)
  
  year += 400 * (dayno / CYCLE_400)
  dayno = dayno % CYCLE_400
  
  year += 100 * (dayno / CYCLE_100)
  dayno = dayno % CYCLE_100
  
  year +=   4 * (dayno / CYCLE_4)
  dayno = dayno % CYCLE_4
  
  year +=   1 * (dayno / CYCLE_1)
  dayno = dayno % CYCLE_1
  </code></pre>
  
  <p>This runs in O(1) for any date, and looks like it should be faster even for dates reasonably close to 1970.</p>
  
  <p>So, assuming that the Minix developers are Smart People who did it their way for a Reason, and probably know a bit more about C than I do, why?</p>