Sandeep
BAN USERGeneralizing the above solution further:
//Given a value (in double) return its nth root.
public class FindNthRoot {
public static double nthRoot(double number, int n, double tolerance) {
double start = 0;
double end = number;
double root = start + (end - start) / n;
int iterations = 1;
//invariant: (end - start) > tolerance
while ((end - start) > tolerance) {
double pow = nthPower(root, n);
if (pow > number) { // 12 is the number then initial root would be 6 and pow is 36 for n = 2 in which case pow > number
end = root; // reduce end to root i.e. 6
} else if (pow < number) { // 9 < 12
start = root; // reset start
} else {
return root;
}
root = start + (end - start) / n;
iterations++;
}
System.out.println("start:" + start + ", " + "end: " + end + ", " + "iterations:" + iterations);
return root;
}
private static double nthPower(double num, int n) {
double result = 1;
for (int i = 0; i < n; i++) {
result = result * num;
}
return result;
}
public static void main(String[] args) {
System.out.println(FindNthRoot.nthRoot(36.4345, 2, 0.000010));
System.out.println(FindNthRoot.nthRoot(27.4345, 3, 0.000010));
System.out.println(FindNthRoot.nthRoot(256.4345, 4, 0.000010));
}
}
below are the results that I got
start:6.0360919429063795, end: 6.0361006295681, iterations:23
6.03609628623724
start:3.0160069149974285, end: 3.0160132810008373, iterations:25
3.0160090369985646
start:4.00169557736413, end: 4.001703962607476, iterations:38
4.0016976736749665
a tree structure like this where except for root node all other nodes have just one child will make the alogrithm move up and down the tree more often and hence DFS would be taxing as compared to BFS. (Even in DFS we could always stop at hop k i.e. Depth K the tax is in moving back and forth)
a11
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
ok if compiler or some other layer beneath our program abstracts the big-endian vs little endian format for the program thus ensuring that the program works consistently across different systems then this program need not try to change the input to big-endian. Isnt it?
- Sandeep June 07, 2014The assumption that I am making here is that the output has to be presented in a big or little endian formatted binary number and not that the input is big/little endian formatted.
If I understand it right, big and little endian should only affect the way they are stored in memory address and not their binary code representations. Otherwise I guess programs containing shiftwise operators would not be portable.
The logic in my above code is still flawed though since as you pointed out the format is not applicable at bits instead it is at bytes.
If I understand it right, big and little endian should only affect the way they are stored in memory address and not their binary code representations.
otherwise a program containing a bitwise shift operator would not be portable since the meaning would change e.g. if lets say a represents 13 then your intention in a >> 1 would be to push bits in a to right by 1 position and you would expect 6 as the result. if a is binary 00000000, 00000000, 00000000, 00001101 then you would get what you expect instead if a is coded as 00001101, 00000000, 00000000, 00000000 then a >> 1 would give a different number altogether making the operation non-portable.
public class DecimalToBinaryConverter {
public String decimalToBinary(int num, boolean bigEndian) {
StringBuilder strBr = new StringBuilder();
while (num > 0) {
strBr = bigEndian ? strBr.insert(0, num % 2) : strBr.append(num % 2);
num = num / 2;
}
return strBr.toString();
}
public static void main(String[] args){
DecimalToBinaryConverter convrtr = new DecimalToBinaryConverter();
System.out.println(convrtr.decimalToBinary(11, true));
System.out.println(convrtr.decimalToBinary(11, false));
}
}
results are
1011
1101
// Take a non-trivial example
// 25
// 12 34
// 1 3 4 5
// if 3 is chosen The answer should be since the links wont change.
// 3
// 12
// 1 25
// 34
// 4 5
// 3's parent's parent becomes right child of 3's parent and this continues up untill root is reached and then stops.
public class BinaryTree<T>{
Node<T> root;
private Class Node<T>{
Node<T> left;
Node<T> right;
}
public BinaryTree<T> tiltUsingLeafNode(BinaryTree<T> tree, T leafNode){
Node<T> parent = findParent(leafNode);
return reverseParentRelationShip(root, parent);
}
}
The solution would be easier if there is a redundant parent link in each node along with left and right links.
- Sandeep June 07, 2014
A more generic approach could be based on applying Newton Rapshon's method to find roots of (x^n - number) = 0
- Sandeep June 08, 2014