DWT-based calendar

[ewmayer]

This is a cute little way to illustrate one of the basic aspects of the Crandall-Fagin discrete weighted transform algorithm used by all modern LL test programs - the mixed-based aspect. I prefer that to Crandall's original "irrational base" terminology, because even though the mixed bases give a transform-length effect which is in some sense equivalent to that which would obtain if an irrational base 2^p/n were able to be used, at no point in the Mersenne-mod DWT does one actually *use* irrational wordsizes - one instead uses a clever mix of just *two* wordsizes, having floor(p/n) and ceiling(p/n) bits. (A common colloquialism here is to call these the "smallwords" and "bigwords", respectively, of the mixed-base representation of the LL-test residues.)

A nice way of illustrating how the mixed-based approach works is by costructing a hypothetical calendar using the mixed-base approach to determine the number of days in each month. In such a DWT-based calendar, each month of a year will have either 30 days ("smallmonth") or 31 days ("bigmonth"). So, dust off your dog-eared copies of Crandall/Fagin and enjoy the following puzzle:

Using the wordsize formula prescribed for Mersenne-mod DWT in the above paper, specify the number of days in each of the 12 months of a standard 365-day year. Now repeat the exercise for a leap year.

Can you identify any obvious practical drawbacks to divvying up the days in a year this way?

I'd like to ask folks already familiar with the DWT to feel free to work the puzzle and provide hints to those less so, but to please refrain from giving the answer for at least (say) a week from today. Thanks.

[ewmayer]

Originally Posted by Xyzzy

<sound of crickets chirping>

Indeed, the massive and forum-disrupting popularity of this puzzle prompts me to waive the one-week waiting period and give the answer, in hopes that this will provoke further stimulating discussion, like we've had so far. :(

The DWT variable-wordsize scheme uses one of two word sizes for each digit, or in our present example, number of days for each month:

#days = ceil[(i+1)*p/n] - ceil[i*p/n], where i=0,...,n-1.

This, for a standard year (p=365, n=12) we have:

Month:	i   [i*p/n] [(i+1)*p/n]    #days
-----	--	---	---	------------
Jan	0	  0	 31	 31-  0 = 31
Feb	1	 31	 61	 61- 31 = 30
Mar	2	 61	 92	 92- 61 = 31
Apr	3	 92	122	122- 92 = 30
May	4	122	153	153-122 = 31
Jun	5	153	183	183-153 = 30
Jul	6	183	213	213-183 = 30
Aug	7	213	244	244-213 = 31
Sep	8	244	274	274-244 = 30
Oct	9	274	305	305-274 = 31
Nov	10	305	335	335-305 = 30
Dec	11	335	365	365-335 = 30

For a leap year, we have p = 366, with the resulting DWT-based calendar (* indicates month whose length differs from same month in the standard-year calendar):

Month:	i   [i*p/n] [(i+1)*p/n]    #days
-----	--	---	---	------------
Jan	0	  0	 31	 31-  0 = 31
Feb	1	 31	 61	 61- 31 = 30
Mar	2	 61	 92	 92- 61 = 31
Apr	3	 92	122	122- 92 = 30
May	4	122	153	153-122 = 31
Jun	5	153	183	183-153 = 30
Jul	6	183	214	214-183 = 31*
Aug	7	214	244	244-214 = 30*
Sep	8	244	275	275-244 = 31*
Oct	9	275	305	305-275 = 30*
Nov	10	305	336	336-305 = 31*
Dec	11	336	366	366-336 = 30

So you can see that the practical problem with this scheme is that the one extra day in the leap year leads to *five* months having changed lengths - it would make much more practical sense to just add a day to one of the 30-day months (e.g. December), analogously to what is done to 28-day February in practice.

We now return the podium to the crickets...

[ppo]

Originally Posted by ewmayer

Indeed, the massive and forum-disrupting popularity of this puzzle prompts me to waive the one-week waiting period and give the answer, in hopes that this will provoke further stimulating discussion, like we've had so far. :(

The DWT variable-wordsize scheme uses one of two word sizes for each digit, or in our present example, number of days for each month:

#days = ceil[(i+1)*p/n] - ceil[i*p/n], where i=0,...,n-1.

This, for a standard year (p=365, n=12) we have:

Month:	i   [i*p/n] [(i+1)*p/n]    #days
-----	--	---	---	------------
Jan	0	  0	 31	 31-  0 = 31
Feb	1	 31	 61	 61- 31 = 30
Mar	2	 61	 92	 92- 61 = 31
Apr	3	 92	122	122- 92 = 30
May	4	122	153	153-122 = 31
Jun	5	153	183	183-153 = 30
Jul	6	183	213	213-183 = 30
Aug	7	213	244	244-213 = 31
Sep	8	244	274	274-244 = 30
Oct	9	274	305	305-274 = 31
Nov	10	305	335	335-305 = 30
Dec	11	335	365	365-335 = 30

For a leap year, we have p = 366, with the resulting DWT-based calendar (* indicates month whose length differs from same month in the standard-year calendar):

Month:	i   [i*p/n] [(i+1)*p/n]    #days
-----	--	---	---	------------
Jan	0	  0	 31	 31-  0 = 31
Feb	1	 31	 61	 61- 31 = 30
Mar	2	 61	 92	 92- 61 = 31
Apr	3	 92	122	122- 92 = 30
May	4	122	153	153-122 = 31
Jun	5	153	183	183-153 = 30
Jul	6	183	214	214-183 = 31*
Aug	7	214	244	244-214 = 30*
Sep	8	244	275	275-244 = 31*
Oct	9	275	305	305-275 = 31
Nov	10	305	336	336-305 = 30
Dec	11	336	366	366-336 = 30

So you can see that the practical problem with this scheme is that the one extra day in the leap year leads to *three* months having changed lengths - it would make much more practical sense to just add a day to one of the 30-day months (e.g. December), analogously to what is done to 28-day February in practice.

We now return the podium to the crickets...

I like it, but for a leap year I believe that there is a mistake for October and November: 305-275 gives 30 days for October, and 336-305 gives 31 for November.
This gives a nice pattern for a leap year: 31,30,31,30,.....31,30 days.
Regards, Pierpaolo.

[ewmayer]

Originally Posted by ppo

I like it, but for a leap year I believe that there is a mistake for October and November: 305-275 gives 30 days for October, and 336-305 gives 31 for November.
This gives a nice pattern for a leap year: 31,30,31,30,.....31,30 days.
Regards, Pierpaolo.

Thanks for pointing out the goof, Pierpaolo - that's what I get for the copy/paste/modify method of doing things by hand. Indeed, the corrected simple-alternating leap year pattern is more along the lines of what one would expect, since a leap year has an equal number of bigmonths and smallmonths, i.e. things should be symmetric in that regard. Of course in one sense things are worse for the DWT-based scheme, since now a whopping five months have changed between a 365 and 366-day year. I've corrected the post.

Thanks for giving the poor overworked crickets a brief rest. ;)

[davieddy]

My assembler-friendly algorithm for choosing 5 months
out of twelve to have 31 days instead of 30 goes like this:

-1>= acc(umulator) >=-12
FOR n = 1 to 12
acc = acc+5
IF carry THEN month(n) =31: acc = acc-12 ELSE month(n)=30
NEXT

[davieddy]

I was glad to note the confirmation that " irrational base"
meant what I thought it did,
What does a number to the base pi (say) look like???

David

[cheesehead]

Originally Posted by ewmayer

This is a cute little way to illustrate one of the basic aspects of the Crandall-Fagin discrete weighted transform algorithm used by all modern LL test programs - the mixed-based aspect.

< snip >

A nice way of illustrating how the mixed-based approach works is by costructing a hypothetical calendar using the mixed-base approach to determine the number of days in each month.

I was delighted to see that you'd posted this!

[cheesehead]

Originally Posted by davieddy

What does a number to the base pi (say) look like???

First, one has to decide what the digits are going to be. The obvious choice is {0,1,2,3}, but there are other possibilities, such as digits whose value is e/pi or pi/2, that make the addition and multiplication tables more complex. Pi itself can't be a digit, because pi = 10_base-pi.