Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created May 31, 2017 19:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/5f296becfac20c0e9b1d4a1190275e5d to your computer and use it in GitHub Desktop.
Save jianminchen/5f296becfac20c0e9b1d4a1190275e5d to your computer and use it in GitHub Desktop.
Root of a number - error range is 0.001 - practice code, fixed the grammar errors and ran a few test cases, edge cases as well.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace RootOfANumber
{
/// <summary>
/// May 30, 2017 - code practice
/// x > 1, 7, 1 7 -> 1000 - 7000 o(logn) , 1000x - O(log1000x) = 10 logx
//space O(1)
// x^(1/n)
// 4^ (1/2) = 2
// x = 7, n = 3, Math.Abs(1.913 * 1.913 * 1.97 - 7) < 0.001
// x = 9, n = 2, 2.999 * 2.999
// 0.001 -> 3 decimals
// x >= 1 , 0 - 1 , > 1
// x = 1, 1.000 = 1, n >0
// x = 0, 0 ,
// (0, 1) x in (0, 1) => 1/x (1, upper bound ), 1/ x
// (1, upper bound ), 0.001,
// given x > 1, 1 - x -> binary search 1 + ( x - 1)/ 2, compare power of n middle x
// 0.001
/// </summary>
class RootOfANumber
{
static void Main(string[] args)
{
var result = root(0.001, 3);
Debug.Assert(Math.Abs(result - 0.1) < 0.001);
var result2 = root(1000, 3);
Debug.Assert(Math.Abs(result2 - 10) < 0.001);
}
// test case: 0
// 1
// 0.001, n = 3, 0.1
// 1000 , n = 3, 10
// ..
static double root(double x, int n)
{
const double errorRange = 0.001;
// your code goes here
if (x == 0 || x == 1 || x < errorRange || Math.Abs(x - 1) < errorRange) // 0, 1
{
return x;
}
bool isLessThanOne = x < 1; // 0.001
if (isLessThanOne)
{
var reverse = getReverse(x); //
var result = root(reverse, n);
return 1000 / result / 1000.0; // 0.1
}
// binary search to find the value
return FindRootBinarySearch(x, n, 1, x); // 1000
}
public static double FindRootBinarySearch(double search, int n, double start, double end) // 1. 1000
{
while (start < end && (end - start) > 0.001) // while, not if. Fix writing error after mocking
{
double middle = start + (end - start) / 2; // 1 + 999/2 (middle keep to 3 decimal )
bool equalToSearch = isEqual(middle, search, n); //
bool middleBigger = isBigger(middle, search, n);
if (equalToSearch) return middle;
if (middleBigger)
{
end = middle; // ? "end = middle - 0.001"
}
else
{
start = middle; // ? "start = middle - 0.001"
}
}
return start;
}
// 0 - equal
// 1 - bigger
// -1 - smaller
private static bool isEqual(double middle, double search, int n)
{
return Math.Abs(Math.Pow(middle, n) - search) < 0.001; // out-of-range
}
private static bool isBigger(double middle, double search, int n)
{
double power = Math.Pow(middle, n);
return Math.Abs(power - search) > 0.001 && power > search;
}
// assume that x is in (0, 1)
private static double getReverse(double x)
{
int result = (int) (1000 / Math.Max(x, 0.001)); // decimal to 3, 0.001 1000 * 1000 = 10 ^6
return result / 1000.0;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment