[r-t] Parity
Robin Woolley
robin at robinw.org.uk
Sat Jun 23 16:59:08 UTC 2007
More than 30 years ago (!), the late Tony Carter (of Luton & Harpenden)
published an article dealing with the material given in Fred Bone's reply. I
have not been able to find my copy so have done my best to reconstruct the
contents. Please bear with me if any errors have crept it over that time,
but see what you can make of it.
First. It is not necessary to sort the changes to derive the 'factorial
index'. It can be done straight from the change. For example, on 6 bells,
the change 213456 must give the index 120. To obtain the index, we reduce
each bell by the number of bells smaller than it to its left. So 213456
becomes 211111, but as Fred notes, we require rounds to be the zeroth index
so reduce the result by one in each posiiton to give 100000. On mutliplying
by the appropriate factorial, one gets the 'lexicographical-order' number.
Second. Tony told me that the above was known long before he published the
article. He claimed the following extension. It is possible to generate the
next factorial index *directly* from the previous using place notation only.
The advantage of this is that one only needs to evaluate the actual change
for the changes you require. Checking is done by checking the index which,
inter alia, needs only one 'bit' - useful on a 48k Spectrum.
As far as I can remember/see, the algorithm goes as follows:
Consider 213456, index 100000 followed by 14 then 'x' place notations. The
change are 231465 and 324156 respec. which (seem) to have indices 110010 &
211011. The algorithm (seems) to be this. In swapping AB, then i if A=>B, we
have B+1.A else B.A
The result was that, on my Spectrum, with a few careful byte-pokes, I
reduced the proof time from a standard length peal from c70 minutes to being
so quick the only speed limit was pressing the 'next screen' key.
Please feel free to comment (politely).
Best wishes
Robin Woolley
PS My son Michael allowed me to use his rubber (eraser for you Americans) to
re-work the problem.
PPS It's all irrelevant anyway, since, using the Earis algorithm, it's so
old it must be wrong.
More information about the ringing-theory
mailing list