Would the naive approach "just work" (although slowly) in Python since it has arbitrary precision?
Python has arbitrary integer precision, that won't help
A surprisingly hard CS problem: sums of square roots (2018)
121–130 of 189 posts
Re: A surprisingly hard CS problem: sums of square roots (2018)
#122> 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…
I'm wrong. The Mahler-Mignotte only works for pairs of roots and doesn't say anything about the absolute value of the sum, at least in the way I was thinking about it. There may be a way to "fix it up" but not that I see and I suspect folks who've studied this in earnest are aware of Mahler-Mignotte and understand why it can't be used to solve this problem.
Thanks to @devit [0] who has understood why the Mahler-Mignotte tactic doesn't work. Just because you can bound the bit complexity of pairs of roots doesn't mean you can bound the complexity of all the 2^N possible {-1,1} combinations of them. At least, I don't see how it can be done simply.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#123Earlier 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.
Since your finite-precision initial conditions are probably not on any stable orbits, I'm not sure how much that interferes with the truth of Ted's explanation.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#124It'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 have an very efficient and "practical" algorithm for determining the score in a sports match. In almost all cases it tells us which team had the higher score -- the only time it fails is when the game in close. In those cases, it can't accurately tell who won.
It SOUNDS like a very practical algorithm, but in reality it's precisely in the "close" cases where people care the most.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#125Earlier 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?
It doesn't really matter. Use 11 for 1, 00 for 00 and 01 for next number. Most ways you can come up with have the same length up to multiplying with some constant, and the constant does not matter in the analysis.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#126So 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…
> EDIT: Doesn’t https://www.sciencedirect.com/science/article/abs/pii/S00200... show that this algorithm is in fact polynomial?
No, they give a linear lower bound for the number of digits you need to compute and show that the bound is tight for certain special numbers, but they don't have a polynomial upper bound for the general case.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#127Earlier quoted context omitted.
You just have to take out square factors from each, and combine terms with matching sqrt(n), and that will be unique
How do you know its unique?
I don't think there's an elementary proof, but you will see a proof if you study algebraic number theory.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#128This 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…
No, it's not a perfect example of better being the enemy of good enough. You're just missing the point. Nobody is using this as an interview question.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#129Earlier quoted context omitted.
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…
A request: please always link to abstract pages of articles, not directly to PDFs. https://arxiv.org/abs/2005.07843
You can also go straight to the abstract from PDF links using the "Redirectify" browser add-on for Firefox and Chrome.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#130I'm not sure why the square root matters in here, it seems like a more general problem of storing an unbounded array of arbitrary precision digits. Wouldn't you run into the same problem with doing simple addition on an array that includes pi to infinite precision?