3 ms·
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 digit
by 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 agoFor (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 ago1) 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.