Databases
StackOverflow2013
Postsdbo
POEfficient algorithm for converting number of days to years (including leap years)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POEfficient algorithm for converting number of days to years (including leap years)
    primarykey
    data
    text
    <h2>The problem</h2> <p>I am writing a class for holding dates in c++, and I found the following problem:</p> <p>I have a number of days <code>N</code> since a reference date (in my case that would be Jan 1, 0001 AD), including the leap days that passed since the reference day. <strong>How can I convert this number to a year <code>Y</code>, month <code>M</code> and day <code>D</code> efficiently</strong>?</p> <p>I would like to do this as efficiently as possible, so the best implementation would obviously have O(1) complexity.</p> <p>The next sections will explain some of the things I already learned.</p> <h2>Leap years</h2> <p>To determine if a year is leap or not, there are a few rules:</p> <ol> <li>Years which are divisible by 4 are leap</li> <li>Exception to rule 1: years that are divisible with 100 are not leap</li> <li>Exception to rule 2: years that are divisible with 400 are leap</li> </ol> <p>This would translate in code like this:</p> <pre><code>bool IsLeapYear(int year) { // Corrected after Henrick's suggestion if (year % 400 == 0) return true; if ((year % 4 == 0) &amp;&amp; (year % 100 != 0)) return true; return false; } </code></pre> <p>An efficient method to calculate how many years are leap before an year would be:</p> <pre><code>int LeapDaysBefore(int year) { // Years divisible by 4, not divisible by 100, but divisible by 400 return ((year-1)/4 - (year-1)/100 + (year-1)/400); } </code></pre> <h2>Calculating the month</h2> <p>Once I find the year, I can calculate how many days there are until the current year, and I can subtract this number from N. This will give me the day of the year.</p> <p>Keeping a table with the day number on which every month starts, we can easily calculate the month. I also created a function which will add 1 if the year is leap, and the month is greater or equal to 2.</p> <pre><code>// What day each month starts on (counting from 0) int MonthDaySt[] = { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 }; int MonthDayStart(int month, bool leap) { if (leap &amp;&amp; month &gt;= 2) return MonthDaySt[month]+1; return MonthDaySt[month]; } </code></pre> <h2>My idea</h2> <p>My algorithm is pretty complicated, and it looks like this:</p> <pre><code>void GetDate(int N, int &amp;Y, int &amp;M, int &amp;D) { int year_days; // Approximate the year, this will give an year greater or equal // to what year we are looking for. Y = N / 365 + 1; // Find the actual year, counting leap days do { Y--; // Calculate the actual number of days until the // approximate year year_days = Y * 365 + LeapDaysBefore(year); } while (year_days &gt; N); // Add 1, because we start from year 1 AD (not 0) Y++; // Calculate month uint64_t diff = N - year_days; // Will give us the day of the year bool leap = IsLeapYear(Y); // Is current year leap? // Use table to find month M = 0; while (MonthDayStart(M, leap) &lt;= diff &amp;&amp; M &lt;= 12) M++; // Calculate day D = diff - MonthDayStart(M - 1, leap) + 1; } </code></pre> <p>The function may have a few bugs (for example, it didn't work when N was 0).</p> <h2>Other notes</h2> <p>I hope that my algorithm is still correct, because I made some changes from the original for this question. If I missed something, or something was wrong, let me know to modify it. And sorry for the long question.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USTibi
    1. USTibi
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POEfficient algorithm for converting number of days to years (including leap years)
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POEfficient algorithm for converting number of days to years (including leap years)
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POEfficient algorithm for converting number of days to years (including leap years)
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHave you thought about dividing the number of years by 400, then consider every 100 years, then find the exact year?
      singulars
      1. POEfficient algorithm for converting number of days to years (including leap years)
      1. USnhahtdh
    2. CO@nhahtdh Yes, I thought of that, but didn't implement it yet.
      singulars
      1. POEfficient algorithm for converting number of days to years (including leap years)
      1. USTibi
    3. COConsult the source: http://emr.cs.uiuc.edu/home/reingold/calendar-book/index.shtml
      singulars
      1. POEfficient algorithm for converting number of days to years (including leap years)
      1. USHigh Performance Mark
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload