Quick 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 sqrt with Newton vs binary search

Company: Uber

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Implement two Python functions: (1) sqrt_newton(x, tol=1e-12) returning the principal square root for float x ≥ 0, without using sqrt/pow; handle x ∈ [0, 1e308], return 0 for x=0, +∞ for x=+∞, and raise ValueError for x<0. Choose a numerically stable initial guess that avoids overflow/underflow for very large/small x, and stop when |y^2−x|/max(x,1) ≤ tol or after 100 iterations. Ensure no division-by-zero and discuss how to guard against catastrophic cancellation. (2) isqrt_bisect(n) returning ⌊√n⌋ for integer n with 0 ≤ n < 2^63, using binary search with O(log n) iterations and no intermediate overflow (e.g., compare mid ≤ n//mid instead of mid*mid ≤ n). Then answer: a) Prove Newton’s method for √x is quadratically convergent near the root; b) For worst-case x in [1e−12, 1e12] with y0 = max(1, x), estimate the iterations to reach tol and justify; c) Compare per-iteration cost and total operations versus binary search for 64-bit n; d) Briefly outline how you would extend sqrt_newton to support complex results for x<0 under IEEE‑754 and why naive branching can be unsafe.

Quick Answer: 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.

sqrt_newton — principal square root via Newton's method

Implement `sqrt_newton(x, tol=1e-12)` returning the principal square root of a nonnegative float `x` WITHOUT using `sqrt` or `pow`. Requirements: - Domain: `x` in `[0, 1e308]`. - Special cases: return `0.0` for `x == 0`; return `+inf` for `x == +inf`; raise `ValueError` for `x < 0`. - Numerical stability: pick an initial guess that avoids overflow/underflow for very large or very small `x` (scale via the binary exponent, e.g. `frexp`). - Iteration: Newton update `y <- 0.5 * (y + x/y)`; stop when `|y^2 - x| / max(x, 1) <= tol` or after 100 iterations. - Robustness: never divide by zero, and guard against catastrophic cancellation in the stopping test by evaluating `|y^2 - x|` as `|y| * |y - x/y|` (reuse the quotient `u = x/y`). Return the float `y`. (Tests use exactly-representable perfect squares where the iteration converges to the exact value.)

Constraints

  • 0 <= x <= 1e308 (IEEE-754 double)
  • tol > 0 (default 1e-12)
  • Do not use sqrt or pow
  • Raise ValueError for x < 0; return 0.0 for x == 0; return +inf for x == +inf

Examples

Input: (0.0,)

Expected Output: 0.0

Explanation: Special case: sqrt(0) is exactly 0.0.

Input: (1.0,)

Expected Output: 1.0

Explanation: sqrt(1) = 1; the guess starts at 1 and the residual is already 0.

Hints

  1. Decompose x = m * 2**e with frexp; an initial guess of 2**(e//2) keeps you within a factor of sqrt(2) of the root, so no overflow even for x ~ 1e308.
  2. The Newton step for f(y)=y^2-x is y <- 0.5*(y + x/y); reuse u = x/y for both the stopping test and the update.
  3. Compute the residual as |y|*|y - x/y| instead of |y*y - x|: this avoids overflow of y*y near 1e154 and avoids cancellation between two large near-equal numbers.

isqrt_bisect — integer floor square root via binary search

Implement `isqrt_bisect(n)` returning `floor(sqrt(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` so the product never overflows. - Use a tight upper bound derived from `n.bit_length()` to roughly halve the iteration count. Return the integer floor of the square root.

Constraints

  • 0 <= n < 2**63
  • O(log n) iterations
  • Must not compute mid*mid (overflow); compare mid <= n // mid

Examples

Input: (0,)

Expected Output: 0

Explanation: Edge case: floor(sqrt(0)) = 0 via the n<2 short-circuit.

Input: (1,)

Expected Output: 1

Explanation: Edge case: floor(sqrt(1)) = 1.

Hints

  1. For 0 and 1, floor(sqrt(n)) == n, so short-circuit n < 2.
  2. From k = n.bit_length(), floor(sqrt(n)) < 2**ceil(k/2); start hi at 2**((k+1)//2) to cut iterations.
  3. Binary search on the candidate root; the overflow-safe predicate is mid <= n // mid, which is equivalent to mid*mid <= n for positive mid.

Loading coding console...