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

61–70 of 189 posts

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

#61

Post by Sharlin »

lupire wrote: post #37
dannyz wrote: post #2

It is always fascinating how many problems that are simply stated are difficult to solve. Whenever I see something like this I try and think about what the repercussions would be if an efficient algorithm did exist, and that helps to understand where the complexity is. In this case I believe there would be many problems in computational geometry involving Euclidean shortest paths that would be made trivial by an effi…

This problem is only hard when infinite precision is needed. It's trivial if you allow any tolerance on the scale that could exist in the Universe.

However, it would be interesting to find some pathological examples of pairs of lists whose sums of square roots compare almost equal if only approximated to some reasonable precision, but diverge absurdly if the fully general algorithm is used, if such pairs even exist.

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

#62

Post by syki »

pfortuny wrote: post #55
syki wrote: post #50

Earlier quoted context omitted.

They are using a different notion of “measure” than the standard notion of absolute value of the difference. Under the standard measure every number is within epsilon distance of a rational for any positive epsilon. Thank you for the clarification.

Yes, of course. Sorry. It is an asymptotic result, so the meaning of "distance" is very blurry in my statement. I was replying to the previous comment which seemed to imply that knowledge.

I’ve never seen this before so thanks for the links and clarification. I learned something new.

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

#63

Post by Tyr42 »

zelphirkalt wrote: post #45
ufo wrote: post #38

Earlier quoted context omitted.

Input length in binary is the standard way to calculate computational complexity. Sometimes we handwave that away, but in problems like this where the size of the number matters, we stick to the more strict definition of computational complexity. Number in binary vs number in decimal doesn't make a big difference because it's just a constant factor.

Thanks really. I guessed as much. What about the other questions? How do you get to an input length from a list of numbers? Just concattenate all their binary digits? Can you answer any of these?

We could instead specify the length (in characters) of a json list representing the two inputs: "[[1, 17, 8], [2, 6, 9]]" if we wanted to. It's base ASCII (i.e. 128 I guess), but unambiguous, and the same up to a multiplicative constant, right?

That solves needing to figure out an encoding scheme for arbitrary length binary number lists.

Or use a trinary encoding, with the set {"0", "1", ","} to let you list numbers nicely if you want. It doesn't matter that much.

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

#64

Post by parhamn »

ismayilzadan wrote: post #47
umvi wrote: post #44

It's hard to solve "generally", sure, but "practically", is there any application where extreme correctness of the algorithm would actually matter? Seems like if two huge lists sum to almost the exact same thing for tons of decimal places, then you can effectively treat them as equal. Sort of like how you only need like 5 or 6 digits of pi to get into orbit around the moon, etc.

If question asked for just returning the sum, then yea, that would be acceptable. However, the question requires the comparison of sums. To decide which one is actually larger, 5-6 digits is not enough, even "practically".

It's not really different. If you were given the sums in the first operation to 5-6 digits and it was acceptable error margin, the comparison is within that acceptable error margin too, it's just this time the error led to a wrong binary not a wrong decimal.

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

#65

Post by abetusk »

misja111 wrote: post #5

It probably has been tried already by someone, but how about this: all square roots can be written as repeating continued fractions [1]. With a bit of work, continued fractions can also be summed [2] and compared. Wouldn't this take less than exponential time? [1] http://benpaulthurstonblog.blogspot.com/2012/05/estimating-s... [2] https://www.jstor.org/stable/1969389

The article points to a Facebook post that considers this method and then is subsequently invalidated [0].

The argument is that the continued fraction representation for sqrt(N) grows as O(lg(N) sqrt(N)), making the representation blow up.

[0] https://www.facebook.com/bshlgrs/posts/10215278471769811?com...

[1] https://mathworld.wolfram.com/PeriodicContinuedFraction.html...

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

#66

Post by abetusk »

devit wrote: post #57
fdej wrote: post #14

> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to establish some kind of bound on this. Like, maybe we should be able to say “if you add two lists of n numbers, each of which has d digits, then they can’t disagree for more than k * n * d digits” for some k. But no-one’s been able to prove anything like this. You c…

Does that actually work? It seems that the degree of minimal polynomial having as root the sum of N square roots might be up to 2^N, and if you then apply the bound at https://en.wikipedia.org/wiki/Geometrical_properties_of_poly... (where n = 2^N) you get a bound on the order of at least 2^N digits (more precisely 2^N (N + D)). So it doesn't seem to lead to a proof of a subexponential number of equal digits, unless t…

Why do you need the bounds for every combination of the N square roots? Isn't it enough to get the minimum distance between the two nearest elements in that list?

If so, why not consider the 2N degree polynomial where P(z) = \prod (z^2 - a_i) ? This polynomial is only 2N degree and gives you the bound you actually care about, the number of bits needed to sum two numbers in the list. Since you're summing 2N of them instead of just one, you might need on the order of lg(N) more bits in your representation (so 2N + lg(N) bits, say) but this is still well within "polynomial" bits.

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

#67

Post by vessenes »

Sharlin wrote: post #61
lupire wrote: post #37

Earlier quoted context omitted.

This problem is only hard when infinite precision is needed. It's trivial if you allow any tolerance on the scale that could exist in the Universe.

However, it would be interesting to find some pathological examples of pairs of lists whose sums of square roots compare almost equal if only approximated to some reasonable precision, but diverge absurdly if the fully general algorithm is used, if such pairs even exist.

I am reasonably sure that this won’t happen, or said another way, a function that returns the minimum delta between any finite pairs of lists is a reasonably well behaved function wrt the length of the list and the size of the integers and doesnt just zoom off to infinitely close to zero ever.

Said yet another way, the ways in which real numbers are dense is spooky and almost totally untied to how rationals work, and i do not believe you can get there from here using square roots.

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

#68

Post by xboxnolifes »

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…

It seems less crazy when you think about the fact that actual ground breaking math has been solved on scrap paper and rudimentary writing utensils. Sometimes all it takes is the right person being prompted with the question.

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

#69

Post by Someone »

erwincoumans wrote: post #13

>> Suppose that I can find some lists of numbers whose sums of square roots are equal for the first ten million decimal points and then start being different Would have been nice to add an example of such list in the blog, I wonder how short that list can be. Also, how important is this in practice? The algorithms using this comparison could handle the 3 cases with a tolerance (larger, smaller, undecided)?

Very short, expressed in number of items in the lists. Once N is large enough, these two single-item lists have that:

First list: (N)

Second list: (N + 1)

N = 10^10^15 is large enough for that.

I think you can construct much smaller examples by looking at Pythagorean triples. Since 3² + 4² = 5² and 5² + 12² = 13², the lists (9k, 16k, 169k) and (25k, 144k, 25k) have the same sum of square roots (22√k) for all k. Subtract one from one of the numbers, and you’ll have a close match, say with error e.

Do the same for a second pair of Pythagorean triples, giving you an error of f. Compute a good rational approximation p/q of e/f, and linearly combine the pairs of sets to get any arbitrary small difference (edit: that construction works starting with any two sets of two sets of numbers)

And I don’t think there is an “in practice” for this problem. When do you ever have to make this computation? If ever, does it matter if your code fails on a tiny fraction of all inputs?

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

#70

Post by zodiac »

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…

But the article presents it as an interesting pure math problem, and doesn't claim that the FP64 solution isn't good enough.

I should add that the people who write state of the art "practical" TSP solvers spend a lot of time thinking about the "theoretical" complexity of it too. Turns out it's a good way to engineer those "good enough" algorithms, provide bounds etc

Post reply on HN