[RC5] Status of OGR-24

distributed at banoffee.co.uk distributed at banoffee.co.uk
Wed Aug 27 13:55:49 EDT 2003


decibel at distributed.net wrote:
[...]
> the case we would distribute the work to the network, but we can't do
> this until we can 'combine stubs' so that many stubs that would take
> minutes to complete could be grouped together.  This is the only way the
> network at large could reasonably process these minute-long stubs.

Suggestion:
Send out a packet that is in effect a stub with 5 marks (rather than 6),
and an implied or explicit instruction that the sixth mark should be at
position 71 or greater.

e.g. (using the first possible example) d.net would have already checked
1-2-4-5-8
1-2-4-5-10
1-2-4-5-13
1-2-4-5-14
..
1-2-4-5-58

so the client could be sent a packet like
1-2-4-5+59

where the '+' means to check the entire stub tail (including 1-2-4-5-59,
1-2-4-5-60, 1-2-4-5-61, ...)

(this notation mimicks the client's output on partly-completed stubs - in
effect 1-2-4-5-8 is equivalent to 1-2-4-5-8+10 )

Such a combined stub would be considerably more complex than the last few
stubs which the network had already handled.


It would presumably also be necessary to distribute shorter stubs which
could not generate 6 mark stubs sufficiently short to be included in
the first search e.g.:

1-2-4-59
1-2-4-60
1-2-4-61
..
(which would be somewhat more work than the already distributed 1-2-4-58-5,
and similar to the suggested 1-2-4-58+8)

.. and finish this with a suitable stub tail (for sake of example at the
same 70 cutoff, but in practice may need to be higher)

1-2-4+64

The same principle could be applied all the way down the earlier mark
positions:

So towards the end of the 1-stub region there might be the following stubs
(assuming a 70 cutoff between stubs and "stub tails" in all cases, and that
the other rules limiting mark positions didn't stop the search earlier):
1-60-2-3-4  (would already have been distributed and checked if legal)
1-60-2-3+6
1-60-2-4-3  (again presumably already checked)
1-60-2-4+5
1-60-2-5
1-60-2-6
1-60-2-7
1-60-2+8
1-60-3-2-4  (*)
1-60-3-2+6
1-60-3-4-2  (*)
1-60-3-4+5
1-60-3-5
1-60-3-6
1-60-3+7
1-60-4-2-3  (*)
1-60-4-2+5
1-60-4-3-2  (*)
1-60-4-3+5
1-60-4-5
1-60-4+6
1-60-5
1-60-6
1-60-7
1-60-8
1-60-9
1-60+10
1-61-2-3
1-61-2-4
1-61-2-5
1-61-2-6
1-61-2+7
1-61-3-2
1-61-3-4
1-61-3-5
1-61-3+6
1-61-4-2
1-61-4-3
1-61-4+5
1-61-5-2
1-61-5-3
1-61-5+4
1-61-6-2
1-61-6+3
1-61-7
1-61-8
1-61+9
1-62-2-3
1-62-2-4
1-62-2-5
1-62-2+6
1-62-3-2
1-62-3-4
1-62-3+5
1-62-4-2
1-62-4-3
1-62-4+5
1-62-5-2
1-62-5+3
1-62-6
1-62-7
1-62+8
1-63-2-3
1-63-2-4
1-63-2+5
1-63-3-2
1-63-3+4
1-63-4-2
1-63-4+3
1-63-5
1-63-6
1-63+7
1-64-2-3
1-64-2+4
1-64-3-2
1-64-3+4
1-64-4
1-64-5
1-64+6
1-65-2
1-65-3
1-65-4
1-65+5
1-66-2
1-66-3
1-66+4
1-67-2
1-67+3
1-68
1-69
1+70

In practice it may be necessary to adjust the cutoff at the earlier
positions, as we are combining an order of magnitude more 6 mark stubs, or
perhaps it should never go shorter than (say) 4 marks... i.e. have the
 +N as the 4th supplied number at earliest and 1-70-2 1-70-3 1-70-4 ...
distributed individually.

This type of approach (albeit using different notation) was used for
distributing the packets in the OGR-22 search.

For example in OGR-22 I did (amongst many others) 3-2-22, a packet that
(in the above notation) would be 3-2+36, and 1-35.


Using this approach, the number of stubs remaining to distribute, and the
complexity of each should be comparable to the search already done.


As an aside, it might be interesting to go back and actually find ALL OGRs
with 24 or fewer marks, so that at the end of the search there will be a
list of rulers to show for the work, rather than a statement of "nope - 
didn't find a better one". In effect this means just searching for a ruler
of length less than OR EQUAL to the best known rather than just less than.
I believe this was estimated to increase the workload by about 7% on OGR-23,
but have no idea how this scales to greater or lesser numbers of marks.

It seems to me that any actual applications of OGRs such as x-ray
crystallography etc. are more likely to be interested in concrete examples
of OGRs than a statement that one known OGR-NN is the best possible of
that length.

-- 
Steve.



More information about the rc5 mailing list