161–170 of 189 posts
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.
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…
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.
Earlier quoted context omitted.
Does that actually work? It seems that the degree of minimal polynomial having as root the sum of N square roots might be up to 2^N, and if you then apply the bound at https://en.wikipedia.org/wiki/Geometrical_properties_of_poly... (where n = 2^N) you get a bound on the order of at least 2^N digits (more precisely 2^N (N + D)). So it doesn't seem to lead to a proof of a subexponential number of equal digits, unless t…
Yes, the worst-case complexity is exponential in N, but the wording in the article could lead you to believe that no explicit exponential bound is known, which is false.
Earlier quoted context omitted.
> At that point you know the answer, you just have to add up the differences. What if your sum in this step is zero?
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 s…
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.
> 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 to…
> there is something profoundly weird about [numbers] you should hear John Conway (RIP) talk about numbers - https://www.youtube.com/watch?v=1eAmxgINXrE
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.
Earlier quoted context omitted.
These are fine but pretty idiosyncratic. HN doesn't have citation rules so the 'always' seems overstated. People linking papers are already going the extra mile for the benefit of others and we don't really need to berate them about how they're holding their generosity wrong.
I didn't mean to come across as berating, but rather as suggesting a better way to link. I hoped that 'request' and 'please' would set the proper tone, but am certainly open to better ways of wording it. I meant 'always' to indicate that I specifically wasn't just complaining pointlessly about the present case, but rather talking about future links; but I can see how it came across like the scolding 'always' as in a…
My personal preference is the PDF link.
Your request was perfectly polite, I was simply wondering what your rationale was for it.
Earlier quoted context omitted.
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 s…
> 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 th…
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!)
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...
Earlier quoted context omitted.
But the article presents it as an interesting pure math problem, and doesn't claim that the FP64 solution isn't good enough. I should add that the people who write state of the art "practical" TSP solvers spend a lot of time thinking about the "theoretical" complexity of it too. Turns out it's a good way to engineer those "good enough" algorithms, provide bounds etc
Sure and there are a lot of simple ways to improve the accuracy of the simple approach before you go for the pure math sledgehammer here. It's all a question of how accurate the answer needs to be. For example, It's pretty easy to come up with an FP64 error bound on the sum. And if the difference between the two sums is greater than that error bound you don't need to do anything more complicated. Where this would get…
For e.g. when you say "anything beyond that is likely unnecessary gold plating", I know you mean "exact algorithms (like the PSPACE algorithm) are unnecessary for solving real-life instances", but without context it sounds like you're saying "there is no conceivable reason people should care about the exact algorithms"