Between Kroflite and Beeline are five other towns.
combinatorics/golomb.ruler New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Between Kroflite and Beeline are five other towns. The seven towns are an integral number of miles from each other along a straight road. The towns are so spaced that if one knows the number of miles a person has traveled between any two towns he can determine the particular towns uniquely. What is the minimum distance between Kroflite and Beeline to make this possible?
Show solution
Dave Bell <dbell@bayarea.net> wrote:
>63 was posted, but I believe it can be 30, possibly less:
A set of integers with unique differences between any two elements is
called a "Golomb ruler". Check out
http://members.aol.com/golomb20/index.html
for more info. Current methods of finding optimal Golomb rulers have
horrendous time performance. Optimal 7-mark rulers have length 25.
One of them is:
0 1 4 10 18 23 25
There are four others, left as exercises :-).
-- Fred Curtis <fred@zip.com.au>
[ Editor: so the minimum distance is 25 miles. Check of the example:
its 21 pairwise differences are 1 2 3 4 5 6 7 8 9 10 13 14 15 17 18
19 21 22 23 24 25, all distinct. ]
[ Editor: the web page "Golomb Rulers - The Search For 20 and 21!"
(In Search Of The Optimal 20 & 21 Mark Golomb Rulers), as of December
1997, converted from HTML. Each link is given after its text; links
relative to the page are given as file names only. Navigation bars,
images and the page counter are left out. The page was in Latin-1 and
has been converted to UTF-8. ]
In Search Of The Optimal 20 & 21 Mark Golomb Rulers
Coordinated By ...
David Vanderschel <DvdS@texas.net>
Mark Garry <MarkGarry@aol.com>
David Landgren <LANDGREN@LANDGREN.NET>
Contributers To OGR-20 Search ...
Paul Longo <plongo@netaxis.com>
Jim Van Zandt <jrv@vanzandt.mv.com>
Lloyd Miller (http://www.cuug.ab.ca:8001/~millerl)
Roland Adorni (http://www.access.ch/private-users/radorni/welcome.html)
David Landgren <LANDGREN@LANDGREN.NET>
Mike Kessler <mkessler@informatik.uni-ulm.de>
Stephen Adams (http://www.swiss.ai.mit.edu/~adams)
Contributers To OGR-21 Search ...
Jim Van Zandt <jrv@vanzandt.mv.com>
Lloyd Miller (http://www.cuug.ab.ca:8001/~millerl)
Roland Adorni (http://www.access.ch/private-users/radorni/welcome.html)
Mike Kessler <mkessler@informatik.uni-ulm.de>
Torbjörn Alm <torbjorn.alm@swipnet.se>
Eric Prestemon <ecp@io.com>
Zyg Furmaniuk
Jason Heilman
Eric Peters (http://home.att.net/~karfston)
Malcolm Farmer <farmermj@isdugp.bham.ac.uk>
Tom Russo <frusso@snet.net>
Vincent Celier <vcelier@direct.ca>
Larry D. Hays
Guillermo Valor <gbv@ctv.es>
Ron Whittle <caver@bigfoot.com>
Nigel Backhouse <sx52@liv.ac.uk>
Shannon Jones <scj@pobox.com>
Lon Harbour <laughy@southeast.net>
Mark Spinelli <mspinell@vt.edu>
Tim Nikkel <tnikkel@cici.mb.ca>
Nathan Lewis (http://www.es.co.nz/~ndlewis/)
Björn Eriksson <mdeans@algonet.se>
Brent Hugh <bhugh@cstp.umkc.edu>
Daniel Lovinger <danlo@MICROSOFT.com>
Geoffrey Faivre-Malloy <gjf@mindspring.com>
Guy Albertelli <Albertel@cis.ohio-state.edu>
Uwe Falck <U.Falck@BESoftware.com>
David Landgren <LANDGREN@LANDGREN.NET>
Steven Robertson (http://www.owlnet.rice.edu/~phantom)
Matthew Wergeland (http://www.flash.net/~malley/main.html)
Peter E. Jones <pejones@mrj.com>
Joseph M. Mikhail <mikhailj@engin.umich.edu>
Colin Lindsay <solaris@skynet.co.uk>
Charles Bonn (http://home.iSTAR.ca/~troll)
Per M. Hansen (http://www.indexdata.dk/perhans)
Jeff Goetz <kaiser0326@aol.com>
Bryce Taylor (http://www.personal.psu.edu/users/j/b/jbt120/)
Nathan Gracie <nathan.gracie@clear.net.nz>
Ted Van Duyn
Brian Hayes (http://www.amsci.org/amsci/other/BPH.html)
Joseph S Harpe <thoreau@umich.edu>
Martin C Sweitzer (http://pobox.com/~msew)
Nick Gardner <nickgard@aol.com>
Gregory Yovanof <yovanof@prodigy.net>
V. Alex Brennen (http://www.geocities.com/ResearchTriangle/9875/)
Sprite Kiger (http://www.ice.org/~sprite)
Hasan Kanji (http://www-personal.usyd.edu.au/~hkanji/)
Matt Thomlinson <matttT@microsoft.com>
Jeff Goetz (http://www.spiritone.com/~hunter03)
Thomas Nøkleby <thomasn@ii.uib.no>
Jari Dahlgren <jarid@icenet.fi>
Ken Hallenius <hallenius@hotmail.com>
Paul Novarese (http://www.cba.ua.edu/~novarese)
Jussi Heino (http://www.utu.fi/~juhehe)
Joseph Broderick (http://animeonline.ml.org/~spock)
Michael Colin <Michael.Colin@darmstadt.netsurf.de>
Oliver Moldenhauer (http://www.pik-potsdam.de/~oliver/)
Sean Anderson <sean.anderson@thepentagon.com>
Olivier Gérard <jacquesg@pratique.fr>
Brad Pinkston (http://www.louisville.edu/~bapink01/)
Jerry Douglas <jdouglas@iquest.net>
Daniel Marcotte (http://www.delta-net.com)
Jason T. Luttgens <luttgenj@bellatlantic.net>
Sven Meinhardt <triarch@bigfoot.com>
-- If we've forgotten to mention you and you'd like to be listed,
please let us know --
- The GOLOMB Mailing List -
A mailing list has been set up for folks interested in assisting in the
search for better Golomb rulers and for folks interested in the
development of faster programs for implementing such searches. To
subscribe, send mail to [listserv@webventures.com]. For the body of
your message, write
subscribe GOLOMB first-name last-name
Many thanks are extended to Ron Whittle for making the mail server
available for this activity.
Notes (Dec,1997):
A sad note: Our condolances go to the family of Marc Zimmerman. Marc,
who joined our effort in September and was most recently working on
stub 2-19 passed away on December 3.
[New] Are you using UNIX and want more control over lowering a job's
priority so that it doesn't interfere with other jobs? Then download
loadwchr.txt and modify the script as needed for your own use.
[New] We are in the process of testing a revised program that may be
up to twice as fast as GVANT. Unfortunately, it also requires
significant RAM (GVANT has a very small footprint in memory) and as
such may not be suitable for multitasking. We'll keep you informed!
[New] Apr May Jun Jul Aug Sep Oct Nov
Done - 9 20 37 48 70 94 116
Left - - - - 1122 1088 972 953
Wondering how far we have left to go? Heres current progress and
estimated workload left to go. All numbers are in trillions (10^12).
The estimated nodes remaining is based on extrapolations from the
nodes already completed.
Notes (Nov,1997):
[New] Are you a new user wondering what the "send.dat" file is
supposed to look like? Wondering how fast an Alpha runs these things?
David Landgren has a live link to one of his runs at A Golomb Stub Run
(http://www.landgren.net/golomb.html).
[New] A special Win-95/NT executable with priority set to "idle" is now
available that only consumes CPU when your system is otherwise ...
(you got it) ... idle. If you are running any normal priority jobs
(such as WORD or EXCEL) this GVANT will use almost _no_ clock cycles,
so you can leave it running all the time! :) And if your CPU is
otherwise idle, this VC5 GVANT can run almost 1/3 more nodes/second
than DJGPP's (wow). Thanks to all those who previously tried to
convince us switch to a native client and to Matt Thomlinson
<matttT@microsoft.com> who added the priority="idle" code that makes it
useable to all. FYI, Matt compiled this version using VC5 switches
/Zp4 /O2 /Ob2 (BTW, he also compiled an Alpha machine version.)
[New] A small problem with the MAC client has been noted. On long
runs, the client priority may slow significantly if left running
unattended in the foreground (just nudge the mouse or touch a key and
it returns to full speed). John Bafford (http://www.glue.umd.edu/~dshadow)
is working on getting this corrected.
[New] Geoffrey Faivre-Malloy <gjf@mindspring.com> wrote _Distributed
Computing_ in this month's BoardWatch
(http://www.boardwatch.com/MAG/97/Nov/bwm40.htm). Interesting reading
;~)
Notes (Oct,1997):
We've got a new MAC client! John Bafford
(http://www.glue.umd.edu/~dshadow) has been kind enough to recompile
Uwe Falck <U.Falck@BESoftware.com>'s earlier client. We have a self
extracting archive version here called golomb.sea but you may also want
to visit John's site (http://www.glue.umd.edu/~dshadow/golomb) to make
sure you have his latest version. If you're still interested, email us
<MarkGarry@aol.com> and we'll give you instructions on where to begin!
Notes (Sept,1997):
We've added a link (timing.htm) if you are interested in seeing how your
GVANT run times compare to configurations used by other users. You are
free to add an entry (you can stay anonymous if you want) or to simply
use the table to see if you can configure your system any better.
Notes (Aug,1997):
We would like to welcome any Power MAC users. Uwe Falck
<U.Falck@BESoftware.com> has been kind enough to compile a MAC self
extracting archive (SEA) for the Power MAC. Although the program uses
little memory, at this time it tends to "hog" the system CPU so you may
only want to run jobs over weekends, etc. If you're still interested,
email us <MarkGarry@aol.com> and we'll give you instructions.
Otherwise, just hold tight ... we're preparing a better behaved client.
Notes (July,1997):
A chart (index2.htm) depicting why we believe we will find a better 21
mark ruler is available for viewing. The info for the chart was
primarily based on the list of the best known golomb rulers
(http://www.cuug.ab.ca:8001/~millerl/g3-records.txt) maintained by
Lloyd Miller (http://www.cuug.ab.ca:8001/~millerl) (including some ones
he found recently using Cyclic Difference Sets)
Similar Projects:
You might want to take a look at one of the following sites that also
deal with Massive Parallel Computing Projects:
PC based: Massive Parallel Computing Projects (http://www.mersenne.org/)
PC based: Computers and Society (http://web0.tiac.net/users/curtisb/index.html)
MAC based: RC5-Mac (http://www.distributed-mac.net)
This site selected:
"Geek Site of the Day" (http://www.owlnet.rice.edu/~indigo/gsotd)
(Nov 1, 1996)
Outline
[Intro] Introduction To Golomb Rulers ("Geek Site Of The Day" material)
[Diff Sets] Background On Golomb Rulers and Perfect Difference Sets
[This Project] Background On This Project
[Files] Files You Can Download If You Care To
[Current Progress] Current Progress (link to "wem-21.htm")
[Tech Notes] Selected Programming Notes, etc
[Sample Output] Sample Output File (link to "samp.html", a sample send.dat file)
Introduction To Golomb Rulers ("Geek Site Of The Day" material)
A long time ago in the land of the hobbits, a writer by the name of
Tolkien wrote stories of a magical ring. Many would attempt to possess
this ring, including a creature called Gollum. Now as the story goes,
born a hobbit, Gollum possessed the One Ring too long; it lengthened
his life unnaturally and desire for it possessed him completely. His
obsession cost him his life when he stumbled and fell into the volcano
Orodruin, bearing the ring with him. (Note: Gollum was known as
Smeagol before he murdered his cousin Deagol and began sneaking among
his relatives, making gulping noises in his throat.)
NO, WAIT A MINUTE! We were talking about Golomb Rulers, not Gollum
rulers! Oh well, lets start over again. But before we do, be prepared
... because searching for Golomb Rulers has about the same effect on
(and requires the same determination from) humans as the search for
the One Ring had on Gollum!
Golomb rulers refer to a spacing technique that is used in a variety of
areas such as astronomy (placement of antennas), xray sensing devices
(placement of sensors), and myriad other fields such as data
encryption.
A Golomb Ruler has a certain number of marks (e.g., 4). The marks are
placed at integer multiples of some fixed spacing. (Thus mark
positions are usually referred to by integer values with 0 being the
leftmost.) The objective is to achieve as many distinct measurement
distances between marks as is possible with the given number of
marks. Thus these marks must be located very efficiently, so that we
avoid redundant distances between marks - ie., the distance from any
mark to any other mark must be a unique distance for the ruler.
Sample: marks at 0-1-2-3 would not be very efficient, since three pairs
are separated by the distance 1. You could only measure the distances
of 1,2, and 3 with this ruler. This is _not_ a Golomb Ruler.
A sample Golomb Ruler with 4 marks is 0-1-3-7. It can measure six
different lengths: 1,2,3,4,6, and 7. See how no distance is measured
twice? Now, what we really want are Optimal Golomb Rulers (OGR's).
These are the _shortest_ golomb rulers for a given number of marks.
For instance, for 4 marks, the OGR is 0-1-4-6, which measures six
distances (1,2,3,4,5,6) but is as short as possible (6 "units" in
length).
Unfortunately, the search for OGRs becomes exponentially more difficult
as the number of marks increases (similar to what mathematicians call
"Np complete" problems ... like the infamous Traveling Salesman
optimization). Many bright people have tried to solve these, but no
one outside of our little group has yet proven a ruler with more than
19 marks as optimal. Some various academics are trying now, but they
may not reach a solution until 10's of CPU years from now.
Anyway, that, in a nut shell, is a Golomb Ruler! If you want a more
complete description including pictures and background material see
"Who else has worked on Golomb Rulers?", especially W. Rankin's home
page (http://www.ee.duke.edu/~wrankin/golomb/golomb.html)).
Background On Golomb Rulers and Perfect Difference Sets
A major breakthrough in Golomb rulers came in 1967, when Robinson
(library.html), et. al., published very efficient rulers containing
from 3 to 24 marks, many of which were OGR's. To accomplish this,
Robinson relied on a technique of using perfect cyclic difference sets
(perfect CDS).
Though a little difficult to generate, CDS's are easy to understand.
Stealing an anology from Kris Coolsaet (see below), consider a string
of beads that form a necklace. Suppose there are seven beads on this
necklace, and that the beads numbered 1, 3 and 7 are red, but all the
others are black. Of special note to us is the property that for each
pair of these red beads, the number of spaces between the beads is a
number unique to that pair on the necklace. Because the differences
(the spaces between the red beads) are all unique, it forms a Cyclic
Difference Set. Consider:
First Red Bead
1 3 7
--- --- ---
2nd 1 - 5 1 (See how no difference is the same?)
Red 3 2 - 3 Also notice that all differences from 1-6
Bead 7 6 4 - are used, this is called a Perfect CDS.
If we cut the necklace and lay it out in a straight line, regardless of
where you make cut the result is _a golomb ruler_! To get the _best_
golomb ruler for this CDS, just cut away the section between the two
red beads that are farthest apart. In our example, we would cut away
the black beads between the red beads numbered 3 and 7, resulting in
the string 7-1-2-3 (-4-5-6- was cut away). Remember that red beads (or
golomb ruler marks) are at positions 1, 3 and 7. Thus we have a golomb
ruler with marks at positions 0, 1 and 3.
The example shown is a simple one, and we'd rather not get into too
much detail here. However, an excellent summary of cyclic difference
sets, including descriptions, pictures, and exercises (along with
practical advice on creating them, including some programming
examples) is available courtesy of Kris Coolsaet
(http://www.hogent.be/~kc) in his CDS Home Pages
(http://www.hogent.be/%7Ekc/cds/welcome.htm). (Special thanks to Kris
for simplifying such a tough subject!)
Anyway, Robinson truncated known CDS's to generate many optimal or near
optimal golomb rulers for up to 24 marks. Following his work, Lam
(library.html), et. al., extended the search in 1988 using the same
basic technique for all rulers with 150 or fewer marks. E.g., he found
a golomb ruler containing 150 marks with a length of just 20521.
Around the same time (actually prior to Lam's work) Atkinson
(library.html), et. al., refined the CDS approach. Robinson and Lam had
only considered CDS's generated from finite projective planes, but
Atkinson --considering some work by Bose-- also considered CDS's
generated from finite affine planes. The differences are too technical
to refer to here, but if you are interested, you might look first to
Kris' CDS Home Pages (http://www.hogent.be/%7Ekc/cds/welcome.htm).
Atkinson found many better golomb rulers, and published his results for
rulers with up to 100 marks.
Special Note: What to expect from OGR-20 and OGR-21 searches
Unfortunately, the OGR-20 search was not likely to produce a new ruler.
Based on the various prior publications (library.html), it can be shown
that Rulers generated 20-30 years ago using CDS's are very efficient,
especially when the rulers generated do not require too many
truncations from the CDS's. (Truncations, you ask? ... yes, sometimes
you are better served by choosing a larger CDS set and "cutting off"
more than just one section of the necklace as per our example)
From Lam's work, the following table can be generated. The OGR column
shows the actual OGR for the given number of marks. The GR(CDS) is the
length of the golomb ruler found through simple truncation of the CDS
(it does not include improvements made by Atkinson using Bose sets). A
simple glance at the table shows a correlation between the number of
CDS truncations required, and the spread between the resulting ruler's
and the OGR's lengths.
Comparison Table
Marks OGR GR(CDS) GR(CDS) CDS Truncations
-OGR 0 1 2 3
2 1 1 [X]
3 3 3 [X]
4 6 6 [X]
5 11 11 [X]
6 17 17 [X]
7 25 28 3 [X]
8 34 35 1 [X]
9 44 45 1 [X]
10 55 55 [X]
11 72 72 [X]
12 85 85 [X]
13 106 114 8 [X]
14 127 127 [X]
15 151 163* 12 [X]
16 177 181 4 [X]
17 199 201 2 [X]
18 216 216 [X]
19 246 246 [X]
20 283 283 [X]
21 -?- 333 -?- [X]
22 -?- 358 -?- [X]
23 -?- 372 -?- [X]
24 -?- 425 -?- [X]
* (3 truncations of next higher CDS yields 155)
Since the GR-20 of length 283 was found with no truncation, it was
probable that it was the OGR-20. However, it appears there may be a
good chance for improving GR-21's current 333 length, since 3
truncation levels were required to generate the ruler, and (so far) no
improvements on the 333 length have been found using Bose sets or
otherwise.
You can download a program (ftp://members.aol.com/golomb20/pds.zip)
that uses CDS's to find good golomb rulers from here, or jump to Kris
Coolsaet's CDS Home Pages (http://turing.hogent.be/~kc/cds) for a full
nuts and bolts description of how to proceed.
In addition to the above evidence of potential improvement, a graph of
solution lengths versus the number of marks (or differences which
equals the number of marks minus 1) graphically illustrates why we
believe that a better GR-21 may be possible. Presented in a linked
page [index2.htm], a graph of the lengths of the best known golomb
rulers (http://www.cuug.ab.ca:8001/~millerl/g3-records.txt) with 10-100
marks reveals that the current GR-21 is a outlier --far above the trend
line. As an interesting aside, note that --to date-- there have been
no new golomb rulers found and documented with 17-100 marks that are
better than those found by Atkinson in 1987 (with two exceptions: Lloyd
Miller found two better rulers using cyclic techniques he learned from
Kris Coolsaet's CDS Home Pages (http://turing.hogent.be/~kc/cds)).
Thus our best hopes for a new significant discovery may depend on
finding a new 21-mark ruler!
Who has worked on golomb rulers recently?
Several web sites (others/others.html) refer to golomb ruler searches,
including exhaustive search techniques, linear optimizers, genetic
algorithms, and there is even a CGI server that is being used by a
computer class for genetic searches for a 100 mark ruler. Recent
results have not revealed any new _optimum_ rulers (Rankin and others
proved that _existing_ 17, 18 and 19 mark rulers were OGR's).
Background On _This_ Project
David Vanderschel first learned of Golomb Rulers over a decade ago, and
at that time wrote a program to search for OGRs. It was his first "C"
program -- called NANT.C -- but it was an order of magnitude better
than anything else published at the time.
Mark Garry read the Scientific American article in 1994 (yes, the 1989
article --don't ask!) and used a Fortran program to search up through
16 marks. His posting of a query in the num.analysis newsgroup in
mid-1995 led to correspondence and a collection of links to work that
others had done.
Combining the works of the two programs into one resulted in a "C"
program that searches (exhaustively) faster than any other known
programs. Sample solution times on a Pentium-133 pc are:
Number of marks = 13 Solution in 1 minute (48 seconds)
14 Solution in 8 minutes (461 " ")
15 Solution in 80 minutes (4817 " ")
16 Solution in 15 hours (52958 " ")
17 Solution in 2.6 days (225393 " ")
18 Solution in 3.8 days (329488 " ")
19 Solution in 36 days (3 mil " ")
20 Solution in 110 weeks (67 mil " ")
[raw] (solvtime.gif) Click here to view a graph of these completion
times.
[adj] (solvtadj.gif) Click here to view a graph adjusted to compensate
for different CPU speeds.
We are looking to the internet with "open arms" hoping that there are
others out there who might want to get involved either running the
current program (written in C) or improving it.
Files You Can Download If You Care To
If you're interested in helping out, this is where you start! At a
minimum, you'll need (1) an executable to run, (2) a basic set of
instructions, and (3) a range to work on.
-- An Executable To Run
There are several executable's available for download, or you can
"roll your own" using the original C Code (gvant_c.txt).
Power MAC (ftp://members.aol.com/golomb20/golomb.sea) users: There is a
small bug in the MAC version that causes it to slowdown --_to a
crawl_!-- if it is the only job running. So for now it is best to run
it in conjunction with other tasks, or to periodically shake your
mouse! John Bafford (http://www.glue.umd.edu/~dshadow) is working on
getting this corrected. You may want to periodically visit John's site
(http://www.glue.umd.edu/~dshadow/golomb) to make sure you have his
latest version.
Windows-95 or Windows-NT PC (ftp://members.aol.com/golomb20/gvant_nt.zip)
and Windows-95 or Windows-NT Alpha
(ftp://members.aol.com/golomb20/gvant_a.zip) users: We suggest you
consider using the NT native executable instead of the DJGPP (DOS)
version. It is set to provide almost no interference with other tasks
(it has a priority of "idle") so you can leave it running for as long
as you can keep your system from crashing! ;~) It is also about 1/3
faster than DJGPP when you aren't actively using your computer for
other tasks. Thanks to all those who previously tried to convince us
switch to a native client and to Matt Thomlinson <matttT@microsoft.com>
who added the priority="idle" code that makes it useable to all. Matt
compiled this version using VC5 switches /Zp4 /O2 /Ob2.
DOS / DOS Window (ftp://members.aol.com/golomb20/gvantdos.zip) users:
The current "executable" code was compiled using the DJGPP/GCC
compiler, and can run in a DOS window. As such, DOS, Windows (3.1 &
95), and OS/2 users can all use the same program. DOS clients need
special installation to make them multitask "friendly", so take a peek
at the readme file!
-- Basic Instructions / Range To Work On
You should browse and print for future reference readme.htm. It covers
installation and gives you an idea of what to expect when you start
running.
When you're ready to try a real run, please visit our "New Users" page
(newuser.htm), read the last minute instructions, and pick a stub to
try! When you complete the test, return the results by email and ask
for a larger range (please do not keep picking stubs from the new user
page).
-- Thats it ?
Well, there's more if you want it. When we started OGR-21 testing in
Spring 1997, we were in the process of testing a new program, but as of
this time we have not realized any improvements. However, before we
finish OGR-21 we may still find a routine that proves to be
significantly faster. In the meantime, perhaps you'd like to see some
documentation of the current program? GVANT documentation
(gvantdoc.txt) is available to supplement the notes in the source code.
Selected Technical Details
We could use some support in seeing if KTEST is currently optimal for a
21 mark ruler. Earlier studies were performed (ktest.gif: Graph of the
current relative speed versus GANT-33b) but they may no longer be valid
since we have further optimized GVANT. The improvement as a function
of KTEST (see the linked chart above) is not only a function of odd or
even rulers, it is also a function of ruler length AND of ruler
_difficulty_. To understand _difficulty_, consider the following:
Best Known Max 1st Max 1st
Ruler Length Segment Two Segments
15 151 24 45
16 177 26 50
17 199 22 48
18 216 17 39
19 246 30 47
20 283 37 67
21 333 50 87
The Maximum 1st segment of a ruler is at most the difference between
the best known ruler length and that of the next smallest OGR.
(Actually, you can show that the Maximum 1st Segment is one less than
shown in the above table if the OGR of next lower ruler already
contains this Maximum 1st segment as one of it's own segments. But
this is not worth implementing since it saves at best 5% of the CPU
time, and only on the least _difficult_ ruler: OGR-18.)
So far we do not know _a priori_ if ktest=1 is better or worse than
"ktest=2" for OGR-21.
We will also be creating a Workload Estimation Model (WEM) for the
OGR-21 search which predicts how difficult each ruler stub will be, so
that we can sub-divide the work more evenly. (Click here to review how
it was constructed for the OGR-20 search: wem/wem.html)
-- David Vanderschel, Mark Garry and David Landgren, December 1997