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