Date: Fri, 16 Feb 2001 13:29:52 +1100 (EST) From: Iwan Jensen X-Sender: iwan@tincan.ms.unimelb.edu.au Reply-To: Iwan Jensen To: Maggie McLoughlin Subject: Re: note from Prof Knuth In-Reply-To: <200101010824.AAA05710@Theory.Stanford.EDU> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear Prof. Knuth, First of all my very humble and sincere apologies for not replying to your recent e-mails earlier. As penance I decided I had to try to find some ever so slight improvements to your approach, but more on this in a while. I am naturally very happy (and a little relieved) that my polyomino counts have been confirmed. I is naturally easy to do extensive test on counts for lower n (up to 44 in my case) simply by being more conservative while descarding invalid configurations (e.g. instead of using the computed n_add we could use n_add-2). But when it comes to pushing the limits of our comoutational resources we have no such options and have to cross our fingers and hope for the best. Glad to know I wasn't wrong. As to your questions of how I calculate n_add. I didn't detail this because I do it rather primitively (no neat cost matrices for me). I extract the information from a configuration into arrays S(i) the state of the i'th occupied site P(i) the position of the i'th occupied site C(i) 0/1 if the i'th site hasn't/has been connected already. First I put in the connections to the lower and upper boundaries. Next I connect all sites in state 1 to the other sites. The cost is d_l=P(i)-P(i-1)-C(i)-C(i-1) or d_u=P(i+1)-P(i)-C(i)-C(i+1). We can always choose the smallest of these. When d_l=d_u we can either examine the possibilities separately, or, as I did use d_l-1. Next we do teh similar thing for the remaining unconnected componets a little more tricky but not that bad. Of course in calculating d we have to take care when the two site span the kink in the boundary line, tedious but not bad. As you can see this is more primitive than your elegant method, and the cost is not necessarily optimal due to the use of d-1 in cases where the uppper and lower costs are the same. Experimentally I found it made almost no difference at the level up to n=46. I had a good read of your program which I find very elegant and nice. I can kick myself for not using the symmetry once a row is completed. I thought about originally for a minute but decided not to since there is no symmetry in intermediate steps so I thought hey it won't help. Had I stopped and thought for 5 minutes I should have realised that off course it helps since you can now totally discard one of the border conditions. You never need the border conditions where you have only touched the border opposite the one you start building from. Due to symmetry this maps to the one where you touch only the border you start building from. Stupid, stupid me. The trick of close packing the generating functions I should have thought of too, well maybe I did, but was to dumb of lazy to implement it. I certainly did't realise that at w=20 you would need less than 3 terms per gf on average. That is some impressive saving. Splitting the calculation in two by using POLYSLAVE would never have occured to me, a very nice trick indeed. This is where I do my penance by suggesting an improvement. When you construct the rectangle at width close to W_max, you quickly reach a kind of `steady-state', that is, the instructions for building the next row do NOT change. For your case at w=20 I would think that this happens after the fourth of fifth row has been added. So you could run POLYNUM output the instructions for building the initial rows then output the instructions for adding a new row and just have POLYSLAVE repeat these the required number of times. Only drawback (easily overcome) is that once you reach row number w you start discarding configurations very quickly and thus getting those last few rows is quick. If you want this saving I think it can be achieved by simply letting POLYNUM jump to row w-1 or so (all that happens is that the minimum number of sites inserted jumps by the number of rows you add) and then continue. Off course uou need to ensure that as you start building a new row you always start a downward (or upward) sweep in memory space but that should not be difficult. If I am right and this works you could save lots of time in POLYNUM and discspace (a factor up to 5 or so). Hope you forgive my not replying sooner. Cheers, Iwan ************************************************************************ Dr. Iwan Jensen Room: 190 Dept. of Mathematics & Statistics Phone: +61 3 8344 5214 The University of Melbourne Fax: +61 3 8344 4599 Victoria 3010 I.Jensen@ms.unimelb.edu.au Australia http://www.ms.unimelb.edu.au/~iwan/ ************************************************************************ Date: Fri, 9 Mar 2001 13:17:48 +1100 (EST) From: Iwan Jensen X-Sender: iwan@tincan.ms.unimelb.edu.au Reply-To: Iwan Jensen To: Maggie McLoughlin Subject: Re: note from Prof Knuth In-Reply-To: <200103012029.MAA27603@Theory.Stanford.EDU> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear Don, You are most welcome to post my e-mail on your web-site, though I might have cut a little back on the self-depreciating remarks had I known -). But then again, maybe not. My observation re. the merging of generating function due to symmetry is simply as follows. In my original program I had to keep four copies of many Gf's. Say the configuration 0010(-)0 would come in four versions none/left/right/both depending on which borders were touched. But under symmetry 0010(-)0 left = 0(-)0100 right So we never need only left touching configurations since they can be folded into only right touching configurations (provided we start building from the right). The configurations with none and both are still required. If the number of configurations of each type grows exponentially with the width then we save a factor of about k^(w-1)/[ k^w + 2k^(w-1) + k^(w-2)] both left/right none over my original approach. Anyway due to your wrapping of the touching into the configuration itself you already use this saving under symmetry. Since my last mail I have implemented most of your improvements to the algorithm (though not the use of POLYSLAVE) and I too noticed that each pass is a little different since the configurations are accessed in different order. This would indicate that to make my 'improvement' work we would need to impose an ordering after completing a row. Thankfully the hash-chains already impose a partial order so we would need to sort each chain and reorganise the configurations (so perhaps not much could be saved depending on how time comsuming this is). I have also implemented a slightly more efficient packing of configurations. The idea is to pack pairs of sites. This is more effient because there are only 13 pairs (a 1 is always surrounded by 0's, a ( is always preceeded by a 0, and a ) is always followed by a 0). Since 13^8 < 2^32 we can store 32 sites in two integers. However, due to the kink in the boundary line we loose a site. 0(-0)(0) is allowed so we insert a 'ghost' 0 in the kink ^ and pack the string 0(-0)0(0) for the above. There are 41 triplets and 121 quadruplets of sites. However, since 41^7 and 121^5 are both > 2^32 this doesn't help. I have also implemented a parallel version of the algorithm and it is currently being tested and optimized. As part of this I am going to n=48 in the first instance, and can then return you a favor by checking your result for n=47. I will keep you informed of further progress. Cheers, Iwan ************************************************************************ Dr. Iwan Jensen Room: 190 Dept. of Mathematics & Statistics Phone: +61 3 8344 5214 The University of Melbourne Fax: +61 3 8344 4599 Victoria 3010 I.Jensen@ms.unimelb.edu.au Australia http://www.ms.unimelb.edu.au/~iwan/ ************************************************************************ Date: Tue, 13 Mar 2001 10:07:32 +1100 (EST) From: Iwan Jensen X-Sender: iwan@tincan.ms.unimelb.edu.au Reply-To: Iwan Jensen To: Maggie McLoughlin Subject: Re: note from Prof Knuth In-Reply-To: <200103012029.MAA27603@Theory.Stanford.EDU> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear Don, You will probably be gratified to know that I have confirmed your count for polyominoes of size 47. The number of size 48 polyominoes is almost certainly (barring any disasters) 1,085,035,285,182,087,705,685,323,738 Best wishes, Iwan Jensen