|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : How does the client search for OGRs?|
A brute force OGR search is essentially a set of nested for loops. For example, an OGR-10 search might look like this:
# Best known OGR-10 is of length 55, so don't search past that For A1 = 1 to 55-OGR # OGR is the length of the optimum 9-mark ruler For A2 = A1 to 55-OGR For A3 = A2 to 55-OGR ... For A10 = A9 to 55 Does A1 thru A10 form an OGR? If so, we have a new best OGR! Next A10 ... Next A3 Next A2 Next A1
Of course, this is a highly simplistic view, and there are many tricks that can be used to narrow the search. One important thing to note is that as the outer loop variables get large, the amount of time spent in the inner loops decreases drastically.
For distributed.net, these for loops are split between the client and the master. The master will generate a stub of a ruler, such as '25/6-5-8-21-15-3'. This tells the client that it should work on a 25 mark ruler, with A1=6, A2=5, A3=8, A4=21, A5=15, and A6=3.
Part of what the master does when generating stubs is limit the size of the stub. If this was not done, the number of stubs (and thus the amount of data the master would have to track) would be far larger than it currently is. More important, if initial stub size wasn't limited, many stubs would be generated that would take minutes or even seconds for a client to search. This would create a unacceptably large load on the network.
Greg Hewgill has a page that describes distributed.net's OGR implimentation in a bit more detail.
© Copyright distributed.net 1997-2013 - All rights reserved