Implement sqrt with Newton vs binary search
Overview
This question evaluates numerical methods and algorithmic robustness, testing understanding of Newton’s method for root-finding, floating‑point stability and IEEE‑754 edge cases, and integer binary-search techniques for exact floor square roots within the Coding & Algorithms domain for a Data Scientist role.
Implement numerically robust square-root routines and analyze convergence
Task 1 — sqrt_newton(x, tol=1e-12)
Implement a Python function that returns the principal square root of a nonnegative float x without using sqrt or pow.
Requirements:
- Input domain: x ∈ [0, 1e308].
- Special cases: return 0.0 for x = 0; return +∞ for x = +∞; raise ValueError for x < 0.
- Numerical stability: choose an initial guess that avoids overflow/underflow for very large/small x. Do not use sqrt/pow.
- Iteration: use Newton's method and stop when |y^2 − x| / max(x, 1) ≤ tol or after 100 iterations.
- Robustness: avoid division by zero and guard against catastrophic cancellation in the stopping test.
Task 2 — isqrt_bisect(n)
Implement a Python function that returns ⌊√n⌋ for an integer n with 0 ≤ n < 2^63 using binary search.
Requirements:
- Complexity: O(log n) iterations.
- No intermediate overflow: compare mid ≤ n // mid instead of mid*mid ≤ n.
Theory
Answer the following:
a) Prove Newton’s method for √x is quadratically convergent near the root.
b) For worst-case x in [1e−12, 1e12] with starting guess y0 = max(1, x), estimate the number of iterations needed to reach tol = 1e−12 (per the stop rule) and justify.
c) Compare per-iteration cost and total operations of Newton’s method versus binary search for 64-bit n.
d) Briefly outline how to extend sqrt_newton to support complex results for x < 0 under IEEE‑754 and why naïve branching can be unsafe.
Solution
Login required