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
