Just for the record, Ray Polivka's article in the latest Vector contains a note by the editor referring to an earlier article in Vector by Ray Cannon (When Is Easter?), which gives algorithms in APL and entertainingly goes into the history. Here is a link to it: http://vector.org.uk/archive/v103/cannon103_67.htm
Ian Clark On Mon, Sep 27, 2010 at 9:23 PM, Dan Bron <[email protected]> wrote: > "Computus" is the calculation of the date of Easter in the Christian > calendar [1]. It is a notoriously dirty problem, arising from the tension > between ecclesiastical and astronomical requirements [2]. > > > > Easter has been much studied in the APL community; I won't give a > bibliography but I'll direct your attention to the recent Vector (vol 22.4). > In particular to [2], where Ray Polivka presents a definition of Easter as a > table of sequential equations: > > > > Step Dividend Divisor Quotient Remainder > > 1. x 19 - a > > 2. x 100 b c > > 3. b 4 d e > > 4. 8b+13 25 g - > > 5. 19a+b-d-g+15 30 - h > > 6. a+11h 319 u - > > 7. c 4 i k > > 8. 2e+2i-k-h+u+32 7 - q > > 9. h-u+q+90 25 n - > > 10. h-u+q+n+19 32 - p > > > > (he got it from an 19th century /Nature/ article, by way of T.H. O'Beirne in > "Puzzles and Paradoxes"). > > > > The nice thing about this approach is that it makes the "dirty" problem of > Easter clean, in the sense that there are no exceptions; given x, the year > in question, x,n,p is the date of Easter in that year. No ifs, ands, buts. > Elegant. > > > > Now, of course, if one stares at the Dividend and Divisor columns, the dirty > details reappear. But one needn't do that! Because we're given this data > as a table, we can treat it as an (opaque) input. That is, with a little > effort, we can have an exception-free table-driven definition of Easter. > > > > I say little effort because J has a number of facilities that make defining > such a computus straightforward. In fact, indirect assignment, dynamic > evaluation, and the primitive #: are basically all you need. For example, > using the definition of easter in [3]: > > > > easter 2000 > > 2000 4 23 > > > > easter 2000+i.10 > > 2000 4 23 > > 2001 4 15 > > 2002 3 31 > > 2003 4 20 > > 2004 4 11 > > 2005 3 27 > > 2006 4 16 > > 2007 4 8 > > 2008 3 23 > > 2009 4 12 > > > > Note that the heart of this definition is merely: > > > > for_entry. B do. > > (H) =. entry > > (Quotient ; Remainder) =. Divisor (#:~ 0&,)~&". eval Dividend > > end. > > > > where H is the header of the table, and B its body. Using indirect > assignment, we're able to define Quotient, Remainder, Divisor, and Dividend > as appropriate for each entry in the table. Dynamic evaluation (".) and > another indirect assignment allows us to define the temporary variables > named in the entry, which will be available for evaluation of subsequent > entries, and for the result of the verb, which is precisely x,n,p . > > > > Coupled with the idiom (0,x) #: y for the quotient & reminder of y wrt x, > and I find this definition simple and elegant. However, there is always > room for improvement: > > > > #1 The current definition of easter requires that that verb be > > explicitly applied at rank 0. > > > > #2 For ". y to work, y must be a valid J sentence. For the > > divisor, this is ok (the divisor is just a constant > > scalar integer). But the dividend is a different story. > > > > So, 1st challenge: > > > > Modify or extend the definition of easter to handle arbitrarily > > ranked arrays, natively (i.e. no "0). > > > > Remember, the goal is to keep the definition of easter as transparent > > as possible, and let the table COMPUTUS speak for itself. > > > > That means: keep it simple! Try not to let programming (i.e. J) > > issues intrude on this simplicity (which is actually a good > > argument to keep "0). > > > > In re: #2, the dividend is close to a valid J sentence, but no cigar. > Consider 2e+2i-k-h+u+32 . Here, > > > > #i Multiplication is implied with juxtaposition, > > whereas in J, all operations are made explicit, and > > > > #ii order of evaluation is backwards w.r.t. a J sentence. > > > > We can address these issues with a little pre-processor, which I named eval > : > > > > eval =: poly&.>/@:( <mailto:/@:(%3c;.2~> <;.2~ 1: _1} >>/\.@:e.&'0123456789' )&>&r2l&.;: > > r2l =. |.&( (<,'-') sr (<'-~') ) > > poly =. '(' , [ , '*' , ')' ,~ ] > > > > This verb has some neat features: > > > > it operates &.;: > > > > it addresses #ii by reversing (|.) the sentence and commuting (~) the > > (non-associative) operations > > > > it addresses #i by leveraging an obscure feature of / . > > Specifically, the identity f/y <==> y when 1=#y > > (which I've always found interesting, but never put > > to use before). > > > > But I'm still not satisfied with it. I think its complexity besmirches the > simplicity of the overall solution (which was its original attraction). > Also, it's not as general as I imagined. Try applying it to the dividends > in the 2nd table presented by Ray Polivka (from O'Beirne). > > > > So, 2nd challenge: > > > > Can you write a better eval ? > > > > I would be particularly impressed with solutions that used the dyad ;: to > lex & parse the dividend (where, in general, the dividend can contain > parens, as in Ray's 2nd table). > > > > -Dan > > > > [1] Wikipedia on Computus: > > http://en.wikipedia.org/wiki/Computus > > > > [2] Vector 24.2, "Ten divisions to Easter", Ray Polivka: > > http://www.vector.org.uk/?vol=24 > <http://www.vector.org.uk/?vol=24&no=2&art=polivka> &no=2&art=polivka > > > > [3] Table-driven exception-free computus: > > > > NB.======================================================================= > > NB. Utility: scalar replace. > > sr =: conjunction def ' =&m`(,:&n) } ' > > > > NB. Easter calculation table, copy/pasted from NB. > http://www.vector.org.uk/?vol=24 > <http://www.vector.org.uk/?vol=24&no=2&art=polivka> &no=2&art=polivka > > COMPUTUS =: -`dm 1 :'({.m)sr({:m)' }."1 <;._1;._2 noun define -. ' ' > > Step Dividend Divisor Quotient Remainder > > 1. x 19 - a > > 2. x 100 b c > > 3. b 4 d e > > 4. 8b+13 25 g - > > 5. 19a+b-d-g+15 30 - h > > 6. a+11h 319 u - > > 7. c 4 i k > > 8. 2e+2i-k-h+u+32 7 - q > > 9. h-u+q+90 25 n - > > 10. h-u+q+n+19 32 - p > > ) > > > > NB. Make ET executable > > easter =: dyad define > > 'H B' =. ({. ,&< }.) y NB. Header and body of equation table > > > > for_entry. B do. > > (H) =. entry > > (Quotient ; Remainder) =. Divisor (#:~ 0&,)~&". eval Dividend > > end. > > > > x,n,p > > ) > > > > NB. Divisor evaluation: reverse sentence, commute operations, NB. > parenthesize multiplication > > eval =: poly&.>/@:( <mailto:/@:(%3c;.2~> <;.2~ 1: _1} >>/\.@:e.&'0123456789' )&>&r2l&.;: > > r2l =. |.&( (<,'-') sr (<'-~') ) > > poly =. '(' , [ , '*' , ')' ,~ ] > > > > NB. Exported functions > > eval =: eval f. > > easter =: $:&COMPUTUS : easter"0 _ f. > > NB.======================================================================= > > > > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
