Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A surprisingly hard CS problem: sums of square roots (2018)

shlegeris.com

Post reply on HN
Print view View original

131–140 of 189 posts

Re: A surprisingly hard CS problem: sums of square roots (2018)

#131

Post by kmill »

thomasahle wrote: post #97
mabbo wrote: post #15

The part of this post that I find most wonderful/strange: > EDIT: I think that Edward Kmett and Paul Crowley might have figured out how to solve this problem in the comments on my Facebook post; see here. I’ll investigate further and update. > EDIT 2: actually we didn’t solve the problem, but it might still be a good direction for future research. Possibly ground-breaking math being done on comments on a Facebook pos…

I don't know if Dunning Kruger effects on Facebook posts are anything new/wonderful/strange. This thread reads like somebody who just heard about the Collatz conjecture, and after half an hour are sure they have a solution.

What a strange coincidence: 17 hours ago Edward Kmett tweeted about Dunning-Kruger https://twitter.com/kmett/status/1485464550786883588?s=20

Re: A surprisingly hard CS problem: sums of square roots (2018)

#132

Post by curiousllama »

mabbo wrote: post #15

The part of this post that I find most wonderful/strange: > EDIT: I think that Edward Kmett and Paul Crowley might have figured out how to solve this problem in the comments on my Facebook post; see here. I’ll investigate further and update. > EDIT 2: actually we didn’t solve the problem, but it might still be a good direction for future research. Possibly ground-breaking math being done on comments on a Facebook pos…

> My guess is that [...] we’re just stuck on proving it because [...] most of the people who would be good at working on this are doing something more useful instead.

Evidently not

Re: A surprisingly hard CS problem: sums of square roots (2018)

#133

Post by cyberbanjo »

fbanon wrote: post #46
mabbo wrote: post #15

The part of this post that I find most wonderful/strange: > EDIT: I think that Edward Kmett and Paul Crowley might have figured out how to solve this problem in the comments on my Facebook post; see here. I’ll investigate further and update. > EDIT 2: actually we didn’t solve the problem, but it might still be a good direction for future research. Possibly ground-breaking math being done on comments on a Facebook pos…

*yawn* https://www.theverge.com/2018/10/24/18019464/4chan-anon-anim...

> “This proof shows that you don’t need to be a professional mathematician to understand mathematics and advance the frontier of knowledge,” Pantone says. “That’s the beautiful thing about math, is that anyone can understand the questions.”

or that prof math post on 4chan?

Re: A surprisingly hard CS problem: sums of square roots (2018)

#134

Post by gfody »

munificent wrote: post #100

> I’m going to update towards thinking that integers and square roots are much scarier, richer objects than I’d thought. I’ve updated to being more scared of real numbers than I used to be—they have all these sketchy properties like “almost none of them have finite descriptions”. Real numbers, and sets, and logical statements, have all started feeling to me like Cthuluesque monstrosities whose appearances are only to…

> there is something profoundly weird about [numbers]

you should hear John Conway (RIP) talk about numbers - https://www.youtube.com/watch?v=1eAmxgINXrE

Re: A surprisingly hard CS problem: sums of square roots (2018)

#135

Post by pontifier »

varelse wrote: post #36

This problem is a perfect example of better is the enemy of good enough. What's striking here is that the simple FP64 solution is for the most part more than good enough for any practical application you would find working in Tech. Anything beyond that is likely unnecessary gold plating. If I were asked this on a job interview and they didn't accept that answer and started going on about me missing the pure math here…

Exactly! Write the best, simplest, acceptable working code you can, and then put a comment in there that if someone has an issue with it, they are welcome to improve it...

if (.1 + .1 != .2): reason = "we can't have nice things."

Re: A surprisingly hard CS problem: sums of square roots (2018)

#136

Post by xxpor »

JadeNB wrote: post #92
balnaphone wrote: post #91

Earlier quoted context omitted.

May I ask, for what reason, please?

Personally, I prefer not to get surprise PDFs; but that's just personal. A better reason is that linking to the abstract page lets you navigate easily around the arXiv from there, including to the PDF if you desire; but there is no 1-click way to get from the PDF back to the abstract. (Of course, it's an easy matter of address munging, but even easier is not to have to do the munging.) A perhaps less satisfying reaso…

Multiple people have said they prefer not getting surprise PDFs. Could you elaborate on why? It's never something I've ever thought about. PDFs open in the browser now for most people, so it seems like it shouldn't make much difference?

Re: A surprisingly hard CS problem: sums of square roots (2018)

#137

Post by ogogmad »

varelse wrote: post #117
CJefferson wrote: post #115

Earlier quoted context omitted.

Looking at your original reply, you started bringing in "job interviews" and "companies that ship". I imagine that's why people downvoted you -- this post (and replies) are about maths, not worrying about really companies. The original post wasn't about practical software, or shipping products, or getting a "good enough answer". It was about an interesting (to many people) maths problem. If you want ycombinator to ju…

And I admitted it's a cool pure math problem. The challenge in the tech industry is balancing the rigor of a pure but nearly intractable solution with using the theory to pump up an O(n) imperfect solution to acceptable reliability. I find the latter more interesting, YMMV. But if that isn't as interesting as the original problem, maybe stay in academia? AI itself is an example of tailoring activation and pooling fun…

Making things hard sometimes leads to insights down the line. For instance, the formula for solving cubic equations seems kind of silly from a numerical point of view -- you can just use a general-purpose numerical algorithm to solve cubics. But the research into solving cubics using restricted operations led to the discovery of the complex numbers, group theory, and the theory of fields, etc. So it was worth doing things the hard way and sticking to the letter of the problem.

Likewise, the ideas people use to solve the problem in the article may have applications elsewhere.

I do sometimes have doubts about whether this is the most efficient way of discovering scientific ideas: Posing puzzles and seeing what tools people throw at them. So I can see the criticisms coming...

Re: A surprisingly hard CS problem: sums of square roots (2018)

#138

Post by tgflynn »

It seems like this should just reduce to the question: given two natural numbers x and y represented by n bits how many bits are needed to represent the difference sqrt(y) - sqrt(x) so that it is non-zero when x != y. To see this suppose you compute each sqrt in both lists to k bits then group together the closest matching pairs from the two lists. Some of these pairs may have a difference of zero. Now increase k until all of the pairs are distinguished (have non-zero differences). At that point you know the answer, you just have to add up the differences.

As for the first question it should take no more than n bits because sqrt(x) is a contraction at least for x >= 1 as is obvious from its graph compared to that of f(x) = x.

Re: A surprisingly hard CS problem: sums of square roots (2018)

#139

Post by amelius »

> comparing sums of square roots is actually kind of a common subtask in eg computational geometry, so a bunch of their problems (including “shortest path through a graph in Euclidean space”!) are as-far-as-we-know extremely hard.

But the question then arises: do we always need to solve these problems to their fullest precision? Can we perhaps leave some ambiguity, and let the system gracefully deal with it? E.g. I don't care if my CAD model has a tiny chip of 1e-12 mm missing, as long as my CAD software doesn't crash on the resulting internal inconsistencies.

See also, e.g.: https://www.cs.purdue.edu/homes/cmh/distribution/papers/Robu...

Re: A surprisingly hard CS problem: sums of square roots (2018)

#140

Post by IIAOPSW »

curiousllama wrote: post #132
mabbo wrote: post #15

The part of this post that I find most wonderful/strange: > EDIT: I think that Edward Kmett and Paul Crowley might have figured out how to solve this problem in the comments on my Facebook post; see here. I’ll investigate further and update. > EDIT 2: actually we didn’t solve the problem, but it might still be a good direction for future research. Possibly ground-breaking math being done on comments on a Facebook pos…

> My guess is that [...] we’re just stuck on proving it because [...] most of the people who would be good at working on this are doing something more useful instead. Evidently not

Most of the people who would be good at working on this are working on getting people to click ads instead.
Post reply on HN