mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-04-13, 19:13   #1
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

101101100110102 Posts
Default 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
ewmayer is offline   Reply With Quote
Old 2007-04-17, 23:49   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·13·449 Posts
Default

Quote:
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:
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)
ewmayer is offline   Reply With Quote
Old 2007-04-18, 08:55   #3
ppo
 
ppo's Avatar
 
Aug 2004
italy

11100012 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
ppo is offline   Reply With Quote
Old 2007-04-18, 18:11   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×13×449 Posts
Default

Quote:
Originally Posted by ppo View Post
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. ;)
ewmayer is offline   Reply With Quote
Old 2007-04-19, 13:48   #5
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

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 is offline   Reply With Quote
Old 2007-04-19, 14:42   #6
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

145128 Posts
Default

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
davieddy is offline   Reply With Quote
Old 2007-04-19, 22:22   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts
Smile

Quote:
Originally Posted by ewmayer View Post
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 is offline   Reply With Quote
Old 2007-04-19, 22:33   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts
Default

Quote:
Originally Posted by davieddy View Post
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
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
On crt based factorization? Unabomber Math 1 2014-04-04 20:19
Calendar math science_man_88 Lounge 11 2011-06-26 11:13
Mersenneforum calendar ET_ Lounge 8 2010-09-02 08:40
Prime95 on NT-based OS ThomRuley Software 2 2004-03-21 15:30
4 checkins in a single calendar month from a single computer 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.