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

141–150 of 189 posts

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

#141

Post by FabHK »

xxpor wrote: post #136
JadeNB wrote: post #92

Earlier quoted context omitted.

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?

I was going to add that some people on slow connections might not want to download large PDFs.

However, in today's web, the html page with the abstract (one paragraph) was a 2.5 MB download, while the 15 page paper including a figure was just 800 kB.

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

#142

Post by cevi »

An example of a tricky case: which is bigger, sqrt(1000000) + sqrt(1000018) + sqrt(1000036) + sqrt(1000059) + sqrt(1000083), or sqrt(1000003) + sqrt(1000011) + sqrt(1000048) + sqrt(1000050) + sqrt(1000084)? (They agree to more than 20 decimal digits of precision!)

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

#143

Post by tgflynn »

abetusk wrote: post #119
devit wrote: post #83

Earlier quoted context omitted.

Not clear how a lower bound on the absolute value of the difference of any two of the square roots would help give a lower bound on the absolute value of the difference of the two sums of square roots.

Sorry to be obtuse, but I don't understand your hesitation. If you have a lower bound on the absolute value of the smallest difference of any/all pairs of roots, the lower bound on the sum of N of them is at most adding lg(N) bits. EDIT: I'm wrong, you're right. You've hit it on the head. My apologies. Just because there's bounds on pairwise roots, doesn't mean they then can be bounded when they're all summed togethe…

I don't see the problem. Once you have enough bits to resolve every pairwise difference you're just reduced to the problem of comparing the sums of two lists of n bit integers and I'm pretty sure that's in P.

If it's not then that should be the main point here, sqrt has nothing to do with it.

EDIT: You also know what the largest possible error is on each pairwise delta so if you add log(N + 1) bits you handle even the worst case where one sum is +N x maxerror and the other -N x maxerror.

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

#144

Post by antognini »

PaulHoule wrote: post #102
ted_dunning wrote: post #86

Earlier quoted context omitted.

Yes. every plot of a chaotic system is grossly wrong. But the cool thing is that it is imperceptibly different from another plot that is correct. this is a consequence of the shadowing theorem that says that while any finitely computed sequence has unavoidable errors, there is a sequence arbitrarily close to the numbers you do compute. (don't hold me to rigorous statements here, it has been many years) (the gist is r…

My understanding is the shadowing lemma is controversial. For instance it applies to the chaotic orbits but not the stable orbits that are embedded in them.

Wouldn't the KAM theorem apply to the stable orbits?

But for the chaotic orbits there was some good work a few years back by Boekholt & Portegies Zwart. They built an arbitrary-precision N-body integrator and found that the results of ordinary N-body simulations are statistically identical to arbitrary precision integrations: https://arxiv.org/abs/1411.6671

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

#145

Post by kccqzy »

cevi wrote: post #142

An example of a tricky case: which is bigger, sqrt(1000000) + sqrt(1000018) + sqrt(1000036) + sqrt(1000059) + sqrt(1000083), or sqrt(1000003) + sqrt(1000011) + sqrt(1000048) + sqrt(1000050) + sqrt(1000084)? (They agree to more than 20 decimal digits of precision!)

The second is bigger, but only by ~2.3 * 10^(-13).

Very good illustration indeed.

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

#146

Post by varelse »

ogogmad wrote: post #137
varelse wrote: post #117

Earlier quoted context omitted.

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 t…

Not going to criticize you, I think it's a cool math problem, but I've experienced people throwing problems like this at me at job interviews in the past so it echoed. And in those cases, they weren't looking for an answer, they were looking for the answer they knew about and no other answer would do. I once ended an interview early over one of these questions.

I am relentlessly production focused but that doesn't mean I don't like math. But by the time you get to FP64 with this thing, the probability of finding a fail case seems insanely low and in fact for the most part you can provably bound the error of the sum and therefore likely prove you have found the solution. Anything beyond that is a corner case as the mathematicians love to say. And now I see the criticisms coming.

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

#147

Post by klyrs »

tgflynn wrote: post #138

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 unt…

> At that point you know the answer, you just have to add up the differences.

What if your sum in this step is zero?

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

#148

Post by pkrumins »

I don't get it - how is this problem any different than simply comparing two very long integers. Given integers "a" and "b" - determine which one is bigger. You don't know as "a" could be seventy six billion trillion quadrillion digits long and "b" could be even more digits and you never stop comparing them as there are more and more digits. No need for square roots or sums.

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

#150

Post by bshlgrs »

pkrumins wrote: post #148

I don't get it - how is this problem any different than simply comparing two very long integers. Given integers "a" and "b" - determine which one is bigger. You don't know as "a" could be seventy six billion trillion quadrillion digits long and "b" could be even more digits and you never stop comparing them as there are more and more digits. No need for square roots or sums.

Good question :) The difference is that in that case, the problem might take a long time because the input is very long, but in this case, the problem might take a long time even if the input itself is fairly short.
Post reply on HN