Update: 2015 - 01 - 07
Newton's method
x_(n + 1) = x_(n) + f(x_(n)) / f'(x_(n))
let f(a) = a^2 - x we want to find a so that f(a) ~
0
a_(n+1) = a_(n) + f(a_(n)) / 2 * a_(n)
public class SquareRoot { public int sqrt(int x) { double prev = x / 2.0; double guess = prev / 2.0 + x / (2.0 * prev); while (Math.abs(guess - prev) > 0.1) { prev = guess; guess = prev / 2.0 + x / (2.0 * prev); } return (int)guess; } }
The only problem I don't understand is that if alternatively I use
guess = prev - x / (2.0 * pref);
I will exceed the time limit.
Another brilliant way is to use bisection method. The basic idea is, the square root of x must lie between 0 to x. So we keep reduce the range by comparing the square of mid with x, we will find our solution.
public class SqureRoot { public int sqrt(int x) { long low = 0; long high = x; while (low <= high) { long mid = (low + high) / 2; if (mid * mid == x) return (int)mid; else if (mid * mid < x) low = mid + 1; else high = mid - 1; } return (int)high; } }
No comments:
Post a Comment