How should I practice Newton Square Root to a Guaranteed Tolerance?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Squarepoint Capital phone screen problems in FastPrep.

Is Newton Square Root to a Guaranteed Tolerance associated with Squarepoint Capital?

FastPrep tags this as a Squarepoint Capital phone screen coding practice problem when the problem catalog has that company and stage context.

Newton Square Root to a Guaranteed Tolerance

Squarepoint Capital● EasyFULLTIMEPHONE SCREEN

Problem statement

Given a positive number x and a tolerance tol, approximate the square root of x with Newton's method, and stop as soon as the error is guaranteed to be at most tol.

Use exactly this procedure:

Start with y = max(x, 1).
If y - x / y <= tol, return y.
Otherwise replace y with (y + x / y) / 2 and go back to step 2.

Every value of y in this procedure is at least the square root of x, and y - x / y is an upper bound on how far y is above it, so the returned value is never more than tol above the true square root.

Return the value this procedure returns. An answer is accepted when it is within 10^-12 * max(1, |expected|) of the expected value.

Function

sqrtWithinTolerance(x: double, tol: double) → double

Examples

Example 1

x = 4.0tol = 0.1return = 2.05

Start at y = 4. The bound 4 - 4 / 4 = 3 is above 0.1, so update to (4 + 1) / 2 = 2.5. The bound 2.5 - 1.6 = 0.9 is still above 0.1, so update to (2.5 + 1.6) / 2 = 2.05. Now 2.05 - 4 / 2.05 is about 0.0988, which is at most 0.1, so the answer is 2.05. Its actual error is 0.05.

Example 2

x = 0.25tol = 0.01return = 0.5001524390243902

x is below 1, so start at y = 1, which is above the root 0.5. The bounds are 0.75 at y = 1, 0.225 at y = 0.625 and about 0.0247 at y = 0.5125, all above 0.01. The next value, about 0.5001524, has a bound of about 0.0003, so it is returned.

Example 3

x = 2.0tol = 1e-06return = 1.4142135623746899

The values are 2, 1.5, about 1.4166667, about 1.4142157 and about 1.41421356237469. Their bounds are 1, about 0.167, about 0.0049, about 4.2 * 10^-6 and about 3.2 * 10^-12. The fourth bound is still above 10^-6, so the procedure makes one more update and returns 1.4142135623746899, which is within about 1.6 * 10^-12 of the square root of 2.

Constraints

10^-6 <= x <= 10^12
10^-6 <= tol <= 1
Inputs and the output are double-precision floating-point numbers.