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:
  • Re:proved? (Score:5, Informative)

    by bunratty (545641) on Saturday October 25, 2008 @10:03PM (#25513867)
    You're thinking of science. You can only disprove a hypothesis, never prove it true. In math, you can prove or disprove a conjecture.
  • Re:proved? (Score:5, Informative)

    by Anonymous Coward on Saturday October 25, 2008 @10:13PM (#25513943)

    What most people don't realize is that all of mathematics is based on certain assumptions, alternatively called axioms, postulates or definitions. Do all triangles have interior angles that add up to 180 degrees? Yes, but only if you make certain assumptions. That's called Euclidean geometry. There is also non-Euclidean geometry which is equally valid and is used to describe some systems in reality. Is there no highest prime? Does 2 + 2 = 4? Do parallel lines never intersect? Are no circles square? Yes again on all counts, but only if you make certain assumptions. So when we say that "x is proven" in mathematics then that is really shorthand for "x is proven based on certain assumptions". That doesn't stop some overzealous mathematicians from acting a little bit smug. I would like to point all smug mathematicians to Kurt Godel's incompleteness theorems.

  • by Pinckney (1098477) on Saturday October 25, 2008 @10: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:wtf (Score:5, Informative)

    by Anonymous Coward on Saturday October 25, 2008 @10: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 Anonymous Coward on Saturday October 25, 2008 @10:29PM (#25514067)

    They are still offering the prize money, just not from RSA.

    And they are going to begin OGR-26 soon.

  • by Anonymous Coward on Saturday October 25, 2008 @10:46PM (#25514167)

    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.

  • by Jsprat23 (148634) on Saturday October 25, 2008 @10: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.

  • by mabhatter654 (561290) on Saturday October 25, 2008 @10: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.

  • by mabhatter654 (561290) on Saturday October 25, 2008 @11:02PM (#25514305)

    the application has to do with harmonics. For example the classic problem is that bridge that collapsed under wind load in the 40's. It collapsed partly because harmonics from the wind, just like a whistle, built up. Part of breaking harmonics is having a quick list of numbers that you can be sure won't duplicate. In a bridge you might pick your structural members to be just a little "off" using proportions from this list so that no two pieces were identical, one way of reducing vibrations in the structure.

    Each length appears exactly once on the list and they can never be repeated unless you pick the exact same line segment.

  • by khchung (462899) on Saturday October 25, 2008 @11:29PM (#25514483) Journal

    I am sorry, but listing out all possibilities (assuming that's what they did) and showing one is the minimum IS a valid proof for that minimum in that particular case.

    For example, to prove "7 is a prime number", listing out 1,2,3,4,5,6 and then showing all are not a factor of 7 is a valid proof that "7 is a prime number". If you think this is not a proof, tell me which step in the proof is wrong.

    Of course, whether the proof of Distributed.net is correct depends on how strongly they can prove their program actually covered all possibilities.

  • by Free the Cowards (1280296) on Saturday October 25, 2008 @11:32PM (#25514503)

    Wikipedia says:

    There is no requirement that a Golomb ruler can measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proven that no perfect Golomb ruler exists for five or more marks.

    And then links to a page which contains the proof.

  • Re:Story (Score:5, Informative)

    by _xeno_ (155264) on Sunday October 26, 2008 @12:00AM (#25514629) Homepage Journal

    why the hell is everything tagged "story"?

    If you mouse over it (and have JavaScript enabled), you'll be informed that it's the "type tag." I assume the concept is that it differentiates between journals, comments, bookmarks, feed entries, and other types of nodes that could, conceptually, appear in the firehose [slashdot.org].

    I have no idea why Slashdot feels the need to show these on the main page, though, considering that everything that currently shows on the main page is a story. But if you play with the firehose, it's what tells you what "thing" the entry is.

  • by Anonymous Coward on Sunday October 26, 2008 @12:10AM (#25514675)

    It is an NP problem, so as long as they tried all possibilities, it should be correct.

  • by Anonymous Coward on Sunday October 26, 2008 @12:52AM (#25514853)
    Your lack of comprehension saddens me.
    An OPTIMAL ruler has no duplicated distances between marks.
    A PERFECT ruler has every possible distance represented.
    The Wikipedia article is fine, it's your reading comprehension that needs looking at.
  • by excelblue (739986) on Sunday October 26, 2008 @12:59AM (#25514897) Homepage

    Two minor mistakes.

    1.) 1 does indeed divide 7. So, you should only show that 2, 3, 4, 5, 6 does not divide 7.

    2.) You need to state that numbers larger than 7 do not divide 7.

  • Re:proved? (Score:4, Informative)

    by 7 digits (986730) on Sunday October 26, 2008 @01:20AM (#25515015)

    > You are confused - there are no assumptions in mathematics because mathematics does not deal with any real entities. There are only definitions and what you are talking about applies to them: depending on your definitions properties of defined entities will differ. Quite a trivial conclusion most sane people already realize.

    *You* are confused and are mixing definitions and axioms. There are assumptions in mathematics, they are called axioms.

    http://en.wikipedia.org/wiki/Axiom [wikipedia.org]

  • Re:Story (Score:1, Informative)

    by Anonymous Coward on Sunday October 26, 2008 @04:00AM (#25515645)
    It works on Firefox 3 for me...
  • Re:wtf (Score:0, Informative)

    by Anonymous Coward on Sunday October 26, 2008 @05:22AM (#25515923)

    Waaa waaa waaa. Click the wiki link you ignorant piece of shit.


  • #!/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, 183, 184, 192, 196, 198, 200, 204, 210, 213, 216, 220, 221, 223, 227, 231, 232, 238, 241, 242, 243, 247, 249, 254, 255, 256, 257, 259, 262, 264, 267, 269, 272, 275, 279, 280, 283, 284, 286, 288, 291, 292, 294, 295, 296, 297, 308, 309, 311, 312, 317, 318, 326, 327, 328, 329, 330, 331, 332, 335, 336, 337, 338, 339, 341, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 356, 358, 361, 362, 363, 364, 366, 369, 370, 371, 373, 374, 375, 377, 378, 379, 380, 381, 383, 385, 386, 388, 390, 391, 393, 397, 398, 399, 400, 401, 403, 404, 405, 406, 407, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 421, 422, 423, 424, 425, 426, 427, 429, 432, 433, 434, 435, 436, 437, 439, 440, 442, 443, 444, 445, 446, 448, 449, 450, 452, 453, 454, 456, 457, 458, 460, 461, 462, 463, 464, 465, 466, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479]

  • by rbarreira (836272) on Sunday October 26, 2008 @09: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 sketerpot (454020) <sketerpot.gmail@com> on Sunday October 26, 2008 @02:58PM (#25519349)

    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 you could do more good there. The clients are also pretty convenient.

"Our vision is to speed up time, eventually eliminating it." -- Alex Schure

Working...