4 ms·
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 t
by 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 agoWhen 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 agoOK I get it, rounding error in calculating the square roots.
- ted_dunning 5y agoYou 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 agoThe 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.