Better Upper Bounds for Square-Root-Sum and Straight-Line Program PositivityResearch Paper
A short arithmetic computation can describe an integer too long to write out efficiently. Repeated squaring already produces this effect using only the literal 1, addition and multiplication. Determining the sign of the resulting integer is therefore a separate computational question from evaluating it in binary. This question matters in exact numerical…