4 ms·

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

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.
- tgflynn 5y ago
  OK, I think I understand the problem now. It's that the actual answer can be very small but non-zero. You can put error bars on your calculations but that doesn't necessarily tell you which side of zero the answer is on. In fact you would need to do the calculation with enough bits to represent the true answer which you don't know a priori. What you can do though is put an upper bound on the size of the difference between the two sums and you can make that bound as small as you want by using more bits.

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.

tgflynn 5y ago
OK, I think I understand the problem now. It's that the actual answer can be very small but non-zero. You can put error bars on your calculations but that doesn't necessarily tell you which side of zero the answer is on. In fact you would need to do the calculation with enough bits to represent the true answer which you don't know a priori. What you can do though is put an upper bound on the size of the difference between the two sums and you can make that bound as small as you want by using more bits.