Slashdot Mirror

← Back to Stories (view on slashdot.org)

Optimal 24 mark Golomb Ruler Proven

Posted by michael on from the number-crunching dept.

globring writes "Four years ago, distributed.net users undertook the search for the optimal 24 mark Golomb Ruler. This year sees the successful conclusion of that effort. The diagram of the optimal ruler can be seen here. If you have no idea what a Golomb Ruler is, you can read up on them. Work on finding the optimal 25 mark ruler is still in progress."

46 comments

  1. So... by lakiolen · · Score: 0, Troll

    what's the point? Give me a slide rule any day.

    --


    What are you expecting to find here?
  2. Brute forcing useful but not as interesting by TheLink · · Score: 2, Interesting

    Brute forcing is like what some alchemists did - try all the combinations and get a result.

    It's more interesting if you can find a "summary" or new point of view.

    Also, IMO a solution (not talking about proof) that is magnitudes larger than the problem is not very good, and that a good solution is like good "compression".

    --
    1. Re:Brute forcing useful but not as interesting by r2q2 · · Score: 3, Informative

      Not really, alchemists were trying everything under the sun that could possibly convert something into gold. Brute forcing is a proven technique where you have an educated guess of what the problem is and then you use compuational cycles to do it.

      --
      My UID is prime is yours?
  3. Distribution of differences? by Anonymous Coward · · Score: 3, Interesting

    The linked figure containing intrapair differences for the 24-mark OGR was very interesting to me.

    I suppose I could look this up, but I'm too lazy at the moment, and I'm not an expert in math.

    But I'm wondering if anyone knows what the distribution of intrapair differences looks like. Does it follow any known distribution? Is it something that someone has looked into?

    I'm in statistics, so these things are interesting to me.

  4. I for one... by rueger · · Score: 3, Funny

    ... welcome our new Golomb rulers...ah I mean overlords!

    --
    Three Squirrels
    1. Re:I for one... by Anonymous Coward · · Score: 0

      ... am pretty ambivalent towards our old joke xerographic machines.

      If I wanted humor this pithy I'd head on out to Branson and take in one of Smirnoff's shows.

  5. I read the article and still have no idea... by Cade144 · · Score: 3, Insightful

    I read the article, and I still don't have much of an idea what a Golomb Ruler is good for, and why you need this in addition to a trusty straight-edge, tape measure, or laser distance finder. But hey, I'm not a mathematician.

    I do know that people like to study problems that have no practical use (yet) and get completly engrossed in them.

    Why bother with Fermat's Last Theorem? Why try to find the least number of colors necessary to color an n-dimensional map? Why obsess over twin primes?

    Because it's darn fun , that's why!

    Hail to all obessed mathematicians and impossible problem solvers !

    Good luck with your 25, 26 and ... n -mark Golomb Rulers.

    1. Re:I read the article and still have no idea... by Leroy_Brown242 · · Score: 2, Funny

      I've been thinking and hearing about OGR for the 4 years since we started the project, and still have no idea what it is. I just let the math geeks understand, and I'll go on being blissfully ignorant.

      --
      Pretty Pictures!
    2. Re:I read the article and still have no idea... by Relic+of+the+Future · · Score: 1

      In mentions several practical uses in the second linked article. Who marked this insightful?

      --
      Those who fail to understand communication protocols, are doomed to repeat them over port 80.
    3. Re:I read the article and still have no idea... by omarius · · Score: 1

      It might have been easier reading up upon if one didn't have to cull through juvenile bull to get to the meat.

    4. Re:I read the article and still have no idea... by GCP · · Score: 5, Informative

      Briefly (probably too briefly) this and similar sounding challenges have real world applications in optimization, where you are trying to figure out how to get what you need without it costing any more than necessary.

      For example, suppose you needed to do something that involved two things that had to be the right distance apart, which might mean physical distance, or two oscillators on different frequencies, or two voltages, or whatever. Just two things separated by some value.

      You could get pairs separated by 1,2,3,4, etc. by just having one thing (telescope, oscillator, electrode, etc.) located at values 0,1,2,3,4, etc. But suppose each of those things cost you $10 million and you had a $50 million budget. You could still lay them out at 0,1,2,3, and 4, but is there another layout where your $50 million could buy you more bang for the buck?

      How could you lay out 5 things to have the maximum number of different gaps between any pair? And this problem adds another constraint, which is to make the total distance from the least value to the greatest value as small as possible. There are real world problems where that's a constraint, too, such as buying the land on which to situate telescopes.

      Once problems like this are tackled and optimal solutions found using just numbers, then somebody who later comes along with a practical problem who has heard about this work can take advantage of this work to optimize his system.

      --
      "Those who have never entered upon scientific pursuits know not a tithe of the poetry by which they are surrounded."
  6. Is'nt RC5-72 rather useless? by GQuon · · Score: 4, Interesting

    Slashdot beat the Amiga team in OGR-24, but the Amiga team is leading the Slashdot team in OGR-25: OGR-25 Team Listing

    But the Dutch Power Cows leads in both efforts.

    OGR-24 blocks have been scarce for the last few months, so the statistics have been rather erratic.

    At least the OGR effort is more useful than the RC5-72 effort. We showed how quick DES and RC5-56 could be broken quickly with a bruce force attack with spare CPU cycles. But why do RC5-72? It's not that interesting.

    I'm doing OGR-25 now, and when that's finished I might go on to something like folding @ home, if there's a client.

    --
    Irene KHAAAAAAN!
    1. Re:Is'nt RC5-72 rather useless? by tqft · · Score: 1

      I know there is a Dutch Power Cows team doing SeventeenOrBust but is there a slashdot team?

      Seventeenorbust.com reports;
      "Sorry, but there are no teams in the system whose names are similar to "slashdot"."

      Any takers to overwhelm these cheesy cows with /. power?

      --
      The Singularity is closer than you think
      Quant
    2. Re:Is'nt RC5-72 rather useless? by Anonymous Coward · · Score: 0

      Come and Take Us On...

  7. A question!!! by file-exists-p · · Score: 1

    I dont get the scheme on top of http://members.aol.com/golomb20/intro.htm. The sequence is 1, 3, 5 and 2. How one can measure 6 with that ?

    --
    Go Debian!

    1. Re:A question!!! by name773 · · Score: 2, Informative

      you can't. i think the idea is that it has no redundant measurements, for example, 1235 measures 3 and 5 twice, 3215 does the same thing, 3512 does 3 twice, etc.

    2. Re:A question!!! by fireduck · · Score: 1

      I don't think it's designed such that it can measure consecutive numbers, rather the optimal ruler for a given number of marks simply has the most unique number of measurements possible. at least that's what i gather looking at the ogr 24...

    3. Re:A question!!! by EggplantMan · · Score: 2, Informative
      The sequence is the sequence of spacings 1,3,5,2, corresponds to the sequence of distances: 0,1,4,9,11 .

      It allows you to measure: 1,3,4,5,8,9,2,7,10,11

      You cannot measure six because no two distance markings differ by six.

      --

      ?-|||-----x<*))))><
  8. Such a thing as a "Complete" Golomb ruler? by dschuetz · · Score: 3, Interesting

    Do Golomb rulers exist that can measure every integer distance from 1 up to their length?

    That is, a ruler with marks at (0,1,2) can measure lengths of 1, 2, and 3 units, and is 3 units long. The sample ruler on the above-linked site has marks at (0,1,4,9,11), and can measure every length between 1 and 11 EXCEPT 6. You can swap the first two blocks (giving (0,3,4,9,11)) but then you lose the ability to measure 10.

    I guess what I'm asking is whether these rulers exist, and how many are they? Or is there a point where they stop being possible?

    1. Re:Such a thing as a "Complete" Golomb ruler? by benhocking · · Score: 1

      There certainly would be such a Golomb ruler, but most likely it wouldn't be optimal. I wonder if any optimal rulers with more than 4 marks are "complete". They give an example for a 4 mark OGR which is "complete" (0-1-4-6). This is all speculation on my part, IANAM. For all I know, all OGR's contain a "complete" representation.

      --
      Ben Hocking
      Need a professional organizer?
    2. Re:Such a thing as a "Complete" Golomb ruler? by ratboy666 · · Score: 2, Informative

      Yes.

      0 mark
      1 mark (0)
      2 mark (0,1)
      3 mark (0,1,3)
      4 mark (0,1,4,6)

      These are all OGRs, and complete. 5 is the first OGR where it is not complete. I don't think they stop being possible (but I could well be wrong).

      Ratboy

      --
      Just another "Cubible(sic) Joe" 2 17 3061
    3. Re:Such a thing as a "Complete" Golomb ruler? by JiffyPop · · Score: 3, Interesting

      What I take from the minimum rulers you give is that they prove that if you have a ruler that can measure every distance from 1 to 11 that it will either be longer than 11 units or it will have more than one way to measure at least one of the lengths. Looking at a table of optimal golomb rulers (google) I see that any optimal golomb ruler longer than 6 units (4 marks at 0-1-4-6) is not "complete," or in other words it cannot measure every unit distance up to and including its length.

    4. Re:Such a thing as a "Complete" Golomb ruler? by Anonymous Coward · · Score: 2, Interesting

      For an n-mark ruler, the length has to be n*(n-1)/2 because that's the number of ways of picking 2 marks, and we're asking for that many distinct distance, from 1 to n*(n-1)/2.

      For 5 marks and more it's impossible. Here's the best you can do:

      5 mark (0,1,2,7,10), 9/10 distinct distances
      6 mark (0,1,2,4,9,15), 13/15 distinct distances
      7 mark (0,1,3,6,13,17,21), 19/21 distinct distances
      8 mark (0,1,7,11,20,23,25,28), 26/28 distinct distances
      9 mark (0,1,2,3,14,21,26,30,36), 32/36 distinct distances
      10 mark (0,1,2,10,24,27,32,39,43,45), 40/45 distinct distances

  9. award for most scientific aol homepage goes to... by avi33 · · Score: 3, Funny

    golomb20

    Seriously. This is the type of thing you expect to see at cs.foo.edu/~golomb20

    Hey, I guess even mathematicians use aol. Well, ONE does, and maybe 19 other golombs before him.

    gears are for wussies

  10. Gollumb rulers and np-complete problems by davidwr · · Score: 3, Interesting

    I'm no expert on np-complete problems, and this is literally an off-the-cuff idea, so feel free to shoot it down or run with it:

    Someone once proved that np-complete problems map to each other. That is, if you solve one, you've solved them all. this page linked in the main story suggests that Golumb Rulers are "like" np complete problems. If it is indeed np complete, then maybe an efficient-but-suboptimal solution to the Golomb Ruler problem will map to any other np-complete problem.

    The same link mentions cyclic difference sets as a means of producing very efficient Golumb rulers, at least up to n=150.

    If this technique maps to other problems, like the travelling-salesman problem, then "practical" albeit not-quite-optimal solutions can be found relatively easily. If you are a traveling salesman, do you really care if your 100-stop route has a small amount of waste, if finding a better solution might take 10 years of cpu time?

    Likewise, if there are other "not quite optimal" solutions to np-complete problems for n>150, perhaps these solutions can be applied to the Golumb ruler problem, to generate "good enough" rulers of longer lengths.

    Of course, if the Golumb ruler problem doesn't map to the other problems, then "nevermind."

    --
    Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
    1. Re:Gollumb rulers and np-complete problems by dkoulomzin · · Score: 5, Informative

      Actually, strictly speaking, both the travelling salesman problem and finding an efficient Gollumb ruler with n marks are not NP-complete. To be NP-complete, a problem must require a yes/no solution.

      For instance "Is this particular Gollumb ruler optimal among all Gollumb rulers with n marks" asks a yes/no question, and could therefore be NP-complete. Also, the problem "Does there exist a way to visit the following cities without travelling more than n miles" is a decision problem. Note that we can usually phrase non-decision problems as decision problems, but going in the other direction can be trickier... you may in fact have to use the yes/no algorithm an exponentially growing number of times to solve the original problem!

      It is true that NP-complete problems "map" to each other. In fact, this is part of their definition: an NP-complete problem is an NP problem that can map to any other NP problem. Essentially, NP-complete problems are the "hardest" problems of the NP problems. (And quickly, a problem is NP if given a solution and a "proof" to the problem, the "proof" can be verified in polynomial time. This loosely implies that if you can try all perspective solutions simultaneously, you can solve the problem in polynomial time, but if you have to try all possible solutions consecutively, it could take a while.)

      The article does mention that this problem is "like" NP-complete problems, but does not suggest any reason for this except for the presumed requirement of exponential time (which by the way is not necessarily a requirement for NP-completeness... this is in fact one of the outstanding questions in computer science).

      To get back to your original question (does an approximation algorithm for this approximate other NP-complete problems)... let's assume that the decision version of this problem is NP-complete. Then an approximation is more of a guess (with one-sided error) about the answer to the yes/no version. In this case, you have an approximator (with one-sided error) for all NP-complete problems. But this might not really provide an efficient or even correct solution for any corresponding non-decision problem.

      Finally, approximators for the travelling salesman problem do already exist. Not surprisingly, the more reliable and accurate the approximation algorithm, the more time it requires.

      I hope this clarifies things...

      --
      Thou shalt not begin a subject line or post with the word "Umm".
    2. Re:Gollumb rulers and np-complete problems by Anonymous Coward · · Score: 0
      "Is this particular Gollumb ruler optimal among all Gollumb rulers with n marks" asks a yes/no question, and could therefore be NP-complete.

      It is highly unlikely such a problem could be NP-complete (unless P = NP), because for a problem to be in NP you have to be able to verify the answer efficiently given a certificate that proves it. For instance in order to do this for a "Is this optimal?" question you would have to come up with some certificate that basically shows that all other possible inputs are not as good as this one. No one knows of a way to really do this efficiently in general. Problems that ask about optimality are generally in the class NP-hard.

      The proper NP-complete version of the problem would ask something like "Is there an N-mark Gollumb ruler such that distances from 1 to R appear exactly once on the ruler?", then to show that there is you provide the actual ruler as a certificate, which can quickly be verified as satisfying the conditions.

    3. Re:Gollumb rulers and np-complete problems by NonSequor · · Score: 3, Informative

      That would be an approximation algorithm. There are in fact approximation algorithms for the traveling salesman problem. The simplest one yields a tour no more than twice the length of the optimal tour. There is a better ones that gives a tour no more than 3/2 times the length of the optimal tour though and you can get a better approximation for some special cases.

      There is a lot of effort going into finding approximation algorithms. Some problems seem to be harder to find good approximations for than others, but it's not possible to take an approximation from one NP-complete problem to generate an approximation for all other NP-complete problems.

      The reason for this is that formally, NP-complete problems are phrased as decision problems. A decision problem basically amounts to "Does this data have the X property?" For the traveling salesman problem you would phrase the decision problem as "Does this weighted graph have a tour visiting each vertex of weight less than N?" The mapping between two NP-complete problems is a mapping for the data that each problem takes as input. This mapping does not provide you with a mapping between near-optimal solutions to one problem and near-optimal solutions to another. Furthermore, some NP-complete problems can only be phrased as a decision problem. For these problems, there are no near-optimal solutions; for all data, the answer is either yes or no.

      But despite that, yes approximation algorithms really are a big deal and private companies are giving grants to people working on commercially applicable ones. Right now I'd say that the study of approximation algorithms and probabilistic algorithms (i.e. algorithms that yield a correct answer most of the time) are where we're seeing the most development in computer science.

      --
      My only political goal is to see to it that no political party achieves its goals.
    4. Re:Gollumb rulers and np-complete problems by Nitish · · Score: 1

      Mostly accurate post, but you had an error in the definition of NP-Complete problems. You said "an NP-complete problem is an NP problem that can map to any other NP problem." Actually, an NP-Complete problem is an NP problem to which all NP problems can be mapped. That is, a problem A is NP-Complete if all problems in NP can be mapped to it, not if A can be mapped to all problems in NP.

      Even if P=NP, there will exist NP-Complete problems which cannot be mapped to all problems in NP.

    5. Re:Gollumb rulers and np-complete problems by dr2chase · · Score: 1
      I'm not sure I buy your claim about the difficulty of solving the original problem in terms of decision problems. For example, if I have an decision procedure for answering "G can be colored with K or more colors" I can derive a "minimum # of colors for G" with binary search: try 1 (no) 2 (no) 4 (no) ... 2-to-M (yes) (log N steps to get an upper bound) and then use binary search to find the precise minimum. Maybe you meant something different.

      Note that polynomial equivalence admits an awful lot of difference in difficulty -- I can get to within a factor of 2 in either traveling salesman or bin packing w/o too much work, but guaranteeing to be within any factor M of optimal K for graph coloring is equivalent to proving that P=NP. (So graph coloring is in some sense a lot harder than TSP or BP. And no, I do NOT remember the proof).

  11. Can someone explain to me... by nganju · · Score: 1
    Why these are practically useful? The second article says they're used for astronomy etc. but it doesn't tell you why they're useful.

    Say you have a Golomb ruler that's 100cm long. It has a bunch of scattered marks on it, and it can measure any number up to 100cm, if you want to take the time to figure out which two marks will yield the measurement you need. Wouldn't it just be easier to put 100 marks on the ruler, each 1cm apart?

    Is there some situation in which creating the ruler is easy but putting marks on it is hard, so you want to minimize the number of marks? I'm having a hard time seeing the usefulness of this.

    --
    There are 2 kinds of people in this world. Those that can keep their train of thought,
    1. Re:Can someone explain to me... by norton_I · · Score: 2, Informative

      Say you have a process in which some sort of radioactive decay generates pairs of photons, and you have a bunch of detectors. The thing you want to measure is P(theta) -- the probability that a pair of photons are emitted at the angle theta. Something like an OGR would be used to arrange your detectors to get the maximum amount of data.

      Of course what I described uses a circular array, not a linear array, but the idea is the same.

      Fundamentally, a lot of science is measuring power in signals as a function of frequency. If you take a finite series of measurements, the frequencies that you can detect are basically those whose wavelength is 1/N the seperation between two detectors. The more different seperations you have, the more frequencies you can detect, and the better you can reconstruct the signal.

    2. Re:Can someone explain to me... by mhotchin · · Score: 2, Informative

      Imagine that a 'mark' consists of a honkin' huge radio telescope dish. Different distances between dishes equates (I think!) to inferometry at different wavelengths.

      So, build a hundred dishes, or 13? (the smallest OGR over 100 has 13 marks, and measures 106).

    3. Re:Can someone explain to me... by Anonymous Coward · · Score: 0

      Why these are practically useful?

      OK, who let an engineer into the Science section?

  12. about time... by Vellmont · · Score: 1

    Distributed.net has drug its feet for a LONG time on the OGR project. OGR-24 could have been solved a couple years ago if they had been more aggressive in re-issuing stubs.

    I could go on, but I'm wondering if anyone knows of any more productive distributed computing projects? Folding at home always seemed a little dubious in its scientific merit, same with seti@home. I'm not much interested in finding bigger and bigger primes (sorry, but it seems rather pointless), so what's someone who wants to put spare computing power to good use to do?

    --
    AccountKiller
    1. Re:about time... by magefile · · Score: 2, Insightful

      Folding at home has a lot of merit as far as studying prions (Creutzfeld-Jakob, aka mad cow in humans) and protein disorders (Parkinsons, Alzheimers, etc.). No, I'm not affiliated with them, but I do have a rare disorder caused by an enzyme (protein) deficiency, so I am fairly aware of proteomics (study of proteins) and medical research.

    2. Re:about time... by Vellmont · · Score: 1

      Oh I understand there's a HUGE amount of value in understanding how proteins fold, it was just my understanding that folding@home provided a very primitive understanding of protein folding (due to limited computing power even on thousands of machines).

      --
      AccountKiller
    3. Re:about time... by rvw14 · · Score: 1

      How about a cure for cancer? http://www.grid.org/projects/cancer/

    4. Re:about time... by kpearson · · Score: 1

      Here are all of your choices.

    5. Re:about time... by magefile · · Score: 1

      They're doing quite well. And maybe this is just personal bias, but I think even a little info on protein folding (which we don't understand) is more important than proof-of-concept brute forcing of hashes.

  13. Nothing optimal about it! by waterbear · · Score: 1

    It's an interesting numerical puzzle, but misnamed.

    A ruler is a practical object of use, and there's nothing optimal in practice about a ruler that has some of its markings missing!

    -wb-

    1. Re:Nothing optimal about it! by Dachannien · · Score: 2, Funny

      Then I think your post title should be "Nothing ruler about it!" because it most certainly is an optimization problem.

  14. Re:award for most scientific aol homepage goes to. by Anonymous Coward · · Score: 0

    Gears are for wussies? Fixies are for little kids and posers.

  15. A good distributed project. by Anonymous Coward · · Score: 0

    This project attempts to evolve more efficient circuit designs than those designed by humans through genetic algorithms. In fact they already have evolved a few circuits that are better than human designs, just check the goals section on the page.
    http://www.informatics.sussex.ac.uk/users/mmg20/dh e/

    However, you could be responsible for evolving Skynet someday.

  16. RC5-72 is a parking effort by GQuon · · Score: 1

    Replying to myself here.

    RC5-72 is considered to be a parking effort, for whenever the OGR effort runs out of work. CPU speed being what it is today, you'd probably have a better payback chance for playing the lottery than cracking RC5-72.

    --
    Irene KHAAAAAAN!