A surprisingly hard CS problem: sums of square roots (2018)
1–10 of 189 posts
Re: A surprisingly hard CS problem: sums of square roots (2018)
#2It 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 efficient algorithm here.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#3[deleted]
Re: A surprisingly hard CS problem: sums of square roots (2018)
#4Relevant material on exact real computation:
Wikipedia article: https://en.wikipedia.org/wiki/Computable_analysis
Book: https://link.springer.com/book/10.1007/978-3-642-56999-9
Re: A surprisingly hard CS problem: sums of square roots (2018)
#5It 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...
Re: A surprisingly hard CS problem: sums of square roots (2018)
#6[deleted]
Re: A surprisingly hard CS problem: sums of square roots (2018)
#7This 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.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#8It 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
In practice I think the problem is linear, in that the required precision is proportional to log maxValue, that would be enough for a certain answer.
It's just that a proof of this is considerably harder, since you can't just assume the fractional part of irrational numbers is random.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#9It reminds me of this problem. When you plot the motion of conservative dynamical systems, say this one
https://en.wikipedia.org/wiki/Standard_map
you get these chaotic areas that look like television static on the map. I was reading an 1987 article from Byte magazine that reminded me of a conversation I had when I was working on my PhD, which is that every plot like this you see is wrong because these are done with finite precision math and it doesn't take that many iterations for calculation errors to be amplified up to the first digit.
It's significant because the reason we know those chaotic regions are full of unstable periodic orbits is that those chaotic regions are also full of stable periodic orbits and that those breed unstable periodic orbits on the separatrices between them. The stable orbits form a hierarchical lattice that constrains the chaotic motion and that should appear as visible structure.
There are hints in the literature that it ought to be possible to use variable precision interval math to do parameter scans, make better images, and more accurately understand the chaotic motion. On top of that we know a lot about how the stable periodic orbits relate to each other which would help in making that kind of image.
I haven't seen any evidence that it's been done and I know one reason it is hard is that the scaling of the algorithm would be worse than the usual way of doing things for the same reason the above problem is hard.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#10It 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
Without looking into the details, the problem might be that two n-bit numbers x and y might have continued fractions for sqrt(x) and sqrt(y) which differ very far along. Also, the continued fractions themselves can get more and more expensive to compute as you go along; possible exponentially more, but I'm not sure.
Also, two continued fractions are not necessarily easy to compare. It's not a positional notation like decimal or binary.