Would the naive approach "just work" (although slowly) in Python since it has arbitrary precision?
Python doesn't use arbitrary precision for floating point values, it just has arbitrarily long integers.
A surprisingly hard CS problem: sums of square roots (2018)
111–120 of 189 posts
Re: A surprisingly hard CS problem: sums of square roots (2018)
#112Would the naive approach "just work" (although slowly) in Python since it has arbitrary precision?
Python does not have arbitrary precision for floating point
Re: A surprisingly hard CS problem: sums of square roots (2018)
#113It'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.
I think that's basically fair. If we were dealing with the reals I'd assume that there was some uncountable number of pathological examples that just happen to exclude all the numbers we really care about (since God ran out of good numbers and had to scrape the bottom of the barrel to fill in the gaps), but the integers seem safe.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#114Re: A surprisingly hard CS problem: sums of square roots (2018)
#115Earlier quoted context omitted.
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
Sure and there are a lot of simple ways to improve the accuracy of the simple approach before you go for the pure math sledgehammer here. It's all a question of how accurate the answer needs to be. For example, It's pretty easy to come up with an FP64 error bound on the sum. And if the difference between the two sums is greater than that error bound you don't need to do anything more complicated. Where this would get…
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 just be about companies and shipping products, then indeed it "has changed". But many people (myself included) like a good pure maths puzzle, and are interested in if there is a "true answer".
Re: A surprisingly hard CS problem: sums of square roots (2018)
#116I wonder if comparing powers of sums would help? Suppose one of the sequences was 3, 7, 15, 30, and consider s = √[3] + √7 + √15 + √30. Then s^2 = 55 + 30 √2 + 6 √5 + 6 √10 + 2 √21 + 2 √105 + 2 √210. s^3 = 159 √3 + 90 √6 + 151 √7 + 90 √14 + 135 √15 + 105 √30 + 18 √35 + 18 √70. ... s^30 = 1679613741139712617544067791402275 + 1187666266098277047375460186425450 √2 + 750901847525954802822187362608010 √5 + 530967788407084…
Doesn't help, because if you start with the sum of N square roots you end up (in the general case) with 2^N square roots once you raise it to a power.
I was curious how this would play out and didn't see your comment, so I made a Jupyter notebook of raising various sums of square roots to various powers. Posting in case anyone else finds it interesting: https://gist.github.com/chrisshroba/8f12757ecbcdd394ceccb3e9...
Re: A surprisingly hard CS problem: sums of square roots (2018)
#117Earlier quoted context omitted.
Sure and there are a lot of simple ways to improve the accuracy of the simple approach before you go for the pure math sledgehammer here. It's all a question of how accurate the answer needs to be. For example, It's pretty easy to come up with an FP64 error bound on the sum. And if the difference between the two sums is greater than that error bound you don't need to do anything more complicated. Where this would get…
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 functions to deliver imperfect solutions that are "good enough" to ship. It's unfortunate these two viewpoints are seen as contradictory rather than complementary, but that does echo our political balkanization so I guess I shouldn't be surprised.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#118So let’s say we start with computing the square roots to X digits of precision after the decimal point. Then we add up lower and upper bounds, giving us intervals for the sums over the two lists. If those intervals overlap we have to go back and compute e.g. 2X digits of precision, and so on. But in most cases we’d be done after the first iteration.
Seems to me that would be polynomial in the average case. The worst case could of course be really bad. But if you’re telling me you know for sure that it’s exponential, then you must know something about the existence of lists with very close sums. As I understood the OP we don’t know if such lists exist.
So average time complexity is polynomial and worst case is unknown.
EDIT: Doesn’t https://www.sciencedirect.com/science/article/abs/pii/S00200... show that this algorithm is in fact polynomial?
Re: A surprisingly hard CS problem: sums of square roots (2018)
#119Earlier quoted context omitted.
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 in…
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 together.
In other words, say you have d_0 = |a_0 - a_1| and d_1 = |a_2 - a_3|, you might get into a situation where |d_0 - d_1] requires some exponential number of bits to represent.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#120This looks more like a problem with ( my understanding of ) complexity theory in general. Categorizing problems by "The size of the input" is too imprecise when irrational numbers are a part of the problem.
I would say that imprecision is somewhat artificially induced by the fact we so thoroughly use IEEE floats that we tend to assume that they are the only numbers. When invoking arbitrary-precision floats (or equivalent), pretty much all numerical calculations get a lot harder than we intuit instantly. So much as comparing one number to another without taking a square root goes from O(1) to O(n) for n = the representat…
> the real universe we live in bottoms out at 10^-35 meters or so
We don't actually know this. It's a plausible speculation in quantum gravity, but we have no evidence either way. This length scale is about 18 orders of magnitude smaller than the smallest scale we can probe with experiments, so we're highly unlikely to get any evidence either way any time soon.