昨天笔试遇到一题，要求用java实现sqrt，当时就想，哪里管过怎么实现的，都是直接拿来用的。所以晚上就查了一些资料，将实现过程整理如下：
图示：
算法思路（说明，下面的“碎片被开方数”，“补丁平方根”是为了方便称呼自取的名称）：
推测公式为(high_patchRoot×2×10+bit_patchRoot)×bit_patchRoot，使其尽可能小于等于fragmentSqrt，循环bit_patchRoot从9~1即可。high_patchRoot为上一轮的补丁平方根”patchRoot。
推测公式的解释：以1156为例，易观察到它的平方根是两位，十位是3，设个位是a，则（3×10+a）2=1156，即302+2×3×10a+a2=1156，即3×2×10a+a2=256，3×2×10a+a2变形为（3×2×10+a）a，即为推测公式。故2为（x+y）2=x2+2xy+y2中的2，×10表示是十位数。
remainder=fragmentSqrt-(high_patchRoot×2×10+bit_patchRoot)×bit_patchRoot
patchRoot=high_patchRoot×10+bit_patchRoot
①151为“碎片被开方数”fragmentSqrt
②2为bit_patchRoot
③3为high_patchRoot，即上一轮的patchRoot
④27为余数remainder
⑤32位patchRoot
①~⑤是第二轮结果
代码
package kafka.productor;
import java.math.BigInteger;
import java.util.Scanner;
public class MySqrt {
static final BigInteger NUM20 = BigInteger.valueOf(20);// 将后面使用的参数定义为final常量
public static void main(String[] args) {
MySqrt mySqrt = new MySqrt();
Scanner input = new Scanner(System.in);
System.out.println(mySqrt.sqrt(input.next()));
}
public String sqrt(String n){
String patchRoot="0"; // 平方根初始化为字符串0
String remainder=""; //余数初始化为""
if(n.length()%2 != 0) n = "0"+n; //如果n是奇数为，防止substring越界
for(int i=0; i<n.length()/2; i++){//两两分组
String fragmentSqrt = remainder+n.substring(2*i,2*i+2); //第2步
String high_patchRoot = patchRoot;
String bit = getBit(new BigInteger(high_patchRoot),new BigInteger(fragmentSqrt)); //第3步
remainder = getRemainder(new BigInteger(fragmentSqrt),new BigInteger(high_patchRoot),new BigInteger(bit)); //第4步
patchRoot = high_patchRoot+bit; //第5步
}
return patchRoot.substring(1); // 去掉结果之前的0
}
private String getRemainder(BigInteger fragmentSqrt, BigInteger high_patchRoot, BigInteger bit_patchRoot) {
return fragmentSqrt.subtract(high_patchRoot.multiply(NUM20).add(bit_patchRoot).multiply(bit_patchRoot)).toString();
}
private String getBit(BigInteger high_patchRoot,BigInteger fragmentSqrt) {
int i;
for(i=9; i>0; i--){
BigInteger bi = BigInteger.valueOf(i);
if (fragmentSqrt.compareTo(high_patchRoot.multiply(NUM20).add(bi).multiply(bi))>=0)
break;
}
return String.valueOf(i);
}
}
参考
https://blog.csdn.net/Super2333/article/details/79476149
https://baike.baidu.com/item/%E5%BC%80%E5%B9%B3%E6%96%B9%E8%BF%90%E7%AE%97/1165387?fr=aladdin
为了得到而努力
2019-03-07
转载请注明来处。
原文：https://www.cnblogs.com/malw/p/10486659.html