mersenneforum.org DWT-based calendar
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-04-13, 19:13 #1 ewmayer ∂2ω=0     Sep 2002 República de California 101101100110102 Posts DWT-based calendar 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 2p/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. Last fiddled with by ewmayer on 2007-04-18 at 18:13 Reason: littlemonth ==> smallmonth so terminology is consistent
2007-04-17, 23:49   #2
ewmayer
2ω=0

Sep 2002
República de California

2·13·449 Posts

Quote:
 Originally Posted by Xyzzy
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:
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	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):
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	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...

Last fiddled with by ewmayer on 2007-04-18 at 18:06 Reason: Corrected leap year months (thanks, ppo)

2007-04-18, 08:55   #3
ppo

Aug 2004
italy

11100012 Posts

Quote:
 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: 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 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): 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 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.

2007-04-18, 18:11   #4
ewmayer
2ω=0

Sep 2002
República de California

2×13×449 Posts

Quote:
 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. ;)

 2007-04-19, 13:48 #5 davieddy     "Lucan" Dec 2006 England 2·3·13·83 Posts 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
 2007-04-19, 14:42 #6 davieddy     "Lucan" Dec 2006 England 145128 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
2007-04-19, 22:22   #7
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts

Quote:
 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!

2007-04-19, 22:33   #8
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts

Quote:
 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 = 10base-pi.

Last fiddled with by cheesehead on 2007-04-19 at 22:41

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Unabomber Math 1 2014-04-04 20:19 science_man_88 Lounge 11 2011-06-26 11:13 ET_ Lounge 8 2010-09-02 08:40 ThomRuley Software 2 2004-03-21 15:30 Gary Edstrom Lounge 7 2003-01-13 22:35

All times are UTC. The time now is 11:28.

Tue Nov 30 11:28:00 UTC 2021 up 130 days, 5:56, 0 users, load averages: 1.57, 1.27, 1.08

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.