20070413, 19:13  #1 
∂^{2}ω=0
Sep 2002
República de California
10110110011010_{2} Posts 
DWTbased calendar
This is a cute little way to illustrate one of the basic aspects of the CrandallFagin discrete weighted transform algorithm used by all modern LL test programs  the mixedbased aspect. I prefer that to Crandall's original "irrational base" terminology, because even though the mixed bases give a transformlength 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 Mersennemod 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 mixedbase representation of the LLtest residues.)
A nice way of illustrating how the mixedbased approach works is by costructing a hypothetical calendar using the mixedbase approach to determine the number of days in each month. In such a DWTbased calendar, each month of a year will have either 30 days ("smallmonth") or 31 days ("bigmonth"). So, dust off your dogeared copies of Crandall/Fagin and enjoy the following puzzle: Using the wordsize formula prescribed for Mersennemod DWT in the above paper, specify the number of days in each of the 12 months of a standard 365day 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. Last fiddled with by ewmayer on 20070418 at 18:13 Reason: littlemonth ==> smallmonth so terminology is consistent 
20070417, 23:49  #2  
∂^{2}ω=0
Sep 2002
República de California
2·13·449 Posts 
Quote:
The DWT variablewordsize 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,...,n1. This, for a standard year (p=365, n=12) we have: Code:
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 153122 = 31 Jun 5 153 183 183153 = 30 Jul 6 183 213 213183 = 30 Aug 7 213 244 244213 = 31 Sep 8 244 274 274244 = 30 Oct 9 274 305 305274 = 31 Nov 10 305 335 335305 = 30 Dec 11 335 365 365335 = 30 Code:
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 153122 = 31 Jun 5 153 183 183153 = 30 Jul 6 183 214 214183 = 31* Aug 7 214 244 244214 = 30* Sep 8 244 275 275244 = 31* Oct 9 275 305 305275 = 30* Nov 10 305 336 336305 = 31* Dec 11 336 366 366336 = 30 We now return the podium to the crickets... Last fiddled with by ewmayer on 20070418 at 18:06 Reason: Corrected leap year months (thanks, ppo) 

20070418, 08:55  #3  
Aug 2004
italy
1110001_{2} Posts 
Quote:
This gives a nice pattern for a leap year: 31,30,31,30,.....31,30 days. Regards, Pierpaolo. 

20070418, 18:11  #4  
∂^{2}ω=0
Sep 2002
República de California
2×13×449 Posts 
Quote:
Thanks for giving the poor overworked crickets a brief rest. ;) 

20070419, 13:48  #5 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
My assemblerfriendly 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 = acc12 ELSE month(n)=30 NEXT 
20070419, 14:42  #6 
"Lucan"
Dec 2006
England
14512_{8} Posts 
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 
20070419, 22:22  #7  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
Quote:


20070419, 22:33  #8 
"Richard B. Woods"
Aug 2002
Wisconsin USA
1E0C_{16} Posts 
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_{basepi}.
Last fiddled with by cheesehead on 20070419 at 22:41 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
On crt based factorization?  Unabomber  Math  1  20140404 20:19 
Calendar math  science_man_88  Lounge  11  20110626 11:13 
Mersenneforum calendar  ET_  Lounge  8  20100902 08:40 
Prime95 on NTbased OS  ThomRuley  Software  2  20040321 15:30 
4 checkins in a single calendar month from a single computer  Gary Edstrom  Lounge  7  20030113 22:35 