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

Post by whoomp12342 » Mon, Jan 24, 2022, 4:57 PM UTC

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

Post by JadeNB » Mon, Jan 24, 2022, 5:01 PM UTC

abetusk wrote: post #49

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…

So, to state explicitly, given a list of positive integers, a_i, and coefficients, d_i \in {-1,1}, test whether \sum_i d_i sqrt(a_i) I guess there's different levels of bounds you can use (Mahler, Mahler-Mignotte, Davenporte-Mahler-Mignotte [0]) but they all involve the discriminant, the deg to the deg power (n^n) and maybe some other factors which put it neatly in a polynomial time bit representation. One bound puts…

Post by ianthehenry » Mon, Jan 24, 2022, 5:07 PM UTC

breezeTrowel wrote: post #75

I'm not sure I understand the problem. If we only need to determine what set produces a sum of square roots that is larger, why can't we simply compare the sum of the original numbers? The square root of 2.0000001, for example, is larger than the square root of 2. The square root of X will be always be larger than the square root of Y if X is larger than Y. The real problem is calculating the precision of square root…

Post by umvi » Mon, Jan 24, 2022, 5:10 PM UTC

whoomp12342 wrote: post #71

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.

we are talking about math here, there are always applications even ones where we dont know in this day and age. I am positive the same question could be been asked about basic calculus concepts in the 12th century.

Post by varelse » Mon, Jan 24, 2022, 5:14 PM UTC

zodiac wrote: post #70

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