Wednesday, January 5, 2011

My Personal Square Root

It was really a fun to revise how to actually calculate square roots on paper!..
Following is my attempt, it works fine, but I am sure there are faster methods.

public static String squareRoot(int number, int decimal_precision){
String answer="";
String pairedNumber = ""+number;
int precision=1;

if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0)
return ""+Math.sqrt(number);

int initialGuess = (int) Math.sqrt(number);
answer+=(""+initialGuess+".");

if ((""+number).length() % 2 != 0)
pairedNumber="0"+pairedNumber;

for (int i=0; i<3*decimal_precision; i++)
pairedNumber=pairedNumber+"0";

String remainder = ""+(number - (initialGuess*initialGuess));
String factor = ""+(2*initialGuess);

while (precision <= decimal_precision){
//System.out.println("remainder="+remainder);
String dropPair = remainder+pairedNumber.substring(2*precision+2, 2*precision+4);
//System.out.println("drop : "+dropPair);
//System.out.println("factor :"+factor);
for (int i=0; i<=9; i++){
String newFactor = factor+i;
// System.out.println("new factor chk = "+newFactor);
BigInteger a = new BigInteger(newFactor).multiply(BigInteger.valueOf(i));
BigInteger b = new BigInteger(dropPair);
BigInteger c = (new BigInteger(newFactor).add(BigInteger.ONE)).multiply(BigInteger.valueOf(i+1));
//System.out.println(a+" "+b+" "+c);
if (a.compareTo(b) == -1 && b.compareTo(c) == -1)
//if (Integer.parseInt(newFactor)*i <= Integer.parseInt(dropPair) && Integer.parseInt(dropPair) < Integer.parseInt(newFactor)*(i+1))
{ //System.out.println("Found new factor : "+newFactor +" with i="+i);
answer=answer+i;
factor = ""+(new BigInteger(newFactor).add(BigInteger.valueOf(i)));
//factor = ""+(Integer.parseInt(newFactor)+i);
remainder = ""+(new BigInteger(dropPair).subtract(a));
//remainder=""+(Integer.parseInt(dropPair) - (Integer.parseInt(newFactor)*i));
break;
}
}
precision++;
// System.out.println("answer="+answer);
}


return answer;
}

Sample I/O:
System.out.println(squareRoot(2, 100));
1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727

No comments:

Post a Comment

Is my blog being read?