14 ms·

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

297 points by EvgeniyZh 5y ago

dannyz 5y ago
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 efficient algorithm here.
- lupire 5y ago
  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.
  - Sharlin 5y ago
    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.
    - vessenes 5y ago
      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.
      - ChrisLomont 5y ago
        This isn't true, which is why the problem lies in the complexity class listed in the article. Arbitrarily bad pathologies exist even for simple inputs.
deleted 5y ago
[deleted]
ogogmad 5y ago
Relevant material on exact real computation: Wikipedia article: https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis Book: https://link.springer.com/book/10.1007/978-3-642-56999-9 https://link.springer.com/book/10.1007/978-3-642-56999-9
misja111 5y ago
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-square-roots.html http://benpaulthurstonblog.blogspot.com/2012/05/estimating-s... [2] https://www.jstor.org/stable/1969389 https://www.jstor.org/stable/1969389
- mihaic 5y ago
  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.
- ogogmad 5y ago
  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.
- contravariant 5y ago
  You're assuming that the period will remain of manageable size. I see no reason why this should be the case. Edit: Also found a more accessible website describing how to do arithmetic with continued fractions: https://perl.plover.com/yak/cftalk/ https://perl.plover.com/yak/cftalk/. In case anyone wants to try it out.
- lupire 5y ago
  Continued fraction approxmations are not a separable monotonically increasing sequence like decimal approximations are (the approximation goes up and down and the error range overlaps other nearby fractions of the same size), so you have no idea when you can terminate a partial computation.
deleted 5y ago
[deleted]
athrowaway3z 5y ago
This 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.
- qsort 5y ago
  Why would it be too imprecise? I agree there are some (many?) problems with some definitions used in complexity theory, but "size of input" is certainly not part of the problem. It can be defined very precisely. I don't see the slightest problem with how it's framed.
  - dooglius 5y ago
    So what is N here? The sequence length, number of digits across all sequence elements, sum of all elements?
    - deleted 5y ago
      [deleted]
    - qsort 5y ago
      N is the sum of the lengths of the elements of all lists, when all elements are written in binary (or any other base, which is the same up to a constant).
- Khoth 5y ago
  Irrational numbers are involved in the problem, but not in the the size of the input, which is a list of natural numbers. There are a number of reasonable ways to encode such a list but they'll all scale in more or less the same way and be equivalent when looking at big O notation.
- deleted 5y ago
  [deleted]
- Frost1x 5y ago
  If you assume that mathematical notation (language) doesn't abstract complexity in a uniform fashion (something you can write and capture meaning with a few symbols isn't inherently more or less complex than something you can write with a lot of symbols), it becomes pretty obvious that something isn't necessarily as simple as it may look at the surface. Having worked in computing for long enough, I'm well aware of this fact in the world of estimating time (which to some degree is estimating complexity) to address a given problem request. I can very easily write down in English a pretty generalized description that you need to: cure any and all forms of cancer. That's a fairly concise request, I can write it in one line, but it hides a mountain of complexity needed to accomplish that. It also doesn't describe what we consider as "cure" or "cancer" which can be ambiguous in some cases. Much of the same is true with seemingly cute conjectures that seem to capture a behavior that may be incredibly complex to prove (if not impossible, e.g. Godel). The Collatz conjecture comes to mind where Paul Erdos famously said something to the effect of "Mathematics may not be ready for such problems."
PaulHoule 5y ago
It reminds me of this problem. When you plot the motion of conservative dynamical systems, say this one https://en.wikipedia.org/wiki/Standard_map 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.
- ted_dunning 5y ago
  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 right)
  - PaulHoule 5y ago
    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.
    - 5y ago
edflsafoiewq 5y ago
> There’s a known, reasonably fast algorithm (in BPP) for checking equality of sums of square roots What is it?
- dooglius 5y ago
  You just have to take out square factors from each, and combine terms with matching sqrt(n), and that will be unique
  - edflsafoiewq 5y ago
    How do you know its unique?
    - aliceryhl 5y ago
      I don't think there's an elementary proof, but you will see a proof if you study algebraic number theory.
    - deleted 5y ago
      [deleted]
  - jepler 5y ago
    That is to say, rewrite each sqrt(N_i) as P_i * sqrt(Q_i) where P and Q are integers and Q contains no squares. So 2 becomes 1 * sqrt(2), 4 becomes 2 * sqrt(1) and 8 becomes 2 * sqrt(2). Now, you can subtract equal terms from each side of the equation and if you can reach 0=0 then the numbers are equal. If you're left with something like sqrt(3) = 5 * sqrt(2) the the numbers are unequal. This stems from the fact, that I give without proof, that for integers X, Y and Z that contain no squares that sqrt(x) + sqrt(y) is never equal to sqrt(z). So there's no way to (say) add a bunch of square roots of 2 and have it become equal to a square root of 3 or 5. A number contains no squares if its prime factorization contains no repeated factors. Since this seems to involve factorization, plus a step of matching up numbers from both sides, the computational complexity would seem to be at least the complexity of factorization. The term-matching step is presumablty the easier step of the two.
erwincoumans 5y ago
>> 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)?
- dmurray 5y ago
  I expect not very important in practice, because 1. We've settled on using IEEE 754 floating point numbers, and all their tolerance quirks, in practice, and still the bridges don't fall down 2. The author describes it as a little-studied field where "most of the people who would be good at working on this are doing something more useful instead" But still, useless pure-maths distractions have a way of yielding results in unexpected fields. Maybe, as the author hints, a solution to this problem would bring us some information-theory insights and some new methods for cryptography or compression or whatever else.
- Someone 5y ago
  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?
fdej 5y ago
> 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 can write down a completely explicit bound here using the Mahler-Mignotte root separation bound. More generally, for any algebraic expression involving algebraic numbers, you can bound a priori the number of digits you need to check to determine its sign. When you involve transcendental numbers, things do get much harder though.
- pfortuny 5y ago
  Exactly: algebraic numbers, despite not being periodic, are in general "reasonably far from each other", and especially from rationals. I guess the problem can be solved using what you say, certainly. It is only transcendentals that can be "too near" each other, and near rationals (this is Liouville's result, which was improved later on, in a specific case the one you say).
  - syki 5y ago
    Rational numbers are algebraic so how are algebraic numbers reasonably far from each other? Algebraic numbers are dense in the real number line.
    - pfortuny 5y ago
      It is a specific statement by Liouville: if you can approximate a number "very well" using rational numbers, then it must be transcendental. https://mathworld.wolfram.com/LiouvillesApproximationTheorem.html https://mathworld.wolfram.com/LiouvillesApproximationTheorem... My statement above may be a bit confusing, though.
      - syki 5y ago
        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.
mabbo 5y ago
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 post.
- fbanon 5y ago
  *yawn* https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery https://www.theverge.com/2018/10/24/18019464/4chan-anon-anim...
  - cyberbanjo 5y ago
    > “This proof shows that you don’t need to be a professional mathematician to understand mathematics and advance the frontier of knowledge,” Pantone says. “That’s the beautiful thing about math, is that anyone can understand the questions.” or that prof math post on 4chan?
- probably_wrong 5y ago
  Just wait until you hear about the paper [1] inspired by a Twitter discussion that ended up winning the "Best theme paper" award in the ACL Conference 2020. [1] Climbing towards NLU: On Meaning, Form, and Understanding in the Age of Data: https://aclanthology.org/2020.acl-main.463.pdf https://aclanthology.org/2020.acl-main.463.pdf
- xboxnolifes 5y ago
  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.
- thomasahle 5y ago
  I don't know if Dunning Kruger effects on Facebook posts are anything new/wonderful/strange. This thread reads like somebody who just heard about the Collatz conjecture, and after half an hour are sure they have a solution.
zelphirkalt 5y ago
Why would one try to formulate it as a function of the input length in binary? Does this have a practical relevance? Why not think about it in terms of the numbers given in decimal, their count and their size? And what is the input length in this problem? The numbers encoded in binary? Pretty sure it cannot be computed by just looking at how many numbers are given in each list.
- ufo 5y ago
  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.
  - zelphirkalt 5y ago
    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?
    - Sharlin 5y ago
      Simply the space it would naively take in memory, ie. the sum of the sizes of the elements. Which is the same thing as the length of all the elements concatenated.
    - Tyr42 5y ago
      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.
    - 5y ago
blackbear_ 5y ago
Doesn't this imply that every algorithm that compares real numbers is in PSPACE?
- ogogmad 5y ago
  The predicates < and > are strictly semidecidable, meaning that if two real numbers are equal to each other, then no algorithm is guaranteed to terminate. The complexity is thus RE, which is worse than PSPACE. But the real numbers which show up in the sum-of-square-roots problem are from being as general as possible, so the complexity is PSPACE at worst. The foundations needed to understand general real number computation are listed here: https://news.ycombinator.com/item?id=30057794 https://news.ycombinator.com/item?id=30057794
  - blackbear_ 5y ago
    Super interesting, thanks a lot fot the resources!
- lupire 5y ago
  Real numbers are slippery, because almost no real numbers are computable, even approximately. This conjecture only applies to numbers that have small descriptions but complicated values. If you don't have simple names for your real numbers, then the algorithms are trivial, because all the complexity is in writing the input!
- adgjlsfhk1 5y ago
  No. That said, most are at least that bad.
yalogin 5y ago
What does “ compute this as a function of the length of the input encoded in binary” mean? Can someone explain it with the other sample used in the article? Does it mean the input will be provided in binary form instead of decimal? How does that change things?
- qsort 5y ago
  You're parsing it wrong. "How quickly can we compute this [this = the solution to the problem], as a function of the length of the input encoded in binary?" i.e. it's just wondering what's the computational complexity. The input can be provided in any base, it makes no difference.
- ogogmad 5y ago
  Whether the input is encoded as binary or decimal doesn't change whether the time complexity is in PSPACE, NP or P. You need some finite alphabet, and then encode the input as a string in this alphabet. The time complexity of an algorithm for SSS is measured by how long it takes (in the worst case) as a function of the length of the input string. As long as you use a positional notation like binary or decimal to encode the integers, the big O of the time complexity will remain the same, and so the exact positional notation doesn't actually matter. The size of the alphabet doesn't matter either. If on the other hand you encode the integers using unary notation, then this can land the problem in P.
varelse 5y ago
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 that would be a great sign that such a place probably doesn't ship things very often. I would also bring up that no one can solve the traveling sales problem either but that approximately optimal solutions run the world of logistics on a daily basis. Yet much like you can dedicate an entire supercomputer to calculating the energy of two hydrogen atoms to arbitrary precision, it's a really interesting problem with respect to the pure math. But come on, the guys most likely to bring this question up are relying on 16-bit floating point to train their neural networks. Exponent.Mantissa.Boom. In practice, I know just about no one anymore who can tell me the format of 32-bit or 64-bit floating point because they're so used to abstracting that away.
- deleted 5y ago
  [deleted]
- zodiac 5y ago
  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
  - varelse 5y ago
    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 complicated IMO is if you were dealing with 128-bit or higher integers. Edit: I am learning so much about the mindset here and what triggers acute attacks of the heebie jeebies. This place has really changed in the past decade since I joined and not for the better. Yes good, good, more downvotes. Show your love with downvotes. I'm stuck at 2970 karma, only you can help me on the journey to zero. Can we beat -4? Let's find out.
umvi 5y ago
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.
- ismayilzadan 5y ago
  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".
  - parhamn 5y ago
    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.
- whoomp12342 5y ago
  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.
  - umvi 5y ago
    Yeah, I get that, but I'm just saying if this is a problem needing solved to accomplish some visual effect in game programming (as a contrived example), that practically speaking it's not a hard problem. It's only a hard problem in a theoretical, general sense.
- ravi-delia 5y ago
  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.
openasocket 5y ago
I'm curious if you could get an algorithm using some sort of factoring. (sqrt(a_1) + sqrt(a_2) + ...)*(sqrt(b_1) + sqrt(b_2) + ...) = (sqrt(a_1*b_1) + sqrt(a_1*b_2) + ... + sqrt(a_2*b_1) + sqrt(a_2*b_2) + ...). So you have a convolution operation on lists of integers which satisfies the following: sumOfSqrts(xs) * sumOfSqrts(ys) = sumOfSqrts(convolution(xs, ys)) You could try something where you factor the two lists you are comparing into their "prime lists", remove the duplicates, and then you've reduced it to comparing some countable set of lists, that might have some properties that make them easier to compare? Of course all of that assumes you can uniquely factor lists under this convolution. I don't think you can't if you assume negative numbers can be in the list. But if you restricted your attention to lists with only positive entries, and factored into only lists with all positive entries, it's possible you have a unique factorization method. I don't have the math skills offhand to tell for sure. NB: the article describes PSPACE as being definitely larger than P or NP. But, just like how we don't know (but strongly suspect) NP is bigger than P, we don't know if PSPACE is bigger than P! Complexity theory is hard, so much so that even these relatively simple questions haven't yet been proven.
SilasX 5y ago
Stupid questions: 1) It seems like all the difficulty is from the fact that the representation of the square roots involves a non terminating sequence of digits requiring high precision. So don’t you have this problem with all irrational functions, not just square root? Eg logarithm, sine, exponent from irrational base. (Does it make a difference that sine is bounded?) 2) Do you have the same problem (difficulty being PSPACE) without the square root part at all, as long as you allow the inputs to be arbitrary precision?
- thomasahle 5y ago
  For (1): Comparing sums of logarithms is pretty easy, since you can rewrite it as comparing products of integers. So not all sums of irrationals are hard. For (2): Allowing inputs to arbitrary precision presumably means they are arbitrarily long bit strings? But if you measure complexity in terms of the total number of input bits, summing long bit strings is very easy.
- ted_dunning 5y ago
  1) Not all representations of square roots have non-terminating form. Continued fractions, for instance, reach a repetitive cycle. Other irrational functions have other patterns. 2) No. If you are just doing sums, the cost is O(N) in time and space where N is the total number of bits in the input. If the inputs are large (i.e. N is big) then you have more time to compute the answer.
breezeTrowel 5y ago
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 roots. But the challenge stated in the post can be solved rather easily in a programmatic fashion by simply comparing initial inputs.
- ianthehenry 5y ago
  Consider [25] and [9, 9]. 25 > 18, but 5 < 6.
  - x3n0ph3n3 5y ago
    Thanks! I had the same thought as the OP and this is just the counter-example I needed.
  - deleted 5y ago
    [deleted]
- deleted 5y ago
  [deleted]
- soperj 5y ago
  you're adding the two square roots though. so for example, which is bigger: [2.00000000000000011,2.0000000000000003],[2.0000000000000002,2.00000000000000021]
- umvi 5y ago
  f(x) = sqrt(x) does not increase linearly with x so you can't do that. Compare the plotted graphs of x (input) vs. sqrt(x) (output)
gpsx 5y ago
I must not be understanding the problem here because this seems pretty simple. If someone told me to add two lists of numbers (the square roots) and then take the difference of the two sums and the sums were potentially too big for the computer to handle, I'd start differencing before I finished the sums. (For example find the total of sum1 - sum2. While processing values, if the running sum is positive take a number from list 2. It it is negative take a number from list 1.) That should be linear in the total number of elements in the list.
- brnt 5y ago
  When I was dealing with this the problem was running into machine error: it happens much faster than you think. Especially when you're summing many very small numbers.
  - gpsx 5y ago
    OK I get it, rounding error in calculating the square roots.
- ted_dunning 5y ago
  You understand precisely the first part of the problem ... it looks easy and linear. But, as the article points out, you may need a very large amount of precision to figure out which way the difference goes if it is very close. This isn't about computing a really big sum. This is about computing enough digits of irrational numbers. If you have to compute an exponential number of tinier and tinier digits you still can need exponential time for very small values.
- amirhirsch 5y ago
  The issue is that the precision of the square roots needs to increase in order to guarantee a result. Consider an algorithm to generate the worst case scenario that starts with two lists that have sqrt sums that differ by D. Append to the lists numbers x and y such that |sqrt(x) - sqrt(y)| > D and append them so that the previously lesser list is now greater but also the absolute difference decreases each step.
tzs 5y ago
I 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 + 530967788407084153582901906991810 √10 + 366402251460399628674629181584238 √21 + 259085516641872377051783075481000 √42 + 163913368573924563188162165414670 √105 + 115904254449237925942667189567670 √210 and so on. For any given finite sequence of positive integers there is a finite set of square roots of positive integers such that all positive integer powers of the sum of the square roots of the sequence members can be expressed as a linear combination of that finite square root set with non-negative integer coefficients. With s^n if we approximate each of the square roots by first the nearest integer not larger than the square root, and second by the nearest integer not smaller than the square root, we get a lower bound and upper bound for s^n. Suppose we do that for the sums of the square roots of the two sequences we want to compare. For each power n, that gives us two integer ranges we can compare. If they do not overlap, we can tell which square root sum is lower. If they do overlap, we can try a higher power n, so we can try a better square root approximation than nearest integer to get narrow ranges for the n'th powers. What I'm hoping for is that by going to higher powers we can avoid having to do high precision square root calculations, so it can be done with just large integer arithmetic and regular floating point.
- cperciva 5y ago
  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.
  - chrisshroba 5y ago
    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/8f12757ecbcdd394ceccb3e9577f7c0d https://gist.github.com/chrisshroba/8f12757ecbcdd394ceccb3e9...
deleted 5y ago
[deleted]
munificent 5y ago
> I’m going to update towards thinking that integers and square roots are much scarier, richer objects than I’d thought. I’ve updated to being more scared of real numbers than I used to be—they have all these sketchy properties like “almost none of them have finite descriptions”. Real numbers, and sets, and logical statements, have all started feeling to me like Cthuluesque monstrosities whose appearances are only tolerable because we only look at the pretty parts of them and don’t let ourselves look at the horrors that lurk below. I don't know much number theory but whenever I poke around at stuff like the Collatz conjecture, it seems like there is something profoundly weird about the interaction of addition/subtraction and multiplication/division. Like each of those pairs defines a totally separate universe and moving between them is irreducibly hard even though the members of both are "just" numbers. By that I mean you can have a number that you understand perfectly well one side (for example, as a set of factors in the world of multiplication). You move it to the other side and perform a trivial operation (say add one). And now you know nothing about it on the other side any more. Maybe this is just me knowing very little about the field.
- kadoban 5y ago
  > Maybe this is just me knowing very little about the field. Can't tell if pun. Either way, it's pretty good. https://en.wikipedia.org/wiki/Field_(mathematics) https://en.wikipedia.org/wiki/Field_(mathematics)
- ogogmad 5y ago
  Looks like Presburger Arithmetic [1] versus Peano Arithmetic [2]. [1] - https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic [2] - https://en.wikipedia.org/wiki/Peano_axioms https://en.wikipedia.org/wiki/Peano_axioms
- gfody 5y ago
  > there is something profoundly weird about [numbers] you should hear John Conway (RIP) talk about numbers - https://www.youtube.com/watch?v=1eAmxgINXrE https://www.youtube.com/watch?v=1eAmxgINXrE
  - 5y ago
ddtaylor 5y ago
Would the naive approach "just work" (although slowly) in Python since it has arbitrary precision?
- Diggsey 5y ago
  Python doesn't use arbitrary precision for floating point values, it just has arbitrarily long integers.
  - ddtaylor 5y ago
    Oh, derp, you're right.
- dooglius 5y ago
  Python does not have arbitrary precision for floating point
- EvgeniyZh 5y ago
  Python has arbitrary integer precision, that won't help
bjornsing 5y ago
So 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/S0020019006001396?via%3Dihub https://www.sciencedirect.com/science/article/abs/pii/S00200... show that this algorithm is in fact polynomial?
- yorwba 5y ago
  > EDIT: Doesn’t https://www.sciencedirect.com/science/article/abs/pii/S0020019006001396 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.
jandrese 5y ago
I'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?
tgflynn 5y ago
It seems like this should just reduce to the question: given two natural numbers x and y represented by n bits how many bits are needed to represent the difference sqrt(y) - sqrt(x) so that it is non-zero when x != y. To see this suppose you compute each sqrt in both lists to k bits then group together the closest matching pairs from the two lists. Some of these pairs may have a difference of zero. Now increase k until all of the pairs are distinguished (have non-zero differences). At that point you know the answer, you just have to add up the differences. As for the first question it should take no more than n bits because sqrt(x) is a contraction at least for x >= 1 as is obvious from its graph compared to that of f(x) = x.
- klyrs 5y ago
  > At that point you know the answer, you just have to add up the differences. What if your sum in this step is zero?
  - tgflynn 5y ago
    There's a known upper bound for the error on each pair delta caused by the finite number of bits. So that gives upper and lower bounds for the error on the sum of the deltas. Add enough bits to your representation to account for that error. I think that's an additional log N + 1 bits where N is the sequence length. Then if the sum comes out to zero that must be the correct answer (probably impossible unless the two sequences contain the same values).
    - klyrs 5y ago
      > Add enough bits to your representation to account for that error. I've reviewed a few papers where authors respond with this sort of argument. It never ends in a publication. But, I really should have picked on the preceding sentence: > Now increase k until all of the pairs are distinguished (have non-zero differences). Do you have an estimate on the bounds, time or space, required for that? Because establishing those bounds is the "hard problem" here. Also, what do you do about questions like sqrt(2)+sqrt(50) =? sqrt(72) where the sums have differing numbers of terms? And, it might be worthwhile to play with an example: (55, 77, 83) and (64, 68, 82) -- depending on where you decide to truncate, the difference wobbles above, below and equal to zero, well past the point you've described where the pairwise differences are nonzero (4 bits and the sums appear to be equal). It finally stabilizes after 25 bits -- much greater than log N + 1.
amelius 5y ago
> comparing sums of square roots is actually kind of a common subtask in eg computational geometry, so a bunch of their problems (including “shortest path through a graph in Euclidean space”!) are as-far-as-we-know extremely hard. But the question then arises: do we always need to solve these problems to their fullest precision? Can we perhaps leave some ambiguity, and let the system gracefully deal with it? E.g. I don't care if my CAD model has a tiny chip of 1e-12 mm missing, as long as my CAD software doesn't crash on the resulting internal inconsistencies. See also, e.g.: https://www.cs.purdue.edu/homes/cmh/distribution/papers/Robustness/robust4.pdf https://www.cs.purdue.edu/homes/cmh/distribution/papers/Robu...
- bshlgrs 5y ago
  Yeah, afaik this problem is totally unimportant in practice.
  - saagarjha 5y ago
    Wait until it ends up being used in some other important field of math.
cevi 5y ago
An example of a tricky case: which is bigger, sqrt(1000000) + sqrt(1000018) + sqrt(1000036) + sqrt(1000059) + sqrt(1000083), or sqrt(1000003) + sqrt(1000011) + sqrt(1000048) + sqrt(1000050) + sqrt(1000084)? (They agree to more than 20 decimal digits of precision!)
- kccqzy 5y ago
  The second is bigger, but only by ~2.3 * 10^(-13). Very good illustration indeed.
- chii 5y ago
  i wonder if you can use logs to do this faster: 1. simplify the sqrt by log of each number, i.e. log(sqrt(x)) = 1/2 * log(x) 2. since sum of logs is the log of the products, i.e., log(a) + log(b) = log(ab) you can simplify the whole expression by multiplying all the numbers, taking the log of the product once (which i presume is much faster), then multiplying by 1/2 since logs are strictly increasing, the resulting number is still going to be bigger if it originally was going to be bigger, and now you don't need to have performed all those sqrts. Now you've reduced the problem to computing 1 log to an arbitrary precision...not sure how one does that actually...
  - bmm6o 5y ago
    I think the + and × are backwards from the way that would be helpful. But if you think it would work, try writing it out in detail.
    - chii 5y ago
      let met try, for [a, b, c], and [d, e, f] 1. Take the log of all terms (allowed, because log keeps the sum monotonic): log(sqrt(a)) + log(sqrt(b)) + log(sqrt(c)) 2. pull out the sqrt from the log: 1/2 * log(a) + 1/2 * log(b) +1/2 * log(c) 3. factor out the 1/2: 1/2 * (log(a) + log(b) + log(c)) 4. sum of logs can be rewritten as a log of product: 1/2 * log (a * b * c) 5. compute log of (a * b * c), and halve it. Ditto with log of (d * e * f). This should give a number which is proportional to the original sum of sqrt.
pkrumins 5y ago
I don't get it - how is this problem any different than simply comparing two very long integers. Given integers "a" and "b" - determine which one is bigger. You don't know as "a" could be seventy six billion trillion quadrillion digits long and "b" could be even more digits and you never stop comparing them as there are more and more digits. No need for square roots or sums.
- bshlgrs 5y ago
  Good question :) The difference is that in that case, the problem might take a long time because the input is very long, but in this case, the problem might take a long time even if the input itself is fairly short.
IvanK_net 5y ago
I think the formulation "this algorithm is in PSPACE" is very inappropriate in this case. Every "sane" algorithm is in PSPACE, e.g. adding two numbers. Either prove, that the problem is PSPACE-complete (any PSPACE problem can be converted into it), or just say that your algorithm takes exponential time in polynomial space.
hiopilot 5y ago
This is not a computer science question. It's a math challenge. We simply rely on computers to do the math faster. I challenge any math person to solve this problem and/or provide a proof. Given that their equations will ultimately be so complex they will fail. For example, just say 1/3. Easy right? 0.333333334 Wrong. It's impossible for a human or a computer to say the answer. NOT a CS issue. We can't combine random and ultimately repeating numbers. Each time you reduce a number via square root you will eventually reach an infinite response and thus it's impossible to solve, let alone with a binary computer system. I would love the very first quantum computer to do 1/3. Just use up all the CPU and energy it has in a problem it can't solve. Forever in time. Look not at the computer as the failure scenario but math in general. At some point you stop and round. When that happens, an error is introduced when you extend the answer beyond the rounding point. At some point you will fine an infinite answer and/or answers. I can write you a computer program to write a single infinite answer. Combining two of them produces the same infinite process. Here is a better answer. Can we shift the base in a way that allows us to answer random questions like these?
- nestorD 5y ago
  Computing the value would be a problem but determining which is bigger is purely a CS question (just one that cannot be solved directly with our usual floating point tool: IEEE 754 arithmetic).
- monktastic1 5y ago
  You may have missed the point. Although fractions may have infinite representations, the question of which sum of fractions is larger is a much easier problem to solve: "On the other hand, comparing the sums of fractions is pretty easy, because division is nice and well behaved. So the question is how complicated square roots are."
- ChrisLomont 5y ago
  >Each time you reduce a number via square root you will eventually reach an infinite response and thus it's impossible to solve, let alone with a binary computer system. This is incorrect. All the symbolic math programs in the world provide counterexamples. There is no need to deal with infinite length decimal numbers to do a lot of proving of things in mathematics, in the same manner when I prove things by hand I do not need to write out infinite length numbers. Your mistake is assuming the only way to analyze a sqrt of a number is to write it out in infinite precision. That is not needed. For example, you can prove on a computer that sqrt(19) > sqrt(17) without having to evaluate either side as a decimal number. For example, Mathematica (or any symbolic program), entering Sqrt[19]>Sqrt[17] returns True.
credulousperson 5y ago
A small note: If you allow randomized algorithms, this problem is actually known to be in P^PP^PP^PP which is well within PSPACE in some sense, but still a ridiculously bad bound. See https://cstheory.stackexchange.com/a/4056 https://cstheory.stackexchange.com/a/4056.
zoomablemind 5y ago
I thought that any algorithms relating with real numbers (and floating point) require use of some epsilon as a measure of closeness. In such approach some different numbers will be treated as equals, but qualified with the epsilon. Thus it could be made practical, as long as epsilon is chosen appropriately to the application domain.
samyrasmy 5y ago
Here is my attempt at proving that this can be done in P-time. I am using the fact that square roots can be expressed as periodic continued fractions, and that there is an upper bound on the period of these fractions which must thus be unique. Please tell me if there are any issues! I hope this holds :) The period of the square root of n is less than k1 * (sqrt(n) log (log (log (n))) ) = Lm(n) We can find this period in polynomial time (n^3) each term is smaller than 2*sqrt(n) Therefore, all square roots up to n are uniquely represented as part of a continued fraction expansion as a0 + 1/(a1 + 1/ (a2 + ...)) ... up to a[Lm(n)]. If we transform this nested fraction into a decimal number, any modification of this fraction will necessarily lead to a delta in the number by at least (a[Lm(n))]^-(Lm(n)), which is at most 2sqrt(n)^-(sqrt(n) Therefore, accurately computing the square root up to the most significant digit of 2sqrt(n)^-(2sqrt(n)) will yield a result distinct from any square root up to n. In the case of a sum of square roots, assuming that n is the largest root, accurately computing the sum up past the most significant digit of 2sqrt(n)^-Lm(n) will be sufficient to decide if a sum of square roots is larger than or smaller than another. 2sqrt(n)^-Lm(n) is reciprocally subexponential, thus the number of digits needing to be computed will grow sub-linearly with n Therefore, the problem can be solved in polynomial time.
- eurasiantiger 5y ago
  Can we get a validity test and benchmark comparing this solution to the generally accepted one?

297 points by EvgeniyZh 5y ago

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 efficient algorithm here.

lupire 5y ago
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.
- Sharlin 5y ago
  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.
  - vessenes 5y ago
    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.
    - ChrisLomont 5y ago
      This isn't true, which is why the problem lies in the complexity class listed in the article. Arbitrarily bad pathologies exist even for simple inputs.

deleted 5y ago

[deleted]

ogogmad 5y ago

Relevant material on exact real computation: Wikipedia article: https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis Book: https://link.springer.com/book/10.1007/978-3-642-56999-9 https://link.springer.com/book/10.1007/978-3-642-56999-9

misja111 5y ago

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-square-roots.html http://benpaulthurstonblog.blogspot.com/2012/05/estimating-s... [2] https://www.jstor.org/stable/1969389 https://www.jstor.org/stable/1969389

mihaic 5y ago
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.
ogogmad 5y ago
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.
contravariant 5y ago
You're assuming that the period will remain of manageable size. I see no reason why this should be the case. Edit: Also found a more accessible website describing how to do arithmetic with continued fractions: https://perl.plover.com/yak/cftalk/ https://perl.plover.com/yak/cftalk/. In case anyone wants to try it out.
lupire 5y ago
Continued fraction approxmations are not a separable monotonically increasing sequence like decimal approximations are (the approximation goes up and down and the error range overlaps other nearby fractions of the same size), so you have no idea when you can terminate a partial computation.

deleted 5y ago

[deleted]

athrowaway3z 5y ago

This 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.

qsort 5y ago
Why would it be too imprecise? I agree there are some (many?) problems with some definitions used in complexity theory, but "size of input" is certainly not part of the problem. It can be defined very precisely. I don't see the slightest problem with how it's framed.
- dooglius 5y ago
  So what is N here? The sequence length, number of digits across all sequence elements, sum of all elements?
  - deleted 5y ago
    [deleted]
  - qsort 5y ago
    N is the sum of the lengths of the elements of all lists, when all elements are written in binary (or any other base, which is the same up to a constant).
Khoth 5y ago
Irrational numbers are involved in the problem, but not in the the size of the input, which is a list of natural numbers. There are a number of reasonable ways to encode such a list but they'll all scale in more or less the same way and be equivalent when looking at big O notation.
deleted 5y ago
[deleted]
Frost1x 5y ago
If you assume that mathematical notation (language) doesn't abstract complexity in a uniform fashion (something you can write and capture meaning with a few symbols isn't inherently more or less complex than something you can write with a lot of symbols), it becomes pretty obvious that something isn't necessarily as simple as it may look at the surface. Having worked in computing for long enough, I'm well aware of this fact in the world of estimating time (which to some degree is estimating complexity) to address a given problem request. I can very easily write down in English a pretty generalized description that you need to: cure any and all forms of cancer. That's a fairly concise request, I can write it in one line, but it hides a mountain of complexity needed to accomplish that. It also doesn't describe what we consider as "cure" or "cancer" which can be ambiguous in some cases. Much of the same is true with seemingly cute conjectures that seem to capture a behavior that may be incredibly complex to prove (if not impossible, e.g. Godel). The Collatz conjecture comes to mind where Paul Erdos famously said something to the effect of "Mathematics may not be ready for such problems."

PaulHoule 5y ago

It reminds me of this problem. When you plot the motion of conservative dynamical systems, say this one https://en.wikipedia.org/wiki/Standard_map 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.

ted_dunning 5y ago
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 right)
- PaulHoule 5y ago
  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.
  - 5y ago

edflsafoiewq 5y ago

> There’s a known, reasonably fast algorithm (in BPP) for checking equality of sums of square roots What is it?

dooglius 5y ago
You just have to take out square factors from each, and combine terms with matching sqrt(n), and that will be unique
- edflsafoiewq 5y ago
  How do you know its unique?
  - aliceryhl 5y ago
    I don't think there's an elementary proof, but you will see a proof if you study algebraic number theory.
  - deleted 5y ago
    [deleted]
- jepler 5y ago
  That is to say, rewrite each sqrt(N_i) as P_i * sqrt(Q_i) where P and Q are integers and Q contains no squares. So 2 becomes 1 * sqrt(2), 4 becomes 2 * sqrt(1) and 8 becomes 2 * sqrt(2). Now, you can subtract equal terms from each side of the equation and if you can reach 0=0 then the numbers are equal. If you're left with something like sqrt(3) = 5 * sqrt(2) the the numbers are unequal. This stems from the fact, that I give without proof, that for integers X, Y and Z that contain no squares that sqrt(x) + sqrt(y) is never equal to sqrt(z). So there's no way to (say) add a bunch of square roots of 2 and have it become equal to a square root of 3 or 5. A number contains no squares if its prime factorization contains no repeated factors. Since this seems to involve factorization, plus a step of matching up numbers from both sides, the computational complexity would seem to be at least the complexity of factorization. The term-matching step is presumablty the easier step of the two.

erwincoumans 5y ago

>> 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)?

dmurray 5y ago
I expect not very important in practice, because 1. We've settled on using IEEE 754 floating point numbers, and all their tolerance quirks, in practice, and still the bridges don't fall down 2. The author describes it as a little-studied field where "most of the people who would be good at working on this are doing something more useful instead" But still, useless pure-maths distractions have a way of yielding results in unexpected fields. Maybe, as the author hints, a solution to this problem would bring us some information-theory insights and some new methods for cryptography or compression or whatever else.
Someone 5y ago
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?

fdej 5y ago

> 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 can write down a completely explicit bound here using the Mahler-Mignotte root separation bound. More generally, for any algebraic expression involving algebraic numbers, you can bound a priori the number of digits you need to check to determine its sign. When you involve transcendental numbers, things do get much harder though.

pfortuny 5y ago
Exactly: algebraic numbers, despite not being periodic, are in general "reasonably far from each other", and especially from rationals. I guess the problem can be solved using what you say, certainly. It is only transcendentals that can be "too near" each other, and near rationals (this is Liouville's result, which was improved later on, in a specific case the one you say).
- syki 5y ago
  Rational numbers are algebraic so how are algebraic numbers reasonably far from each other? Algebraic numbers are dense in the real number line.
  - pfortuny 5y ago
    It is a specific statement by Liouville: if you can approximate a number "very well" using rational numbers, then it must be transcendental. https://mathworld.wolfram.com/LiouvillesApproximationTheorem.html https://mathworld.wolfram.com/LiouvillesApproximationTheorem... My statement above may be a bit confusing, though.
    - syki 5y ago
      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.

mabbo 5y ago

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 post.

fbanon 5y ago
*yawn* https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery https://www.theverge.com/2018/10/24/18019464/4chan-anon-anim...
- cyberbanjo 5y ago
  > “This proof shows that you don’t need to be a professional mathematician to understand mathematics and advance the frontier of knowledge,” Pantone says. “That’s the beautiful thing about math, is that anyone can understand the questions.” or that prof math post on 4chan?
probably_wrong 5y ago
Just wait until you hear about the paper [1] inspired by a Twitter discussion that ended up winning the "Best theme paper" award in the ACL Conference 2020. [1] Climbing towards NLU: On Meaning, Form, and Understanding in the Age of Data: https://aclanthology.org/2020.acl-main.463.pdf https://aclanthology.org/2020.acl-main.463.pdf
xboxnolifes 5y ago
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.
thomasahle 5y ago
I don't know if Dunning Kruger effects on Facebook posts are anything new/wonderful/strange. This thread reads like somebody who just heard about the Collatz conjecture, and after half an hour are sure they have a solution.

zelphirkalt 5y ago

Why would one try to formulate it as a function of the input length in binary? Does this have a practical relevance? Why not think about it in terms of the numbers given in decimal, their count and their size? And what is the input length in this problem? The numbers encoded in binary? Pretty sure it cannot be computed by just looking at how many numbers are given in each list.

ufo 5y ago
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.
- zelphirkalt 5y ago
  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?
  - Sharlin 5y ago
    Simply the space it would naively take in memory, ie. the sum of the sizes of the elements. Which is the same thing as the length of all the elements concatenated.
  - Tyr42 5y ago
    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.
  - 5y ago

blackbear_ 5y ago

Doesn't this imply that every algorithm that compares real numbers is in PSPACE?

ogogmad 5y ago
The predicates < and > are strictly semidecidable, meaning that if two real numbers are equal to each other, then no algorithm is guaranteed to terminate. The complexity is thus RE, which is worse than PSPACE. But the real numbers which show up in the sum-of-square-roots problem are from being as general as possible, so the complexity is PSPACE at worst. The foundations needed to understand general real number computation are listed here: https://news.ycombinator.com/item?id=30057794 https://news.ycombinator.com/item?id=30057794
- blackbear_ 5y ago
  Super interesting, thanks a lot fot the resources!
lupire 5y ago
Real numbers are slippery, because almost no real numbers are computable, even approximately. This conjecture only applies to numbers that have small descriptions but complicated values. If you don't have simple names for your real numbers, then the algorithms are trivial, because all the complexity is in writing the input!
adgjlsfhk1 5y ago
No. That said, most are at least that bad.

yalogin 5y ago

What does “ compute this as a function of the length of the input encoded in binary” mean? Can someone explain it with the other sample used in the article? Does it mean the input will be provided in binary form instead of decimal? How does that change things?

qsort 5y ago
You're parsing it wrong. "How quickly can we compute this [this = the solution to the problem], as a function of the length of the input encoded in binary?" i.e. it's just wondering what's the computational complexity. The input can be provided in any base, it makes no difference.
ogogmad 5y ago
Whether the input is encoded as binary or decimal doesn't change whether the time complexity is in PSPACE, NP or P. You need some finite alphabet, and then encode the input as a string in this alphabet. The time complexity of an algorithm for SSS is measured by how long it takes (in the worst case) as a function of the length of the input string. As long as you use a positional notation like binary or decimal to encode the integers, the big O of the time complexity will remain the same, and so the exact positional notation doesn't actually matter. The size of the alphabet doesn't matter either. If on the other hand you encode the integers using unary notation, then this can land the problem in P.

varelse 5y ago

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 that would be a great sign that such a place probably doesn't ship things very often. I would also bring up that no one can solve the traveling sales problem either but that approximately optimal solutions run the world of logistics on a daily basis. Yet much like you can dedicate an entire supercomputer to calculating the energy of two hydrogen atoms to arbitrary precision, it's a really interesting problem with respect to the pure math. But come on, the guys most likely to bring this question up are relying on 16-bit floating point to train their neural networks. Exponent.Mantissa.Boom. In practice, I know just about no one anymore who can tell me the format of 32-bit or 64-bit floating point because they're so used to abstracting that away.

deleted 5y ago
[deleted]
zodiac 5y ago
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
- varelse 5y ago
  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 complicated IMO is if you were dealing with 128-bit or higher integers. Edit: I am learning so much about the mindset here and what triggers acute attacks of the heebie jeebies. This place has really changed in the past decade since I joined and not for the better. Yes good, good, more downvotes. Show your love with downvotes. I'm stuck at 2970 karma, only you can help me on the journey to zero. Can we beat -4? Let's find out.

umvi 5y ago

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.

ismayilzadan 5y ago
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".
- parhamn 5y ago
  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.
whoomp12342 5y ago
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.
- umvi 5y ago
  Yeah, I get that, but I'm just saying if this is a problem needing solved to accomplish some visual effect in game programming (as a contrived example), that practically speaking it's not a hard problem. It's only a hard problem in a theoretical, general sense.
ravi-delia 5y ago
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.

openasocket 5y ago

I'm curious if you could get an algorithm using some sort of factoring. (sqrt(a_1) + sqrt(a_2) + ...)*(sqrt(b_1) + sqrt(b_2) + ...) = (sqrt(a_1*b_1) + sqrt(a_1*b_2) + ... + sqrt(a_2*b_1) + sqrt(a_2*b_2) + ...). So you have a convolution operation on lists of integers which satisfies the following: sumOfSqrts(xs) * sumOfSqrts(ys) = sumOfSqrts(convolution(xs, ys)) You could try something where you factor the two lists you are comparing into their "prime lists", remove the duplicates, and then you've reduced it to comparing some countable set of lists, that might have some properties that make them easier to compare? Of course all of that assumes you can uniquely factor lists under this convolution. I don't think you can't if you assume negative numbers can be in the list. But if you restricted your attention to lists with only positive entries, and factored into only lists with all positive entries, it's possible you have a unique factorization method. I don't have the math skills offhand to tell for sure. NB: the article describes PSPACE as being definitely larger than P or NP. But, just like how we don't know (but strongly suspect) NP is bigger than P, we don't know if PSPACE is bigger than P! Complexity theory is hard, so much so that even these relatively simple questions haven't yet been proven.

SilasX 5y ago

Stupid questions: 1) It seems like all the difficulty is from the fact that the representation of the square roots involves a non terminating sequence of digits requiring high precision. So don’t you have this problem with all irrational functions, not just square root? Eg logarithm, sine, exponent from irrational base. (Does it make a difference that sine is bounded?) 2) Do you have the same problem (difficulty being PSPACE) without the square root part at all, as long as you allow the inputs to be arbitrary precision?

thomasahle 5y ago
For (1): Comparing sums of logarithms is pretty easy, since you can rewrite it as comparing products of integers. So not all sums of irrationals are hard. For (2): Allowing inputs to arbitrary precision presumably means they are arbitrarily long bit strings? But if you measure complexity in terms of the total number of input bits, summing long bit strings is very easy.
ted_dunning 5y ago
1) Not all representations of square roots have non-terminating form. Continued fractions, for instance, reach a repetitive cycle. Other irrational functions have other patterns. 2) No. If you are just doing sums, the cost is O(N) in time and space where N is the total number of bits in the input. If the inputs are large (i.e. N is big) then you have more time to compute the answer.

breezeTrowel 5y ago

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 roots. But the challenge stated in the post can be solved rather easily in a programmatic fashion by simply comparing initial inputs.

ianthehenry 5y ago
Consider [25] and [9, 9]. 25 > 18, but 5 < 6.
- x3n0ph3n3 5y ago
  Thanks! I had the same thought as the OP and this is just the counter-example I needed.
- deleted 5y ago
  [deleted]
deleted 5y ago
[deleted]
soperj 5y ago
you're adding the two square roots though. so for example, which is bigger: [2.00000000000000011,2.0000000000000003],[2.0000000000000002,2.00000000000000021]
umvi 5y ago
f(x) = sqrt(x) does not increase linearly with x so you can't do that. Compare the plotted graphs of x (input) vs. sqrt(x) (output)

gpsx 5y ago

I must not be understanding the problem here because this seems pretty simple. If someone told me to add two lists of numbers (the square roots) and then take the difference of the two sums and the sums were potentially too big for the computer to handle, I'd start differencing before I finished the sums. (For example find the total of sum1 - sum2. While processing values, if the running sum is positive take a number from list 2. It it is negative take a number from list 1.) That should be linear in the total number of elements in the list.

brnt 5y ago
When I was dealing with this the problem was running into machine error: it happens much faster than you think. Especially when you're summing many very small numbers.
- gpsx 5y ago
  OK I get it, rounding error in calculating the square roots.
ted_dunning 5y ago
You understand precisely the first part of the problem ... it looks easy and linear. But, as the article points out, you may need a very large amount of precision to figure out which way the difference goes if it is very close. This isn't about computing a really big sum. This is about computing enough digits of irrational numbers. If you have to compute an exponential number of tinier and tinier digits you still can need exponential time for very small values.
amirhirsch 5y ago
The issue is that the precision of the square roots needs to increase in order to guarantee a result. Consider an algorithm to generate the worst case scenario that starts with two lists that have sqrt sums that differ by D. Append to the lists numbers x and y such that |sqrt(x) - sqrt(y)| > D and append them so that the previously lesser list is now greater but also the absolute difference decreases each step.

tzs 5y ago

I 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 + 530967788407084153582901906991810 √10 + 366402251460399628674629181584238 √21 + 259085516641872377051783075481000 √42 + 163913368573924563188162165414670 √105 + 115904254449237925942667189567670 √210 and so on. For any given finite sequence of positive integers there is a finite set of square roots of positive integers such that all positive integer powers of the sum of the square roots of the sequence members can be expressed as a linear combination of that finite square root set with non-negative integer coefficients. With s^n if we approximate each of the square roots by first the nearest integer not larger than the square root, and second by the nearest integer not smaller than the square root, we get a lower bound and upper bound for s^n. Suppose we do that for the sums of the square roots of the two sequences we want to compare. For each power n, that gives us two integer ranges we can compare. If they do not overlap, we can tell which square root sum is lower. If they do overlap, we can try a higher power n, so we can try a better square root approximation than nearest integer to get narrow ranges for the n'th powers. What I'm hoping for is that by going to higher powers we can avoid having to do high precision square root calculations, so it can be done with just large integer arithmetic and regular floating point.

cperciva 5y ago
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.
- chrisshroba 5y ago
  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/8f12757ecbcdd394ceccb3e9577f7c0d https://gist.github.com/chrisshroba/8f12757ecbcdd394ceccb3e9...

deleted 5y ago

[deleted]

munificent 5y ago

> I’m going to update towards thinking that integers and square roots are much scarier, richer objects than I’d thought. I’ve updated to being more scared of real numbers than I used to be—they have all these sketchy properties like “almost none of them have finite descriptions”. Real numbers, and sets, and logical statements, have all started feeling to me like Cthuluesque monstrosities whose appearances are only tolerable because we only look at the pretty parts of them and don’t let ourselves look at the horrors that lurk below. I don't know much number theory but whenever I poke around at stuff like the Collatz conjecture, it seems like there is something profoundly weird about the interaction of addition/subtraction and multiplication/division. Like each of those pairs defines a totally separate universe and moving between them is irreducibly hard even though the members of both are "just" numbers. By that I mean you can have a number that you understand perfectly well one side (for example, as a set of factors in the world of multiplication). You move it to the other side and perform a trivial operation (say add one). And now you know nothing about it on the other side any more. Maybe this is just me knowing very little about the field.

kadoban 5y ago
> Maybe this is just me knowing very little about the field. Can't tell if pun. Either way, it's pretty good. https://en.wikipedia.org/wiki/Field_(mathematics) https://en.wikipedia.org/wiki/Field_(mathematics)
ogogmad 5y ago
Looks like Presburger Arithmetic [1] versus Peano Arithmetic [2]. [1] - https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic [2] - https://en.wikipedia.org/wiki/Peano_axioms https://en.wikipedia.org/wiki/Peano_axioms
gfody 5y ago
> there is something profoundly weird about [numbers] you should hear John Conway (RIP) talk about numbers - https://www.youtube.com/watch?v=1eAmxgINXrE https://www.youtube.com/watch?v=1eAmxgINXrE
- 5y ago

ddtaylor 5y ago

Would the naive approach "just work" (although slowly) in Python since it has arbitrary precision?

Diggsey 5y ago
Python doesn't use arbitrary precision for floating point values, it just has arbitrarily long integers.
- ddtaylor 5y ago
  Oh, derp, you're right.
dooglius 5y ago
Python does not have arbitrary precision for floating point
EvgeniyZh 5y ago
Python has arbitrary integer precision, that won't help

bjornsing 5y ago

So 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/S0020019006001396?via%3Dihub https://www.sciencedirect.com/science/article/abs/pii/S00200... show that this algorithm is in fact polynomial?

yorwba 5y ago
> EDIT: Doesn’t https://www.sciencedirect.com/science/article/abs/pii/S0020019006001396 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.

jandrese 5y ago

I'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?

tgflynn 5y ago

It seems like this should just reduce to the question: given two natural numbers x and y represented by n bits how many bits are needed to represent the difference sqrt(y) - sqrt(x) so that it is non-zero when x != y. To see this suppose you compute each sqrt in both lists to k bits then group together the closest matching pairs from the two lists. Some of these pairs may have a difference of zero. Now increase k until all of the pairs are distinguished (have non-zero differences). At that point you know the answer, you just have to add up the differences. As for the first question it should take no more than n bits because sqrt(x) is a contraction at least for x >= 1 as is obvious from its graph compared to that of f(x) = x.

klyrs 5y ago
> At that point you know the answer, you just have to add up the differences. What if your sum in this step is zero?
- tgflynn 5y ago
  There's a known upper bound for the error on each pair delta caused by the finite number of bits. So that gives upper and lower bounds for the error on the sum of the deltas. Add enough bits to your representation to account for that error. I think that's an additional log N + 1 bits where N is the sequence length. Then if the sum comes out to zero that must be the correct answer (probably impossible unless the two sequences contain the same values).
  - klyrs 5y ago
    > Add enough bits to your representation to account for that error. I've reviewed a few papers where authors respond with this sort of argument. It never ends in a publication. But, I really should have picked on the preceding sentence: > Now increase k until all of the pairs are distinguished (have non-zero differences). Do you have an estimate on the bounds, time or space, required for that? Because establishing those bounds is the "hard problem" here. Also, what do you do about questions like sqrt(2)+sqrt(50) =? sqrt(72) where the sums have differing numbers of terms? And, it might be worthwhile to play with an example: (55, 77, 83) and (64, 68, 82) -- depending on where you decide to truncate, the difference wobbles above, below and equal to zero, well past the point you've described where the pairwise differences are nonzero (4 bits and the sums appear to be equal). It finally stabilizes after 25 bits -- much greater than log N + 1.

amelius 5y ago

> comparing sums of square roots is actually kind of a common subtask in eg computational geometry, so a bunch of their problems (including “shortest path through a graph in Euclidean space”!) are as-far-as-we-know extremely hard. But the question then arises: do we always need to solve these problems to their fullest precision? Can we perhaps leave some ambiguity, and let the system gracefully deal with it? E.g. I don't care if my CAD model has a tiny chip of 1e-12 mm missing, as long as my CAD software doesn't crash on the resulting internal inconsistencies. See also, e.g.: https://www.cs.purdue.edu/homes/cmh/distribution/papers/Robustness/robust4.pdf https://www.cs.purdue.edu/homes/cmh/distribution/papers/Robu...

bshlgrs 5y ago
Yeah, afaik this problem is totally unimportant in practice.
- saagarjha 5y ago
  Wait until it ends up being used in some other important field of math.

cevi 5y ago

An example of a tricky case: which is bigger, sqrt(1000000) + sqrt(1000018) + sqrt(1000036) + sqrt(1000059) + sqrt(1000083), or sqrt(1000003) + sqrt(1000011) + sqrt(1000048) + sqrt(1000050) + sqrt(1000084)? (They agree to more than 20 decimal digits of precision!)

kccqzy 5y ago
The second is bigger, but only by ~2.3 * 10^(-13). Very good illustration indeed.
chii 5y ago
i wonder if you can use logs to do this faster: 1. simplify the sqrt by log of each number, i.e. log(sqrt(x)) = 1/2 * log(x) 2. since sum of logs is the log of the products, i.e., log(a) + log(b) = log(ab) you can simplify the whole expression by multiplying all the numbers, taking the log of the product once (which i presume is much faster), then multiplying by 1/2 since logs are strictly increasing, the resulting number is still going to be bigger if it originally was going to be bigger, and now you don't need to have performed all those sqrts. Now you've reduced the problem to computing 1 log to an arbitrary precision...not sure how one does that actually...
- bmm6o 5y ago
  I think the + and × are backwards from the way that would be helpful. But if you think it would work, try writing it out in detail.
  - chii 5y ago
    let met try, for [a, b, c], and [d, e, f] 1. Take the log of all terms (allowed, because log keeps the sum monotonic): log(sqrt(a)) + log(sqrt(b)) + log(sqrt(c)) 2. pull out the sqrt from the log: 1/2 * log(a) + 1/2 * log(b) +1/2 * log(c) 3. factor out the 1/2: 1/2 * (log(a) + log(b) + log(c)) 4. sum of logs can be rewritten as a log of product: 1/2 * log (a * b * c) 5. compute log of (a * b * c), and halve it. Ditto with log of (d * e * f). This should give a number which is proportional to the original sum of sqrt.

pkrumins 5y ago

I don't get it - how is this problem any different than simply comparing two very long integers. Given integers "a" and "b" - determine which one is bigger. You don't know as "a" could be seventy six billion trillion quadrillion digits long and "b" could be even more digits and you never stop comparing them as there are more and more digits. No need for square roots or sums.

bshlgrs 5y ago
Good question :) The difference is that in that case, the problem might take a long time because the input is very long, but in this case, the problem might take a long time even if the input itself is fairly short.

IvanK_net 5y ago

I think the formulation "this algorithm is in PSPACE" is very inappropriate in this case. Every "sane" algorithm is in PSPACE, e.g. adding two numbers. Either prove, that the problem is PSPACE-complete (any PSPACE problem can be converted into it), or just say that your algorithm takes exponential time in polynomial space.

hiopilot 5y ago

This is not a computer science question. It's a math challenge. We simply rely on computers to do the math faster. I challenge any math person to solve this problem and/or provide a proof. Given that their equations will ultimately be so complex they will fail. For example, just say 1/3. Easy right? 0.333333334 Wrong. It's impossible for a human or a computer to say the answer. NOT a CS issue. We can't combine random and ultimately repeating numbers. Each time you reduce a number via square root you will eventually reach an infinite response and thus it's impossible to solve, let alone with a binary computer system. I would love the very first quantum computer to do 1/3. Just use up all the CPU and energy it has in a problem it can't solve. Forever in time. Look not at the computer as the failure scenario but math in general. At some point you stop and round. When that happens, an error is introduced when you extend the answer beyond the rounding point. At some point you will fine an infinite answer and/or answers. I can write you a computer program to write a single infinite answer. Combining two of them produces the same infinite process. Here is a better answer. Can we shift the base in a way that allows us to answer random questions like these?

nestorD 5y ago
Computing the value would be a problem but determining which is bigger is purely a CS question (just one that cannot be solved directly with our usual floating point tool: IEEE 754 arithmetic).
monktastic1 5y ago
You may have missed the point. Although fractions may have infinite representations, the question of which sum of fractions is larger is a much easier problem to solve: "On the other hand, comparing the sums of fractions is pretty easy, because division is nice and well behaved. So the question is how complicated square roots are."
ChrisLomont 5y ago
>Each time you reduce a number via square root you will eventually reach an infinite response and thus it's impossible to solve, let alone with a binary computer system. This is incorrect. All the symbolic math programs in the world provide counterexamples. There is no need to deal with infinite length decimal numbers to do a lot of proving of things in mathematics, in the same manner when I prove things by hand I do not need to write out infinite length numbers. Your mistake is assuming the only way to analyze a sqrt of a number is to write it out in infinite precision. That is not needed. For example, you can prove on a computer that sqrt(19) > sqrt(17) without having to evaluate either side as a decimal number. For example, Mathematica (or any symbolic program), entering Sqrt[19]>Sqrt[17] returns True.

credulousperson 5y ago

A small note: If you allow randomized algorithms, this problem is actually known to be in P^PP^PP^PP which is well within PSPACE in some sense, but still a ridiculously bad bound. See https://cstheory.stackexchange.com/a/4056 https://cstheory.stackexchange.com/a/4056.

zoomablemind 5y ago

I thought that any algorithms relating with real numbers (and floating point) require use of some epsilon as a measure of closeness. In such approach some different numbers will be treated as equals, but qualified with the epsilon. Thus it could be made practical, as long as epsilon is chosen appropriately to the application domain.

samyrasmy 5y ago

Here is my attempt at proving that this can be done in P-time. I am using the fact that square roots can be expressed as periodic continued fractions, and that there is an upper bound on the period of these fractions which must thus be unique. Please tell me if there are any issues! I hope this holds :) The period of the square root of n is less than k1 * (sqrt(n) log (log (log (n))) ) = Lm(n) We can find this period in polynomial time (n^3) each term is smaller than 2*sqrt(n) Therefore, all square roots up to n are uniquely represented as part of a continued fraction expansion as a0 + 1/(a1 + 1/ (a2 + ...)) ... up to a[Lm(n)]. If we transform this nested fraction into a decimal number, any modification of this fraction will necessarily lead to a delta in the number by at least (a[Lm(n))]^-(Lm(n)), which is at most 2sqrt(n)^-(sqrt(n) Therefore, accurately computing the square root up to the most significant digit of 2sqrt(n)^-(2sqrt(n)) will yield a result distinct from any square root up to n. In the case of a sum of square roots, assuming that n is the largest root, accurately computing the sum up past the most significant digit of 2sqrt(n)^-Lm(n) will be sufficient to decide if a sum of square roots is larger than or smaller than another. 2sqrt(n)^-Lm(n) is reciprocally subexponential, thus the number of digits needing to be computed will grow sub-linearly with n Therefore, the problem can be solved in polynomial time.

eurasiantiger 5y ago
Can we get a validity test and benchmark comparing this solution to the generally accepted one?