Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Root of a number with error range - similar to Leetcode 69 sqrt(x) - May 3, 2017
using System;
class Solution
{
// x < 1, log(1/x) - each search constanat time
// x > 1, log(x) -
static double root(double x, uint n)
{
const double errorRange = 0.001;
if( equalByError(x, 1)) return 1;
if( equalByError(x, 0)) return 0;
// x < 1, y ^ n = x
if( x < 1) return getSmallRangeDivision(1.0, root ( 1.00/x, n));
// assuming x > 1
double start = 1.001;
double end = x - 0.001;
while(start < end && end - start > errorRange )
{
double middle = start + (end - start)/2;
var checkedValue = Math.Pow(middle, n);
if(equalByError(checkedValue, x)) return middle;
else if(checkedValue < x )
{
start = middle;
}
else
{
end = middle;
}
}
return start;
}
private static bool equalByError(double x, double y)
{
return Math.Abs(x - y) < 0.001;
}
private static decimal getSmallRange(double x)
{
return decimal(x , 3);
}
private static double getSmallRangeDivision(double x, double y)
{
return (int)(x * 1000/ y) / (double)1000; // error range 0.0001
}
static void Main(string[] args)
{
double[] result = new double[3];
result[0] = root(7, 3) ;
result[1] = root(9, 2);
result[2] = root(0.9, 2);
foreach(var item in result)
{
Console.WriteLine(item);
}
}
}
// 1.913 * 1.913 * 1.913 = 7, n =3
// Math.Abs(2.999 * 2.999 - 9) < 0.001
// binary search - n > 1, range 1, x
// start = 1
// middle = 1 + ( x -1 )/2, middle ^ n < x, error > 0.001
// middle = start, assuming x > 0
// is there better than binary search algorithm? O(logn), n = x - 1.
// edge cases: x nonnegative, x >= 0, if it is 0, the answer is 0
// x = 1, the answer is 1
// if x in (0 , 1), small than 1, search range x, but it should be less than 1, search range (x, 1)
// else if x > 1, search range is (1, x)
// 0, 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.