11 ms·
A Formula for the Number of Days in Each Month
- joezydeco 12y agoGreat start. Now let's add leap years. =)
- _lce0 12y agobut that's trival, isn't that already solved? function f(x) { return 28 + maybeLeap(x) + (...); } I remember it's something related with "(x % 4) == 0" and "not ends_with(00)"
- agrona 12y agoExcept for every 400th year.
- _lce0 12y agohow about this? leap = function(x) { if ((x % 4) != 0) { return 0; } return Number( (x % 100) != 0 || (x % 400) == 0 ); } function(x) { return 28 + leap(x) + (...) };
- joezydeco 12y agoOP is trying to express the day count as a pure math expression. maybeLeap() probably won't do here.
- sparkie 12y agodays y m = 28 + (m + (m `div` 8)) `mod` 2 + 2 `mod` m + 2 * (1 `div` m) + ((2 `div` m) `mod` 2) * (leap y) where leap y = multiple 4 y - multiple 100 y + multiple 400 y where multiple int y = ((y + (int - 1)) `mod` int + 1) `div` int
- USNetizen 12y agoI believe Zeller's Congruence had already solved this, no? Zeller's is based upon calculating the day of the week, but it also calculates days in the month and accounts for leap years. Plus, it's been around since the 19th century and is used in many major programming languages to calculate date (its implementation is sometimes a first year Comp Sci course project for introductory programming): http://en.wikipedia.org/wiki/Zeller%27s_congruence http://en.wikipedia.org/wiki/Zeller%27s_congruence For a programming example that does this same thing: https://github.com/mwhawkins/JavaZellers https://github.com/mwhawkins/JavaZellers How did this make the front page of HN being a problem which has already been solved and well documented for almost 200 years? Not to knock the author, as they put in some time apparently, but was just curious.
- cristianpascu 12y agoThe age of the solution and number of people knowing about it... Well. :)
- burkaman 12y agoWell, a lot of people have never heard of Zeller's Congruence. Also, the process is kind of interesting, not just the result. That's why that article on deriving the fast inverse square root constant did well here, even though many people already know the result.
- Iazel 12y agoI can't find any way to calculate days in month using Zeller's Congruence °_° That's seems to calculate only the day of the month (and it's awesome!). Even the Java program use a fixed array to output the days in month! XD
- tzs 12y agoIf you give up on February and just resign yourself to treating it as an exception, then the formula in the article, 30 + (x + [x/8])%2, is trivial to compute in your head. Zeller's Congruence is quite a bit harder to do in your head. For mental calculation of day of week, I use a method given in a Martin Gardner book, but this only works for 1900-1999. I'll give a fix to extend it to other centuries. Let Y be the last two digits of the year, let M be the month (1-12), and D be the day of the month (1-31). Let [X] denote the integer part of X. Compute w = [Y/12] + Y%12 + [Y%12/4] Compute w = w + month_offset(M), where month_offset is defined by this table: M month_offset 1 1 2 4 3 4 4 0 5 2 6 5 7 0 8 3 9 6 10 1 11 4 12 6 Compute w = w + D w%7 gives the day of the week, with Saturday being day 0. A couple notes. 1. You can reduce mod 7 as you go. For example, to get the day of the week of 1969-07-16, you could think "[69/12] = 5, add 9 (69%12) giving 14 == 0 mod 7. [9/4] = 2, so we are at 2. Add month_offset(7) == 0, giving 0. Add 16 (D), and we have 3 mod 7, so Wednesday". 2. Month_offset is easy to remember if you think of it this way: 1 4 4 0 2 5 0 3 6 1 4 6 That's 12^2, 5^2, 6^2, and 12^2+2. I don't know why that makes it easy, but Gardner suggested it, and I have not forgotten it in something like 40 years, even though I rarely use it. 3. If the year is a leap year, subtract 1 for dates in January and February. 4. For years in 2000-2099, subtract 1 from the result. For years in 1800-1899, add 2. If you forget what the century correction is, you can work it out in your head. For instance, to find the correction for 20xx, work out the day of week of 1999-12-31: 99=12x8+3, [3/4]=0, month_offset(12)=6, so 8+3+0+6+31==6 mod 7, or Friday. Now work out 2000-01-01 without a century correction: 0=0x12+0, [0/4]=0, month_offset(1)=1. 2000 is a leap year, so need to subtract 1 in January, so we have 0+0+0+0+1-1+1==1 mod 7, so Sunday. However, it should be Saturday since it comes after Friday, and so the century correction must be -1 for 20xx. 5. Gardner's method is really one of the other well known methods (I forget which one) adjusted to make mental calculation easier. Addendum: this is described in chapter 7, "Tricks of Lightning Calculators" from the Martin Gardner collection "Mathematical Carnival".
- doragcoder 12y agoThere was a Hacker News article about why August has 31 days, breaking the 30/31 alternating days. I can't find it but here's an article about it. http://www.infoplease.com/spot/history-of-august.html http://www.infoplease.com/spot/history-of-august.html It just makes it a more interesting formula because of that!
- ChuckMcM 12y agoGreat analysis. The next step would be to see if the code to implement the function can be shorter than 12 bytes (and array of bytes holding the number of days in the month such that f(x) = days_of_month[x]; is longer than the computation. Of course from a pure cycle counting advantage doing it as a calculation will always be faster as memory is slow to access.
- hawkice 12y agoI mean, you have to load the instructions, too. That being said those have pretty intelligent pre-fetching baked in, but if it's the computational bottleneck, you can get the values into registers for the lookup. I'm not sure this post is meant to be a model for good implementation advice, though, performance-oriented or otherwise. Just an interesting tidbit. EDIT: I'm trying to figure out how to write code using registers instead of indexes into memory and it ends up with lots of conditionals instead of basically one instruction. The conversation about speed is... tricky. Can some people who are more expert help out?
- toast0 12y agoIf you want to trade bytes of instructions for bytes of constants, you could store the number of days - 28, so you only need two bits of constant per month.
- saalweachter 12y agoOnce you do that, you can trade your array for a 32-bit integer: f(n) = 28 + ((0x3bbeecc >> n >> n) & 3)
- recursive 12y agoHere's mine. No floating point logic required. let days = (i ^ (i >> 3) | 30) - 1 / (i * 9 % 17) * 2
- arthurcolle 12y agoWhat language would this work in? let looks like ocaml but those don't look like the write syntactical ways to do math stuff IIRC
- tlarkworthy 12y agodoesn't work in JS:- function days2(i) { return (i ^ (i >> 3) | 30) - 1 / (i * 9 % 17) * 2 } 1 30.77777777777778 2 28 3 30.8 4 29 5 30.818181818181817 6 29.333333333333332 7 30.833333333333332 8 30.5 9 29.846153846153847 10 30.6 11 29.857142857142858 12 30.666666666666668
- recursive 12y agoThat makes sense. js doesn't have integer division.
- deleted 12y ago[deleted]
- pzxc 12y agoThirty days hath September April, June, and November All the rest have 31 Except for the very special one. ... The knuckles method, for those who don't know: Make a fist. Start with January on your first knuckle. Counting knuckles AND the gaps between knuckles, so each knuckle is 31 days, the gap between is 30 days (or 28/29 for february). Repeat on the last knuckle before reversing. ... So-- KNUCKLE_gap_KNUCKLE_gap_KNUCKLE_gap_KNUCKLE JAN_feb_MAR_apr_MAY_jun_JUL (repeat last knuckle and reverse) AUG (knuckle repeat)_sep_OCT_nov_DEC (ending on your middle knuckle) ALLCAPS = KNUCKLE = 31 days
- javert 12y agoRe: the knuckle technique. I prefer to simply start over again from the first knuckle, as opposed to reversing direction. It gives you one less thing to remember, since you don't have to remember to repeat on the last knuckle.
- smokey_the_bear 12y agoI learned it that you move onto the other hand.
- bhrgunatha 12y agoMe too and it must mean something that I still use this method from time to time. Why is is so difficult to just remember?
- javert 12y ago> Why is is so difficult to just remember? Probably because there is almost a pattern, but not quite.
- pzxc 12y agoI prefer to reverse, because it emphasizes that there is a double-31 pair of consecutive months which is unique in the pattern and a good thing to know/remember (that both July and August are long months)
- tlarkworthy 12y agomy digital attempt:- function days(m) { return 30 + ((m + (m > 6)) % 2) - 2 * (m == 2) }
- kazagistar 12y agoCompiles down to something like a hundred bytes of code. What a savings!
- svisser 12y agoThe easiest function would be a mapping from 12 input values to 12 output values. For example, see the Collatz conjecture which only defines two cases (but one could have 12): http://en.wikipedia.org/wiki/Collatz_conjecture http://en.wikipedia.org/wiki/Collatz_conjecture
- danbruc 12y ago29 + 2 * ABS(SIGN(month - 2)) - FLOOR(ABS(month - 7.5)) % 2
- Someone 12y agoSimple (warning: I did not verify this result): -( 11 x^11)/907200 +( 163 x^10)/181440 -( 37 x^9 )/1260 +( 13481 x^8 )/24192 -( 2055371 x^7 )/302400 +( 240683 x^6 )/4320 -( 28268521 x^5 )/90720 +( 85774775 x^4 )/72576 -(446998571 x^3 )/151200 +( 46351537 x^2 )/10080 -( 221017 x )/56 +1416 That is a nice continuous, infinitely differentiable function. Source: http://www.wolframalpha.com/input/?i=interpolating+polynomial+calculator&f1=%7B31%2C28%2C31%2C30%2C31%2C30%2C31%2C31%2C30%2C31%2C30%2C31%7D&f=InterpolatingPolynomialCalculator.data_%7B31%2C28%2C31%2C30%2C31%2C30%2C31%2C31%2C30%2C31%2C30%2C31%7D&a=*FVarOpt.1-_***InterpolatingPolynomialCalculator.data--.***InterpolatingPolynomialCalculator.data2---.*-- http://www.wolframalpha.com/input/?i=interpolating+polynomia... To get something more impressive, I would use the discrete Fourier transform. That leads to http://en.wikipedia.org/wiki/Trigonometric_interpolation http://en.wikipedia.org/wiki/Trigonometric_interpolation. That gives you a nice formula with lots of sines and cosines.
- danbruc 12y agoI tried DFT, the result is not pleasant and there is no really obvious way to generate the coefficients with a compact formula.
- Someone 12y agoYou shouldn't believe everything you read on the Internet/I guess I should have added a smiley.
- danbruc 12y agoI tried it well before you wrote your comment because I hoped that the alternating pattern would yield something short but February messes everything up.
- repsilat 12y agoThat's a shame, it'd be nice to have a formula that "wrapped around" properly. I've been happy with the rhyme for a while. I can't remember it properly (in my head it ends "all the rest have strawberry jam, except my grandmother who rides a bicycle"), but it's obviously enough. Now that I see it all laid out, though, I wonder if I can do better -- "Odd is 31 days to July, then it flips." Now the people in school counting on their knuckles all makes sense.
- Dylan16807 12y agoGreat, in your distaste for the method that can involve knuckles, you have recreated it exactly. 1. alternate 31 and 30 2. reset in month 8 3. alter feb to 28 In my mind using modulus and floor in a mathematical formula is no more valid than using cases. A clever formula would avoid all of them.
- danbruc 12y agoROUND((61 + COS(3 * month - 22.5)) / 2) Admittedly rounding is still cheating but it allows compacter solutions than being spot-on every time. Handling February is left as an exercise for the reader.
- jcrites 12y ago> In my mind using modulus and floor in a mathematical formula is no more valid than using cases Agreed. Using floor it seems like you can construct a function that's effectively defined piecewise, by constructing a floor expression that's zero outside of a specified input domain, and 1 within the domain. Then you multiply the floor expression by the piecewise expression that you'd use to define a piecewise function over that domain. Nevertheless I found the article to be an interesting read on mathematical reasoning - a thought process for designing functions with particular behavior. Is there a rigorous way of describing why mod and floor seem like cheating in a way, aside from the fact that they can be used to construct piecewise functions? Is the ideal hack in this scenario a continuous, smooth function? (And something more interesting than the result of polynomial interpolation?)
- thaumasiotes 12y ago> Using floor it seems like you can construct a function that's effectively defined piecewise, by constructing a floor expression that's zero outside of a specified input domain, and 1 within the domain. Then you multiply the floor expression by the piecewise expression that you'd use to define a piecewise function over that domain. And you can fit a polynomial the same way by (using the example at hand) defining f(x) = c_1(x-2)(x-3)...(x-12) + c_2(x-1)(x-3)...(x-12) + c_3(x-1)(x-2)...(x-12) [but the (x-3) factor is missing!] + . . . + . . . + . . . + c_12(x-1)(x-2)...(x-11) And then choosing c_1 such that the c_1 term is equal to 31 when x=1, c_2 such that the c_2 term is equal to 28 when x=2, and so forth. You'll get a well-defined polynomial, impeccably "mathematical" -- in fact, you should get the polynomial listed in Someone's comment (since there should only be one 11th-degree polynomial passing through those 12 points). The traditional way to fit a polynomial to points is by reducing a matrix, linear-algebra style, but this approach is equivalent and, as you can see, amounts to nothing more than defining several functions which are zero except at the point of interest, and then scaling them to take the proper value at the point of interest. Why is that more "valid" than using a modulus? Frankly, I'm much more concerned by the OP using "2 mod x" when 1 is a legal value for x.
- OMGWTF 12y ago// without floats, multiplication, division, modulo: int result = (30|m^(m>>3)) - (((m^13)+1)>>4<<1);
- grandalf 12y agomeant to upvote, accidentally downvoted.
- xxxyy 12y agoAnybody knows the reason behind August having 31 days? This is the source of the complexity of the days-in-a-month problem. All I can find is this legend, which could even be true. http://timesofindia.indiatimes.com/home/stoi/Why-does-February-have-28-days-and-July-and-August-31-days/articleshow/2677672.cms http://timesofindia.indiatimes.com/home/stoi/Why-does-Februa...
- GFK_of_xmaspast 12y agohttp://en.wikipedia.org/wiki/Julian_calendar#Sacrobosco.27s_theory_on_month_lengths http://en.wikipedia.org/wiki/Julian_calendar#Sacrobosco.27s_...
- freework 12y agodef days_in_month(month_num): if month_num in [1, 3, 5, 7]: return 31 elif month_num in [4, 6, 9, 11]: return 30 return 28
- btbuildem 12y agoYour solution (which does not account for leap years, btw) simplifies to: def days(month): return [31,28,31,30,31,30,30,31,30,31,30,31][month]
- thaumasiotes 12y agoI can't wait for 0/0/2015 ;)
- btbuildem 12y agoHa, nice one. I'm mixing my Es with my Ps
- kayamon 12y agodays = 28 + ((0x3bbeecc>>(month*2))&3);
- danieltillett 12y agoWhere does this come from?
- OMGWTF 12y agoThe basic idea is to encode the array within a single integer: 0 + [anything, 31,28,31,30,31,30,31,31,30,31,30,31] 28 + [anything, 3, 0, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3] 00, 11,00,11,10,11,10,11,11,10,11,10,11 reverse: 11,10,11,10,11,11,10,11,10,11,00,11, 00 0011 1011 1011 1110 1110 1100 1100 0x 3 b b e e c c We have 4 possible values in the array, so we need 2 bits per value. We have one dummy value + 12 required values, so we need a total of 2*13 = 26 bits which fits easily into a 4 byte integer (either 32 bits unsigned or 31 bits signed). To retrieve one element from the "array", we need to shift our constant 2 bits per month or twice by the numer of months. Then we need to mask everything but the lowest 2 bits (&3).
- danieltillett 12y agoGreat explaination. This is the sort of post that makes me love HN.
- bartbes 12y agoIt basically just stores [3, 0, 3, 2, ...] as 2-bit numbers, and the shift then corresponds to indexing.
- bjconlan 12y agoWow that's very clever!
- byuu 12y agoI like yours for the minimum number of operations needed: 28+((0x3bbeecc>>(m*2))&3) But here's my own attempt anyway, which wins on number of characters typed =) 30+(m&1^m>7)-m*(m==2)
- grandalf 12y agoWhat's the formula for the number of days in a month+year (so that it calculates leap years formulaically too?
- shitlord 12y agoWas I the only one who expected to see a Dirac delta function used for February? I was pleasantly surprised.
- allannienhuis 12y agoJavascript: var f = function(i){return new Date(2014,i,0).getDate();}; JSON.stringify([1,2,3,4,5,6,7,8,9,10,11,12].map(f)) == JSON.stringify([31,28,31,30,31,30,31,31,30,31,30,31]); :P
- mikesmith 12y agoThirty days have September, April, June, and November. All the rest have 31, Except for February all alone, It has 28 each year, but 29 each leap year.
- mikesmith 12y agoThirty days have September, April, June, and November. All the rest have 31, Except for February all alone, It has 28 each year, but 29 each leap year.
- gckruger 12y agoThis is awesome. Well done, OP.
- gordaco 12y agoFor something more or less related, check out the calculation of the date of Easter: http://en.wikipedia.org/wiki/Computus http://en.wikipedia.org/wiki/Computus. Some versions, like Gauss' algorithm, also relied heavily on moduli.
- mariodiana 12y agoA perfect illustration of why a simple lookup table is often the better implementation. I'll stick to the knuckles method—thank you very much.
- no_gravity 12y agoCan be shortened to 28+(x+~~(x/8))%2+2%x+2*~~(1/x)
- xclojure 12y agoWhy is it any better/faster than a simple switch case like this in Clojure: #(case % 1 31 2 28 3 31 4 30 5 31 6 30 7 31 8 31 9 30 10 31 11 30 12 31)
- bvrlt 12y agoOr in C: f(int m) { return [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31][m] } The OP didn't claim it was better than anything, it's just a nice exercise in style!
- arsenerei 12y ago#([31 28 31 30 31 30 31 31 30 31 30 31] (dec %)) > Why is it any better/faster than a simple switch case like this in Clojure It's not about better or faster. It's fun to think of things like this. :)
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]