Forgot your password?
typodupeerror
Math Supercomputing Science

Distributed.net Finds Optimal 25-Mark Golomb Ruler 265

Posted by timothy
from the unique-and-in-duplicate dept.
kpearson writes "Distributed.net's 8-year-old OGR-25 distributed computing project has just proven conclusively that the predicted shortest 25-mark Golomb ruler is optimal. 'The total length of the ruler is 480, with marks at positions: 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480. (This ruler may alternatively be expressed in terms of the distance between those positions, which is how dnetc displays them: 12-17-10-33-19-...).' 124,387 people participated in the project and two people found the shortest ruler, one on October 10, 2007 and the other on March 24, 2008."
This discussion has been archived. No new comments can be posted.

Distributed.net Finds Optimal 25-Mark Golomb Ruler

Comments Filter:
  • wtf (Score:5, Insightful)

    by Anonymous Coward on Saturday October 25, 2008 @08:35PM (#25513693)
    i know we're all supposed to be nerds here, but this is way left of field. dont supposed you could have included a LITTLE more info in the summary as to what the fuck you're talking about?
    • Re:wtf (Score:5, Informative)

      by Anonymous Coward on Saturday October 25, 2008 @09:23PM (#25514021)

      According to the wikipedia article that was linked, a Golomb ruler is a set of numbers where no two pairs of numbers have the same distance. The "order" is how many numbers are in it, and the "optimal" ruler for an order is the one that ends on the lowest number.

      So what they've found which set of 25 numbers - where the distance between any possible pair among them is unique - ends on the lowest number.

    • by unassimilatible (225662) on Saturday October 25, 2008 @10:31PM (#25514495) Journal
      The sumbitch spends most of his time in a dark cave.

      And what the hell would he measure anyway? Not like he has any windows for drapes, my precious.
    • by achurch (201270)
      Read The Fine Link from "Golomb ruler", and be enlightened. If you can make the summary more concise by moving some of it to a separate layer, then why not? The web is all about three-dimensional text, after all.
    • by AbRASiON (589899) *

      How the fuck did this get a +4? I've never even been to university, nor have I done well in maths but as a /. reader I thoguht we all knew about distributed.net? Times certainly have changed, soon we'll see "how is babby formed?" posts on this place,...

  • I like how this is tagged "whatcouldpossiblygowrong," as if building a better radio antenna is going to bring about the end of the world. Oh, wait, I forgot that the movie "Pulse" was a documentary...
    • It's always a valid if stupid question. What could go wrong? In this case, the 25-mark Golomb ruler may NOT be optimal, in which case you would have people using the 25-mark Golomb ruler, with... gasp... SUB optimal results. You might be asking yourself what that would look like. I really haven't the slightest idea what any of this is about, so I couldn't say.

      But the tag gets onto any and all biology related articles, along with it's brother "iamlegend." Usually when it has nothing to do with curing ca

  • by Anonymous Coward on Saturday October 25, 2008 @09:06PM (#25513891)

    distributed.net used to have a very vibrant community, with several projects on-going at one time. But lately, things haven't been going so well for them. The prize funds for their RC5-72 challenge were recently yanked. And the only other project they had on-going was this OGR-25 project.

    Does anyone know if they'll offer further projects in the near future? Many people I know have moved on to BOINC-based [berkeley.edu] distributed computing projects, instead of sticking with distributed.net.

    • It would be nice if there were distributed projects that were more closely linked to modern mathematics than the Golomb ruler computations. ABC@home [abcathome.com] is a start, but I'd be more interested in seeing something like a distributed expansion of tables like these [washington.edu] fed into SAGE in an automated way. Other computations that might be useful include homotopy groups of spaces like spheres, Groebner basis calculations for various geometric objects, and knot invariant calculations [toronto.edu], but I don't know how well these can b

    • RC5-72 (Score:5, Insightful)

      by epine (68316) on Sunday October 26, 2008 @01:01AM (#25515187)

      It's worth calculating the number of gigawatt-hours of electricity is expended on these toy problems. The original goal was to make a political point: we can't assume some of these codes are out of range with present technology. Having made your point, you're just boiling water to arbitrarily make the problem another order of magnitude more expensive to crack.

      When did we decide that the major problem facing planet earth was a surplus of electricity we must burn off by any available method?

      • Precisely! (Score:4, Insightful)

        by rbarreira (836272) on Sunday October 26, 2008 @07:36AM (#25516757) Homepage

        Exactly... I participated in RC5-64, but RC5-72 just seems pointless to me. It's the exact same problem, just 256 times harder.

        Furthermore, these encryption challenges are not actually discovering anything. They're essentially brute-forcing a random number which another computer chose.

        Contrast this with distributed computing challenges about mathematics (such as OGR-25 which is being discussed here), health or other issues where the result is something meaningful and potentially useful about the world.

      • by rbarreira (836272) on Sunday October 26, 2008 @08:03AM (#25516899) Homepage

        Let's assume the project will terminate when 50% of the keyspace has been searched. That's 2^71 keys to search.

        A E6600 Core 2 Duo PC calculates about 17M keys per second according to a quick google search. This means around 1.4e14 computer-seconds to search 50% of the keyspace, or 3.85e10 hours.

        A PC like this one uses around 150 watts, so it would consume 5,775,000,000 KWh of energy to search that keyspace.

        Some different ways of visualizing this amount of energy:

        • At $0.10 dollars per KWh, that's almost $600 million worth of electricity
        • It's the energy contained in 600 million liters of gasoline (157 million gallons)

        This of course doesn't take into account future improvements in CPU efficiency.

    • by steevc (54110) on Sunday October 26, 2008 @04:24AM (#25515929) Homepage Journal

      I ran OGR25 again for the last few months in hope of seeing that project complete. RC5-72 just seems pointless to me. We already know it will take decades without some radical improvement in processing power.

      I've been disappointed by the lack of updates to the dnet site. Even now the projects page still says that OGR25 is active.

      I've moved to Folding@home now as I hope it will have tangible benefits. My contribution is pretty minor as I don't have the hardware for GPU processing.

      • Re: (Score:3, Informative)

        by sketerpot (454020)

        I've moved to Folding@home now as I hope it will have tangible benefits. My contribution is pretty minor as I don't have the hardware for GPU processing.

        If you just have a CPU, then your spare cycles would probably be spent on some BOINC-based projects. [berkeley.edu] I'm especially a fan of Rosetta and uFluids. Rosetta is another protein folding program, but unlike Folding@home it focuses on predicting the final protein structure from the genetic code, rather than simulating the folding process itself. And if you think labs-on-a-chip are cool, uFluids is designing better microfluidic devices with some enormous genetic algorithm. Those are harder to speed up with GPUs, so

  • The Wikipedia page says One practical use of Golomb rulers is in the design of phased array radio antennas such as radio telescopes. Antennas in an [0,1,4,6] Golomb ruler configuration can often be seen at cell sites [wikipedia.org]. Does this mean we can now construct larger antennas with greater sensing power, using fewer materials, due to knowing a larger optimal configuration than previously?
    • by Pinckney (1098477) on Saturday October 25, 2008 @09:19PM (#25513987)
      Probably not. The [0,1,4,6] ruler is only order 4; we've previously known optimal rulers up to order 23. If larger configurations can be practically used, I would expect to see order 5 and higher already in use.
    • Re: (Score:3, Insightful)

      by mblase (200735)

      Does this mean we can now construct larger antennas with greater sensing power, using fewer materials, due to knowing a larger optimal configuration than previously?

      Probably not, since (a) optimal rulers of order greater than four but less than twenty have been known for some time, and (b) the [0,1,4,6] ruler is proven to be the largest perfect optimal ruler (according to the Wikipedia article).

      • by ClintJCL (264898)
        Thank you. So being "perfect" helps more in this situation than anything else?
        • by Jsprat23 (148634) on Saturday October 25, 2008 @09:46PM (#25514173)

          As a hypothesis, if the distance from 0 to 1 is half a wavelength, the distance from 1 to 4 is 3/2 wavelengths and the distance from 1 to 6 is 5/2 wavelengths. These distances represent the first 3 resonances of a resonant dipole antenna. In the case of an antenna, perfect would mean capturing all of the resonances and thus be optimal.

          • I don't get how they know which resonances are the perfect ones to capture, though... Did someone just arbitrarily decide that? Does this coincide with music theory at all (octaves, harmonics, etc)?
    • by SQLGuru (980662)

      Partly yes and partly no. (disclaimer, I only know what I read on Wikipedia -- much like you)

      It sounds like an optimal Golomb ruler allows you to find the shortest that works (which would imply less materials [towers?]) but in this case, it was merely confirming the one that was already assumed to be the shortest. So, yes but no.

      Layne

      • by mabhatter654 (561290) on Saturday October 25, 2008 @09:53PM (#25514231)

        it's essentially defines a list of numbers such that if you pick any two segments that are not the same segment they will always have different lengths. This is useful for things that involve harmonics.. radio, buildings, ect. where you need to build "imperfect" shapes. With antennas this is so that they don't interfere with each other in close proximity. With bridges you might need to make each length of bridge section a slightly different length to keep the bridge from vibrating to pieces. It's a list, highly useful to engineers of various types. Not that exciting, unless you really needed to have 25 critical measurements when 24 just wouldn't do.

  • Every number I plugged in could be measured as a length between 2 numbers in that set. But according to wikipedia, no perfect ruler exists for over 5. And this has 25. So it's not perfect.

    So does anyone have a list of numbers that can't be measured as distances between these? I'd rather not calculate it myself.

    • Re: (Score:2, Informative)

      by Anonymous Coward

      A few lines of Python suggests that there are 180 numbers that can't be measured, starting with 81, 90, 93, 103, 110...

      Obviously the 11 numbers preceding 480 can't be measured, for example.

    • Re: (Score:3, Insightful)

      by Pretzalzz (577309)
      Well, 25 choose 2 is 300 so presumably 180 numbers must be missing.
    • by interiot (50685)
      Missing are: 81, 90, 93, 103, ... 476, 477, 478, 479 (180 different numbers missing total). The fact that it can measure all distances from 1 to 25 doesn't make it perfect, it has to measure all distances up to its length (480).
    • Re: (Score:3, Informative)

      by jonaskoelker (922170)


      #!/usr/bin/python
      marks = [0, 12, 29, 39, 72, 91, 146, 157, 160, 161, 166, 191, 207,
      214, 258, 290, 316, 354, 372, 394, 396, 431, 459, 467, 480]
      unmeasurable = set(range(1, 481))
      for i in range(1, len(marks)):
      for j in range(i):
      unmeasurable.discard(marks[i] - marks[j])
      print sorted(unmeasurable)

      Output:
      [81, 90, 93, 103, 110, 111, 120, 139, 153, 171, 172, 174, 176, 18

  • by pottymouth (61296) on Saturday October 25, 2008 @09:43PM (#25514153)

    My new yumiz ruler is perfectly calibrated in emh's and is 14.667 long. Now I'm going to go measure something like the how many pins can fit on one you guy's heads...

  • You don't need 8 years to design a ruler to measure a pigeon. That's just plain dumb.

  • Years ago I saw a puzzle that is obviously based on this - get two suits, say Diamonds & Clubs. The idea is to arrange the cards in a horizontal line so the the aces are one card away from each other, the deuces two cards away from each other..., the 10's ten cards away from each other..., the kings 13 cards away from each other etc.

    e.g. for starters:

    3 1 2 1 3 2

    It can be done with all 13 cards.

You don't have to know how the computer works, just how to work the computer.

Working...