Computer Arithmetic

For very large x, computing √(x + 1) − √x in floating point suffers catastrophic cancellation. Which rewrite computes it accurately?

  1. ACompute 1 ÷ (√(x + 1) + √x)
  2. BCompute √(x + 1 − x)
  3. CConvert √(x + 1) and √x to double precision and subtract with the same formula
Show answer and explanation

Answer: A. Compute 1 ÷ (√(x + 1) + √x)

√(x + 1) and √x are nearly equal, so subtracting them directly cancels the leading digits. Multiplying numerator and denominator by √(x + 1) + √x gives (x + 1 − x) ÷ (√(x + 1) + √x) = 1 ÷ (√(x + 1) + √x), eliminating the subtraction of close values. √(x + 1 − x) equals 1 and is simply wrong. Switching to double helps, but the same problem returns for larger x, so it is not a fundamental fix.

  • A. Correct. The rewrite removes the subtraction and avoids cancellation.
  • B. √(x + 1 − x) equals 1, which is not the original expression.
  • C. Even in double precision, the problem returns for larger x.
Practice this topic Back to topic

More Computer Arithmetic questions

  1. In single precision, adding 1 to 100 million (10⁸) leaves the result unchanged at 100 million. Which explains this?
  2. What is the purpose of Kahan (compensated) summation when adding many floating-point numbers?
  3. What is the advantage of computing a × b + c with an FMA (fused multiply-add) instruction?
  4. What is the main reason bfloat16 is used for AI training?
  5. When training neural networks in FP16 (half precision: 1 sign, 5 exponent, 10 significand bits), which problem tends to arise and is countered by scaling up the loss (loss scaling)?