81–90 of 189 posts
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 root…
Consider [25] and [9, 9]. 25 > 18, but 5 < 6.
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 root…
Compare the plotted graphs of x (input) vs. sqrt(x) (output)
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…
Why do you need the bounds for every combination of the N square roots? Isn't it enough to get the minimum distance between the two nearest elements in that list? If so, why not consider the 2N degree polynomial where P(z) = \prod (z^2 - a_i) ? This polynomial is only 2N degree and gives you the bound you actually care about, the number of bits needed to sum two numbers in the list. Since you're summing 2N of them in…
> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to establish some kind of bound on this. Like, maybe we should be able to say “if you add two lists of n numbers, each of which has d digits, then they can’t disagree for more than k * n * d digits” for some k. But no-one’s been able to prove anything like this. You c…
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…
That should be linear in the total number of elements in the list.
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 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…
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)
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…
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…
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.
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…
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.
> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to establish some kind of bound on this. Like, maybe we should be able to say “if you add two lists of n numbers, each of which has d digits, then they can’t disagree for more than k * n * d digits” for some k. But no-one’s been able to prove anything like this. You c…