Estimating Optimal Golomb Ruler Fit

Golomb Rulers are an interesting class of math problem. For one thing, they can consume all available “computes” for all foreseeable future time. For another, they are useful.

Useful for what? Well, for siting radio telescopes for optimal performance with minimum number on the least land, and for some kinds of data compression and in radio, spectrum use. Among other things (including optimal position of sensor for things like x-ray fingerprints of diamonds).

So what’s a Golomb Ruler? Pretty simple, really. It is a set of marks on a stick where the distance between e two marks is unique.

A lot more is here:

https://en.wikipedia.org/wiki/Golomb_ruler

But I’m just going to give one simple example and I think that’s enough to “get it”.

A Golomb Ruler with 5 elements (called ‘order 5’) and largest element of 11 (called ‘length 11’) is:

0  1  4  9  11

And if you look at the distance between the different numbers you get:

1  3  5  2
   4  8  7
      9  10
         11

No 2 numbers the same.

Now this ‘ruler’ is also an “optimal ruler” as the 11 is as small as you can get and still make 5 marks. This matters since, for example, if you were making a radio telescope with 5 antennas, you get the maximum information with the least land if you space them at 0 (start), 1, 4, 9, and 11. If those were km spacings, you would really rather not put one out at 23 km beyond what you needed and buy a lot more land…

There’s also some interesting bits on Golomb Rulers here:

http://mathworld.wolfram.com/GolombRuler.html

And here:

http://www.research.ibm.com/people/s/shearer/grule.html

Nostalgia

I first started looking at this about a dozen (or maybe 14 now..) years ago when I first had a long duration contract in Florida. I was in a Motel and using my Compaq laptop (that I still have…) with some God Awful slow processor by today’s standards. It’s something like 64 MB of memory, Red Hat 5.2 or so, and some small Pentium. But I had a Golomb Ruler code I’d written running on it. (“someday” I need to find that in the archives and compare it to modern versions for speed and accuracy).

While doodling around looking at these lengths, I decided to just “plot them and look at it.” This was done by hand on graph paper. By Inspection, it sure looked like a parabola. Smith’s Hypothesis Of Golomb Rulers was formed: “Optimal Golomb Rulers lie near a parabola”.

I doodled around some more and did a crude curve fitting. It sure seemed to hold and have some predictive power. I even managed to find one of the next likely Optimal Golomb Rulers, but at that time it was not easy to find out if it was new (or tell anyone) unless you were a math professor.

Then the contract “suddenly ended” when the client decided to outsource their data center. Golomb went on the shelf as I packed up and headed home, looking for a new job and no longer spending evenings bored silly looking for a ‘hobby’ to keep me interested.

Time Passes

Well, time passes, and Moore’s Law makes computers a LOT faster. The Raspberry Pi I’m using now is roughly the same performance in total computes as the Cray XMP I managed in the 1980’s. The Web makes all sorts of things nearly trivial to find, or do. Distributed Computing has moved Golomb Rulers forward quite fast (and hit a new exponential wall at an optimal length of 28), and my “solution” can now be checked against reality (IFF I can find it in one of the old boxes…)

Furthermore, since blogging has evolved into existence, I can now “publish” without all the pain and suffering of the past.

So with that, I’m going to “toss the idea at the world” and see if it grows…

The Fitting Of The Curve

Where before I did this with pencil and paper over nights in the hotel, now it is a quick visit to a web page:

WolframAlpha Quadratic Fit

Quadratic Fit to Optimal Golomb Rulers

Quadratic Fit to Optimal Golomb Rulers

Now this shows that the errors are to each side of the ‘fit’. You really want a parabola that sits to one side, so that a search does not run forever to find nothing.

I went back by hand and did a trial of a few simpler equations, looking for one or two that seemed to just skirt the edges of the fit for the more recent data points. In the very early data points, you get an exact fit with

y= 1/2 x^2 -1/2 X

but that rapidly doesn’t fit so well. (Implying that the actual curve isn’t quite a parabola, or that the integer nature of the rulers makes them have significant ‘jitter’ in the errors as things grow).

Some of the other ‘fits’ as you add items are:

0.64 X^2 -1.15 X +0.6
0.70 X^2 -1.51 X +0.7
0.74 X^2 -1.89 X +1.66
0.81 X^2 -2.70 X +3.3

And so it goes. Clearly a better “fit” and perhaps even solving for the vertex of the implied parabola would be very helpful.

But I just want a good enough ‘rule of thumb’ for the next few numbers in the Golomb series. So I did a hand fit / fudge with some simplifications. First off, this basic formula is of the form y=aX^2+bX+c and I dumped the “c”. Then adjusted to keep the fit close.

There are four formulas that look to have some ‘merit’ as starting point finder for a search for any given ruler.

0.8 X^2

0.8 X^2 -X

0.8 X^2 -1/2X

0.81 X^2 -X

There is certainly a better choice with a bit more tuning.

I computed the predicted value of each, and compared that to the known Optimal Golomb Rulers for the 27 known lengths.

0.8 X^2 gives a value that never fails to be just outside the actual value, but the distance is a bit further than I’d like.

0.8 X^2 – X gives a nice close value, but sometimes is just a hair too short. Take the ruler of n=21 for example. The optimum known is length 333. If you do 0.8 x 21^2 = 352.8 and that’s about 20 away from the optimal. It would take a while to iterate that distance. Now look at 0.8 X^2 -X and you get 331.8 and a miss by 1.2 so you search forever and find nothing. That’s not good.

Yet in the first 27, there are only 4 misses, and two of them are the n=1 and n=2 cases at the start. Clearly it’s a very tight fit. (The other big one is n=25 and length 480 where it predicts 475 for a miss by 5).

Which brings us to the two other formulas. Instead of taking out a full X, take out 1/2 X, or have the X^2 grow a bit faster.

The 0.8 X^2 and 0.81 X^2- X formulas have “cross over” at n=100 with both giving a prediction of 8000 length, while the best known is length 8831 and 0.8 X^2 – X predicts 7900 length. This fairly strongly implies, IMHO, a more optimal ruler than the known length at between 7900 and 8000 with the potential of one just a bit shorter than 7900 not ruled out. 0.8 X^2 – 1/2X gives 7950 and I’d expect the actual value is more probably between 7900 and 7950 if I had to bet.

IMHO, the optimal thing to do from this point would be to fit 3 parabolas. One just outside the known optimal values, one just inside, and one ‘best fit’. Then search from both edges toward the middle and from the middle toward both edges. As soon as any ruler if found, it sets a new bounds and the searches outside that bounds can be discarded.

It is my belief that this ‘fitting’ method using parabolas (or any better fit) would significantly reduce the search area from the present methods for proving an Optimal Golomb Ruler (which is exhaustive search). While exhaustive search is still the only way to prove a ruler is optimal, this ought to more rapidly get you to good candidates.

For a list of the known rulers, optimal or not, see:

http://www.research.ibm.com/people/s/shearer/grtab.html

This web page contains a table giving the lengths of the shortest known Golomb rulers for up to 150 marks. The values for 23 marks or less are known to be optimal. For the actual rulers see

    known optimal rulers
    best rulers from projective plane construction
    best rulers from affine plane construction 

Table of lengths of shortest known Golomb rulers marks 	length 	found 	by 	proved 	by 	comments
1 	0 					trivial
2 	1 					trivial
3 	3 					trivial
4 	6 					trivial
5 	11 	1952 	WB 	1967? 	RB 	hand search
6 	17 	1952 	WB 	1967? 	RB 	hand search
7 	25 	1952 	WB 	1967? 	RB 	hand search
8 	34 	1952 	WB 	1972 	WM 	hand search
9 	44 	1972 	WM 	1972 	WM 	computer search
10 	55 	1967 	RB 	1972 	WM 	projective plane construction p=9
11 	72 	1967 	RB 	1972 	WM 	projective plane construction p=11
12 	85 	1967 	RB 	1979 	JR1 	projective plane construction p=11
13 	106 	1981 	JR2 	1981 	JR2 	computer search
14 	127 	1967 	RB 	1985 	JS1 	projective plane construction p=13
15 	151 	1985 	JS1 	1985 	JS1 	computer search
16 	177 	1986 	JS1 	1986 	JS1 	computer search
17 	199 	1984? 	AH 	1993 	OS 	affine plane construction p=17
18 	216 	1967 	RB 	1993 	OS 	projective plane construction p=17
19 	246 	1967 	RB 	1994 	DRM 	projective plane construction p=19
20 	283 	1967 	RB 	1997? 	GV 	projective plane construction p=19
21 	333 	1967 	RB 	1998 	GV 	projective plane construction p=23
22 	356 	1984? 	AH 	1999 	GV 	affine plane construction p=23
23 	372 	1967 	RB 	1999 	GV 	projective plane construction p=23
24 	425 	1967 	RB 			projective plane construction p=23
25 	480 	1984 	AH 			projective plane construction p=25
26 	492 	1984 	AH 			projective plane construction p=25
27 	553 	1984 	AH 			projective plane construction p=27
28 	585 	1984 	AH 			projective plane construction p=27
29 	623 	1984 	AH 			projective plane construction p=29
30 	680 	1984 	AH 			projective plane construction p=29
31 	747 	1984 	AH 			projective plane construction p=31
32 	784 	1984 	AH 			projective plane construction p=31
33 	859 	1984 	AH 			projective plane construction p=32
34 	938 	1984 	AH 			projective plane construction p=37
35 	987 	1984 	AH 			affine plane construction p=37
36 	1005 	1984 	AH 			affine plane construction p=37
37 	1099 	1984 	AH 			projective plane construction p=37
38 	1146 	1984 	AH 			projective plane construction p=37
39 	1252 	1984 	AH 			projective plane construction p=41
40 	1282 	1984 	AH 			affine plane construction p=41
41 	1305 	1984 	AH 			projective plane construction p=41
42 	1397 	1984 	AH 			projective plane construction p=41
43 	1507 	1984 	AH 			affine plane construction p=43
44 	1596 	1984 	AH 			projective plane construction p=43
45 	1687 	1984 	AH 			projective plane construction p=47
46 	1703 	1984 	AH 			projective plane construction p=47
47 	1804 	1984 	AH 			affine plane construction p=47
48 	1887 	1986 	LS 			projective plane construction p=49
49 	1958 	1984 	AH 			projective plane construction p=49
50 	2094 	1984 	AH 			projective plane construction p=49
51 	2190 	1984 	AH 			projective plane construction p=53
52 	2270 	1984 	AH 			projective plane construction p=53
53 	2347 	1984 	AH 			projective plane construction p=53
54 	2373 	1984 	AH 			projective plane construction p=53
55 	2598 	1984 	AH 			projective plane construction p=59
56 	2725 	1984 	AH 			projective plane construction p=59
57 	2773 	1984 	AH 			projective plane construction p=59
58 	2851 	1984 	AH 			projective plane construction p=59
59 	2911 	1984 	AH 			projective plane construction p=59
60 	3019 	1984 	AH 			projective plane construction p=59
61 	3134 	1984 	AH 			affine plane construction p=61
62 	3215 	1984 	AH 			projective plane construction p=61
63 	3391 	1984 	AH 			projective plane construction p=64
64 	3527 	1984 	AH 			projective plane construction p=64
65 	3593 	1984 	AH 			projective plane construction p=64
66 	3757 	1984 	AH 			projective plane construction p=67
67 	3819 	1984 	AH 			projective plane construction p=67
68 	3956 	1984 	AH 			projective plane construction p=67
69 	4145 	1984 	AH 			projective plane construction p=71
70 	4217 	1984 	AH 			projective plane construction p=71
71 	4330 	1984 	AH 			projective plane construction p=71
72 	4473 	1986 	LS 			projective plane construction p=73
73 	4513 	1984 	AH 			projective plane construction p=73
74 	4753 	1984 	AH 			projective plane construction p=73
75 	4982 	1984 	AH 			projective plane construction p=79
76 	5089 	1984 	AH 			projective plane construction p=79
77 	5204 	1984 	AH 			projective plane construction p=79
78 	5299 	1984 	AH 			projective plane construction p=79
79 	5408 	1984 	AH 			projective plane construction p=79
80 	5563 	1984 	AH 			projective plane construction p=79
81 	5717 	1984 	AH 			projective plane construction p=83
82 	5814 	1984 	AH 			projective plane construction p=83
83 	6020 	1984 	AH 			projective plane construction p=83
84 	6159 	1984 	AH 			projective plane construction p=83
85 	6410 	1984 	AH 			affine plane construction p=89
86 	6537 	1984 	AH 			affine plane construction p=89
87 	6708 	1984 	AH 			projective plane construction p=89
88 	6745 	1984 	AH 			projective plane construction p=89
89 	6778 	1984 	AH 			projective plane construction p=89
90 	6967 	1984 	AH 			projective plane construction p=89
91 	7542 	1984 	AH 			affine plane construction p=97
92 	7617 	1984 	AH 			projective plane construction p=97
93 	7726 	1984 	AH 			projective plane construction p=97
94 	7884 	1984 	AH 			projective plane construction p=97
95 	7967 	1984 	AH 			projective plane construction p=97
96 	8121 	1984 	AH 			affine plane construction p=97
97 	8357 	1984 	AH 			projective plane construction p=97
98 	8462 	1986 	LS 			projective plane construction p=101
99 	8540 	1984 	AH 			projective plane construction p=101
100 	8831 	1984 	AH 			projective plane construction p=101
101 	8897 	1986 	AH 			projective plane construction p=101
102 	9218 	1986 	AH 			projective plane construction p=101
103 	9408 	1986 	LS 			projective plane construction p=103
104 	9581 	1986 	LS 			projective plane construction p=103
105 	9884 	1997 	LM 			affine plane construction p=107
106 	10135 	1986 	LS 			projective plane construction p=107
107 	10241 	1997 	LM 			projective plane construction p=109
108 	10415 	1986 	LS 			projective plane construction p=109
109 	10583 	1986 	LS 			projective plane construction p=109
110 	10767 	1997 	LM 			projective plane construction p=109
111 	11108 	1986 	LS 			projective plane construction p=113
112 	11292 	1986 	LS 			projective plane construction p=113
113 	11423 	1986 	LS 			projective plane construction p=113
114 	11764 	1986 	LS 			projective plane construction p=113
115 	12212 	1986 	LS 			projective plane construction p=121
116 	12412 	1986 	LS 			projective plane construction p=121
117 	12517 	1986 	LS 			projective plane construction p=121
118 	12741 	1998 	JS2 			projective plane construction p=125
119 	12911 	1986 	LS 			projective plane construction p=121
120 	13089 	1986 	LS 			projective plane construction p=121
121 	13280 	1986 	LS 			projective plane construction p=121
122 	13521 	1986 	LS 			projective plane construction p=125
123 	13761 	1997 	LM 			affine plane construction p=127
124 	13948 	1998 	JS2 			affine plane construction p=125
125 	14055 	1986 	LS 			projective plane construction p=125
126 	14348 	1986 	LS 			projective plane construction p=127
127 	14460 	1998 	JS2 			projective plane construction p=128
128 	14821 	1986 	LS 			projective plane construction p=128
129 	15075 	1986 	LS 			projective plane construction p=128
130 	15275 	1986 	LS 			projective plane construction p=131
131 	15548 	1986 	LS 			projective plane construction p=131
132 	15893 	1986 	LS 			projective plane construction p=131
133 	16192 	1986 	LS 			projective plane construction p=137
134 	16296 	1986 	LS 			projective plane construction p=137
135 	16622 	1997 	LM 			projective plane construction p=139
136 	16766 	1986 	LS 			projective plane construction p=137
137 	17031 	1997 	LM 			projective plane construction p=139
138 	17124 	1986 	LS 			projective plane construction p=139
139 	17579 	1997 	LM 			affine plane construction p=139
140 	17938 	1986 	LS 			projective plane construction p=139
141 	18601 	1986 	LS 			projective plane construction p=149
142 	18751 	1986 	LS 			projective plane construction p=149
143 	18941 	1997 	LM 			affine plane construction p=149
144 	19123 	1997 	LM 			projective plane construction p=151
145 	19325 	1986 	LS 			projective plane construction p=149
146 	19628 	1986 	LS 			projective plane construction p=149
147 	19757 	1986 	LS 			projective plane construction p=149
148 	20037 	1986 	LS 			projective plane construction p=149
149 	20265 	1997 	LM 			projective plane construction p=151
150 	20521 	1986 	LS 			projective plane construction p=149

References for above table.

WB - Wallace C. Babcock
    W. C. Babcock, "Intermodulation Interference in Radio Systems", Bell System Technical Journal, 1953, p. 63-73. 
RB - John P. Robinson and Arthur J. Bernstein
    J. P. Robinson and A. J. Bernstein, "A class of binary recurrent codes with limited error propagation", IEEE Transactions on Information Theory, IT-13(1967), p. 106-113. 
WM - William Mixon (unpublished, cited in)
    M. Gardner, "Mathematical games", Scientific American, June 1972, p. 116-118. 
JR1 - John P. Robinson
    J. P. Robinson "Optimal golomb rulers" IEEE Transactions on Computers, C-28(1979), p. 943-944. 
JR2 - John P. Robinson
    J. P. Robinson "Addendum to "Optimal golomb rulers"" IEEE Transactions on Computers, C-32(1983), p. 201. 
AH - M. D. Atkinson and A. Hassenklover
    M. D. Atkinson and A. Hassenklover, "Sets of Integers with Distinct Differences", School of Computer Science, Carlton University, Ottawa Ontario, Canada, Report SCS-TR-63, August 1984.
    see also
    M. D. Atkinson, N. Santoro, and J. Urrutia, "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters", IEEE Transactions on Communications, COM-34(1986), p. 614-617. 
LS - Alex W. Lam and Dilip V. Sarwate
    A. W. Lam and D. V. Sarwate, "On optimum time-hopping patterns", IEEE Transactions on Communications, COM-36(1988), p. 380-382. 
JS1 - James B. Shearer
    J. B. Shearer, "Some New Optimum Golomb Rulers", IEEE Transactions on Information Theory, 36(1990), p. 183-184. 
OS - W. Olin Sibert (unpublished, cited in)
    A. Dollas, W. T. Rankin and D. McCracken, "A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler", IEEE Transactions on Information Theory, It-44(1998), p. 379-382. 
DRM - Apostolos Dollas, William T. Rankin and David McCracken
    A. Dollas, W. T. Rankin and D. McCracken, "A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler", IEEE Transactions on Information Theory, It-44(1998), p. 379-382. 
GV - Mark Garry, David Vanderschel and others (web project)
    Golomb ruler search site 
LM - Lloyd Miller (web page dated Oct. 12, 1997)
    Table of shortest known Golomb rulers (was Table of shortest known Golomb rulers ). 
JS2 - James B. Shearer (unpublished)
    Computations done Feb. 19, 1998 in preparing this table. 

The known Optimal Rulers are given in the wiki. I also compiled the Golomb Ruler Searcdh probrams from:

http://researchweb.watson.ibm.com/people/s/shearer/grprog.html

on my Raspberry Pi just to see if I can keep it busy testing this hypothesis. At first, I was surprised that the results did not match those of the wiki table. Looking a bit further, I realized these are ‘distance reflections’ of each other. A ruler can be specified as the positions, or as the distance between elements. Using n=5 as the example, the wiki lists:

0 1 4 9 11
0 2 7 8 11

while the grs1.f program gives:

pi@RPiM2 ~ $ ./grs1
00005 11
      0     1     4     9    11
      0     3     4     9    11
 n=  5 k=  11 solutions=       2 time= 0.00000000000 nodes=            40.

Note the second ruler of each is different. But state them as length segments instead:

2  5  1  3
   7  6  4
      8  9
         11
and

3  1  5  2
   4  6  7
      9  8
         11

Each row is just a reflection of the other. Typically reflected rulers are considered the same, so if you do run the programs, don’t let that throw you.

And, finally, there’s the distributed.net effort to find ever larger optimal rulers using a gaggle of home machines.

http://www.distributed.net/OGR

Just to give an idea where folks have gotten to, this problem grows exponentially at each step, but so does Moore’s Law (for now).

http://blogs.distributed.net/2014/02/

The OGR-27 project has been completed.
Filed under: project status — Mike Reed @ 16:09 UTC

Dear friends,

distributed.net is proud to announce the completion of OGR-27!

It is almost five years ago to the day that we began on this exciting journey. Almost 20,000 of you joined us.. without whom, it would have been impossible.

We have proven conclusively by the exhaustive search of all possible rulers that the previously predicted 27-mark ruler is indeed the most optimal one. We were confident that we would find a more optimal ruler during this search, but it was not to be.

We expected it to take us seven years to complete this awesome task but thanks to your efforts recruiting your friends and co-workers to our effort and a little help from Moore’s Law, we did it in five.

The best known ruler is 27/3-12-26-25-29-2-9-36-10-68-1-4-17-53-35-8-16-28-6-14-13-71-18-19-23-7 (length 553). Represented the other way, this is marks at positions 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553.

In total, we verified 302,621,586 unique stubs (2,526 with 3-diffs, 179,120 with 4-diffs, 6,457,815 with 5-diffs and 295,982,125 with 6-diffs), requiring each to have been completed at least two times independently and with an identical node count. Additionally, due to a client implementation bug in some early clients, we required all stubs to have been verified at least once by a client greater than v2.9109.518. This delayed us by a few weeks towards the end of the project but was necessary to ensure that no work was skipped.

The shortest ruler was sent to us 11 times, with one user completing it twice. I will be writing to this user directly for some help picking lottery numbers!
We will be sending some distributed.net swag to the lucky winners and hope that you will join us as we move on to our next challenge!

Moo!

One presumes the Moo! greeting is a reference to COW – a Cluster Of Workstations, which is how Distributed Net computing works.

At any rate, in about 2019 we ought to have a length 28 solution, using about 100,000 “computer-years” of computing…

And that points out why I’m hopeful someone will find a way to make use of a ‘near parabolic’ fit to the Optimal Golomb Ruler length.

It would be very nice if “Smith’s Hypothesis of Parabolic Optimal Golomb Ruler Length” could help to cut off a year or three of that compute burden. Unfortunately, at the present size of things, there is no way for me to test this significantly on my own.

So there you have it. Cast to the winds of Mathematical Fortune. May it find favor somewhere.

Subscribe to feed

About E.M.Smith

A technical managerial sort interested in things from Stonehenge to computer science. My present "hot buttons' are the mythology of Climate Change and ancient metrology; but things change...
This entry was posted in Science Bits, Tech Bits and tagged , , , . Bookmark the permalink.

6 Responses to Estimating Optimal Golomb Ruler Fit

  1. bobalooga says:

    Small quibble: the length is the largest DISTANCE not largest element.

  2. E.M.Smith says:

    @Bobalooga:

    Um, when talking about the last element (11 in the above example) the length from start to end is 11 and the distance from 0 to 11 is 11, so I’m not seeing the subtlety you are working at.

    Are you speaking of non-optimal rulers where the final element, the distance from it to the start, and the length might all be different? For all known optimal Golomb Rulers the largest element size, the distance from start to it, and the length are all the same… (and they all start at zero).

  3. Larry Ledwick says:

    Just off the top of my head, going back to my engineering days where we had to learn how to plot those conic section curves graphically rather than mathematically perhaps you should look at similar curves which are not quite parabolas.

    A parabola is plotted using a fixed relationship between a point and a line, where an ellipse is plotted by using a fixed relationship between the two foci. At the special case where they foci of the ellipse are an infinite distance apart the curve plotted is identical to a parabola with the same distance to its focus. (the line “directrix” mimics a distant foci at infinite distance in the ellipse) and in that case an ellipse and a parabola are identical when the foci of the ellipse are infinite distance apart.


    http://www.engineerintrainingexam.com/eit-review/mathematics-for-engineering/straight-lines-and-conics/

    Therefore an ellipse is always “inside” the parabola it mimics. Any ellipse with a major axis shorter than infinity would plot inside the parabola, If that is the case the ellipse might be the inner bound of the jitter and a hyperbola might be the outer bound of the jitter.

    Defining the characteristics of the ellipse and hyperbolas which would bound the jitter I leave as an exercise for those with more math background than I, but it would be a logical starting place in my view for analyzing your rule. Perhaps some relationship with the key characteristics of the ellipse and hyperbola and the parabola’s characteristic dimensions, like the bounding value would be some relationship with the largest known number of the ruler you are working on and trying to find the next number in the series.

    If true you would trim the values to test by several orders of magnitude.

  4. E.M.Smith says:

    @Larry:

    Interesting idea…

    Oh, and since we’re at 1/2 decade to compute a proof… it would be very practical to recompute bounding ellipse, parabola, and hyperbola for each run / length target.

    And yes, that “trim by a couple of orders of magnetude” is the whole idea. You trade some occasional failures (like picking a starting point inside the actual optimum) for a potential very fast hit most of the time on a ‘near optimal’, then adjust strategy. IFF the one bound run wanders off an dies, the other run ought to succeed and much sooner than otherwise.

    Since we’re in the land of using multiple processors anyway, it would be reasonable to “bound the space” and assign parts of the cluster to search parts of the space. This just (hopefully) starts them off such that at least one of them is much much closer to the final solution…

  5. bobalooga says:

    Yes, since you didn’t specify non-optimal, I had to be a pedant.

  6. E.M.Smith says:

    Ok. Pedantry welcome ;-)

    I’ve been an olympic class nit harvester sometimes too :-)

Comments are closed.