## Newton's Method

This is copied from my friend Newton.

Then I wrote this code:

``````public int sqrt(int x) {
if(x < 0) return -1;
if(x == 0) return 0;

// x/t + t = 2t
double t = (double)x;
double tt = 0;
while( (int)tt - (int)t != 0 ){
tt = t;
t = (x/t + t) /2;

}

return (int)tt;
}
``````

## Programming Way

Well, I replaced the mathematical way finally, maybe, I think I should do this in programming way.

### Brute Force

Search through `1..x`, find the `i`, such that `i^2 == x` or `i^2 < x < (i + 1)^2`.

### Binary Search

As we can brute force, and `1..x` is obviously ordered, we can do it by applying binary search pattern.

``````treat 1..x as the content of an array[0..x-1]

while s < e

m = (s + e) / 2

if (m + 1)^2 == x
return m + 1

if (m + 1)^2 < x < (m + 1 + 1)^2
return m + 1

if x < (m + 1)^2
e = m
else
s = m + 1
``````

#### Overflow

The testcases contain some large numbers like `Integer.MAX_VALUE`, code will fail due to overflow.

To avoid this, change any `+` and `*` to `-` and `/`

• `m = (s + e) / 2` -> `m = (e - s) / 2 + s`
• `(m + 1)^2 == x` -> `x / (m + 1) == (m + 1)`

## 0x5f3759df

``````float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;

x2 = number * 0.5F;
y  = number;
i  = * ( long * ) &y;                       // evil floating point bit level hacking
i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
y  = * ( float * ) &i;
y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

return y;
}
``````