Distributed.net Finds Optimal 25-Mark Golomb Ruler 265
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."
wtf (Score:5, Insightful)
Re:wtf (Score:5, Informative)
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.
Re:wtf (Score:5, Funny)
Why the hell does Gollum need a ruler anyway? (Score:5, Funny)
And what the hell would he measure anyway? Not like he has any windows for drapes, my precious.
Re:Why the hell does Gollum need a ruler anyway? (Score:5, Funny)
Re: (Score:2)
One needed to rule them all. :)
A primer on corporations (Score:3, Insightful)
Corporations are investment vehicles for people. They represent the interests of people. These people are called "stockholders." This is how the average Joe (70% of US equities are held by the small investor) can pool his resources with other people and get part of the Dream. Like my parents. My dad is a former middle class salesman who was "retired" early due to an on-the-job disability. Thankfully, my parents got into Apple at a good price,
RTFL (Score:2)
Re: (Score:2)
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,...
Shouldn't have to (Score:5, Insightful)
Headlines or summaries should be self explanatory.
Hello, context??? (Score:5, Insightful)
That's got to be the most incomprehensible story summary I've ever seen posted to Slashdot, and that's saying a lot. Seriously. The predicted shortest 25-mark Golomb ruler is optimal? What on earth are you talking about? How about giving us the barest minimum of a context, so we might have some tiny clue what that spew of buzzwords is getting at.
Re: (Score:3, Insightful)
Re:Hello, context??? (Score:4, Insightful)
A summary has to assume some understanding of the subject at hand. If a summary includes mention of a photon, for example, it doesn't necessarily require that it be defined what a photon is in the summary.
That's the point of the criticism. A large majority of the readers here would be familiar with a photon, but not with a Golomb ruler.
Re: (Score:2, Insightful)
Re:Hello, context??? (Score:5, Insightful)
So, to understand the summary, and therefore decide whether or not I want to RTFA, I need to RTFA? You see where that defeats the purpose of the summary?
Re:Hello, context??? (Score:4, Insightful)
Re:Hello, context??? (Score:5, Insightful)
Oh get off it. It's not about being "spoonfed", it's about writing a decent summary. When mentioning a relatively obscure topic (yes, yes, all real geeks know what a Golomb ruler is, etc) it's pretty much common sense to throw in a one-sentence description (so we at least know the general context), instead of, say, a useless list of numbers. I don't need you to tell me what I'm supposed to be eager to do, thank you very much.
As far as complaining goes, given that:
- that was a bad summary
- it is the job of an editor to improve on bad summaries
- Slashdot does have editors
It is at least theoretically possible that complaining can accomplish something. Theoretically.
Re: (Score:3, Insightful)
You really can't get more specific than that. Just because you don't know what a Golomb ruler isn't doesn't make it a bad summary. A summary has to assume some understanding of the subject at hand.
However, for anything written (summary, abstract, article, etc.) the audience should be considered, and the appropriate degree of explanation presented.
Re:Hello, context??? (Score:4, Funny)
Re: (Score:2)
Trick is though, the summary kind of makes us decide to click the link. One sentence of the applications would've been enough. Still, it didn't really bother me, as I already knew what a Golomb ruler was.
Re: (Score:2)
Re: (Score:2)
I tend to scan /. through Google Reader, so I don't get any of the hyperlinks normally found in the summary. I shouldn't have to link to the /. story to link to a Wiki entry on what is clearly an obscure topic.
whatcouldpossiblygowrong (Score:2, Funny)
Re: (Score:2)
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
What will be their next project? (Score:4, Interesting)
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.
Re: (Score:2)
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)
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)
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.
OK, here is a calculation (Score:4, Informative)
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:
This of course doesn't take into account future improvements in CPU efficiency.
Re:OK, here is a calculation (Score:4, Insightful)
According to this page [pcstats.com], the same PC I mentioned before uses up 40 more watts when under full load than when idling. That's about 27% of the 150 watts I mentioned before.
These figures are just ballpark numbers which give a rough idea. There are all kinds of people running these programs... Some make computer farms specifically to run them, some others don't buy new computers but leave theirs when they otherwise wouldn't, and then there's those who don't change their habits because of distributed computing. There's everything in between as well, making it very hard to estimate the real impact.
Re:What will be their next project? (Score:4, Insightful)
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)
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
so we get cheaper, better antennas? (Score:4, Insightful)
Re:so we get cheaper, better antennas? (Score:5, Informative)
Re: (Score:3, Insightful)
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).
Re: (Score:2)
Re:so we get cheaper, better antennas? (Score:4, Informative)
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.
very interesting (Score:2)
Re: (Score:2, Informative)
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: (Score:2)
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
Re:so we get cheaper, better antennas? (Score:5, Informative)
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.
can someone please tell me which #s aren't incl? (Score:2, Interesting)
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)
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:can someone please tell me which #s aren't incl (Score:5, Funny)
a few lines from Python would say
Then shalt thou count to three, no more, no less. Three shall be the number thou shalt count, and the number of the counting shall be three. Four shalt thou not count, neither count thou two, excepting that thou then proceed to three. Five is right out.
Re: (Score:3, Insightful)
Re: (Score:2)
Re: (Score:3, Informative)
#!/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
I can do better than that... (Score:4, Funny)
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...
wut? (Score:2)
parser: no such token "yumiz"
parser: no such token "emh's"
parser: all you pins are like the belong to us
You mean "angels"? (Score:2)
If you're trying to call us pinheads your ruler needs to be calibrated in angels.
Pigeon (Score:2)
You don't need 8 years to design a ruler to measure a pigeon. That's just plain dumb.
Playing Cards Puzzle (Score:2)
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.
Re:Not Bush? (Score:4, Funny)
Re:proved? (Score:5, Insightful)
Yes. Yes, you did.
Re:proved? (Score:5, Funny)
But you can't prove that, which proves his point.
Re: (Score:2)
Yes.
Re: (Score:2)
Apparently so.
Re:proved? (Score:5, Insightful)
Mathematics may be defined
as the subject in which we
never know what we are talking
about,nor whether what we are
saying is true.
--Bertrand Russell
Re: (Score:2)
Re: (Score:3, Insightful)
Hasn't GÃdel done pretty much exactly that? [wikipedia.org]
Re:proved? (Score:5, Informative)
Re: (Score:2)
Re: (Score:2)
apologies to all the yes men and for the record, my TI-89 did all the math for me...
Re:proved? (Score:5, Informative)
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.
Re:proved? (Score:5, Funny)
You just reminded me of......
Ah, Kryten; just thinking. [Rapidly] Assuming of course we're not dealing with five-dimensional objects in a basic Euclidean geometric universe and given the essential premise that all geo-mathematics is based on the hideously limiting notion that one plus one equals two, and not as Astemeyer correctly postulates that one and two are in fact the same thing observed from different precepts, (Pulls a "nerdy" grimace, and loudly exhales through his nose.) the theoretical shape described by Siddus must therefore be a poly-dri-doc-deca-wee-hedron-a-hexa-sexa-hedro-adicon-a-di-bi-dolly-he-deca-dodron. (Pulls the same face, exhales a second time.) Everything else is poppycock. Isn't that so?
Re:proved? (Score:5, Funny)
Re: (Score:2)
Completely unrelated, but I think the coolest shape name is the disdyakis triacontahedron.
http://en.wikipedia.org/wiki/Disdyakis_triacontahedron [wikipedia.org]
Re: (Score:2, Insightful)
Re:proved? (Score:4, Informative)
> 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: (Score:2)
Unlike science, math has no reality connection. There is no requirement for math to portray reality or hold up to experiments or anything like that. Valid math is math that stays within the rules.
Re: (Score:2)
One that easily comes to mind is the axiom of choice ( http://en.wikipedia.org/wiki/Axiom_of_choice [wikipedia.org] ). I remember, during my math topology studies, having to actually assume the axiom of choice for certain demonstrations (ie: the demonstration would be invalid if you don't consider the axiom of choice true).
Such an axiom, can be chosen as true or false, but cannot be demonstrated. Nowadays, the axiom of choice is generally assumed (ie: the mathematics branches that we generally studies include that axiom),
Re: (Score:2)
Assumptions cannot be dubious.
They may be not of your liking, but that hardly makes them dubious.
Re: (Score:2)
Re: (Score:2)
From XKCD: Certainty [xkcd.com]
Aikon-
Re:Story (Score:5, Insightful)
why the hell is everything tagged "story"?
I have another question. What happened to the option to turn off tags?
And one more: Is there any forum to discuss Slashdot issues? Seems like the only way is to bitch off-topic in the articles.
Re:Story (Score:5, Funny)
Re:Story (Score:5, Insightful)
No, you can directly email them but of course they will only use that as ammunition to be taken out of context and savaged via the poorly conceived "Disagree Mail [slashdot.org]" "Feature".
I'd leave, but there isn't really an alternative that's better. Instead I use adblock and suck off this teat without providing benefit to the site. (Unless you include this post as "providing benefit" which is dubious since it will almost certainly get modded down.)
Re:Story (Score:5, Informative)
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.
Re:Story (Score:5, Funny)
Actually, when I mouse over tags I get an incomprehensible mess of overlapping elements. It's probably my fault for using something as obscure as Firefox, though; I'm sure it works perfectly on IE6.
Re: (Score:2)
The type of OCD that makes one check /.
Re: (Score:2)
Umm... 6 * 12oz > 40oz
That's true not only in terms of volume, but also price (it's an economy joke).
Re: (Score:2)
Not going to take the political bait, but I have to say I would be Joe Dead before I was Joe Colt 45.
Re:It hasn't been proven, it has been shown. (Score:5, Insightful)
Yes, people routinely get this wrong. They're not wrong this time.
In this case, the distinction between "it was proven" and "it was shown" is a distinction without a difference. In math, you can "show" something within a restricted domain; for example, that a postulated solution to a given equation really is a solution, without giving a complete family of solutions. One can show it numerically, or show it analytically. Here, a restricted set of postulated solutions over the only available domain (the positive integers) was exhaustively searched for actual solutions, and the set that satisfied the postulates was also shown to be optimal (in a well-defined sense for the problem).
This is no more a "non-proof" than the proof of the 4-color map theorem in two dimensions, which was also "shown" using an exhaustive search.
Bah, Humbug! (Score:5, Insightful)
There is a BIG difference between [proven and shown] as anyone within the Maths and the Sciences can tell you. I'm sorry, but people routinely get this wrong and it gets quite aggravating.
First, there is such a thing as proof by inspection. It may be considered inelegant by certain folks, but it's there nonetheless.
Second, it's just as aggravating (for those in certain fields) that computational results are not more valued. Sure, analytical results provide insight that computational results do not. But if you simply want to know the answer, why not accept a computational result?
Third, anticipating the old "how do we know the computer didn't make a mistake" comment: Theoretical proofs need to be proofread just as code does. So why not accept a computer program (and its verified output, as in the summary) as proof?
That's enough of a proof (Score:5, Informative)
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.
Re: (Score:2)
Certainly.
The proof, however, is not very elegant. Unfortunately, brute force is the best tool we have for certain "hard" problems.
Re: (Score:2)
Define "elegant".
Fortunately we do have more and more powerful brute force systems these days.
I don't agree with the definition that any brute force tool is "inelegant", or lacks "mathematical beauty". In those cases, one should try to find elegant brute force algorithms. For instance, I think the fast Fourier transform is a very elegant algorithm, because it's rather simple yet ingenuous
Re:That's enough of a proof (Score:4, Informative)
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: (Score:2)
No it's not. There are some number systems where this is false. So if you don't state 2., you'll have to state something which restricts you anyway.
Re: (Score:2)
These kinds of number fields occur in lots of applications, eg in cryptography: fast factorization is the key to eavesdropping and will make you rich. Enough motivation for you? ;-)
Re: (Score:2)
Actually, I think you only need to go up to the halfway point. After that, if it were evenly divisible, it would have already been taken care of by something smaller.
Re:That's enough of a proof (Score:4, Funny)
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.
The one where you claim 1 is not a factor of 7....
Re: (Score:2)
Heh, I had a good laugh out of this stupidity myself...
Re:I would really like to understand this. (Score:4, Informative)
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.
Re: (Score:2)
Could a valid and perfect ruler not be made in the form of 0,1,3,6,10,15,21,28,36,etc to infinity?
No. Because the ruler looks at the distances between ALL the various makes on it. So in your example, it's invalid because the distance between 0 and 3 is 3 and the distance between 3 and 6 is 3. (Same issues with 0,6 and 15,21, etc.) You're aiming to find something where no two points are the same distance apart, not just adjacent points.
That said, I'm just going off the wikipedia article myself too, so if someone who knows better than me cares to comment, feel free to jump in.
Re:cool! (Score:5, Funny)
Re: (Score:2)
Oh good, I wasn't the only one who read the entire thing waiting for a reference to (the) TFA.
Re: (Score:2, Insightful)
Re: (Score:2)
Not really. You need a function which is in P but whose inverse is NP-hard.
Re: (Score:2)
In theory HIGGS particle should exist and standard model is true but dozens of countries and thousands of scientists have built the biggest machine ever known to prove it exists or not. If it doesn't exist, it will also serve to science too.
http://en.wikipedia.org/wiki/Large_Hadron_Collider [wikipedia.org]