java实现开根号的运算方式寻技术

java实现开根号的运算

面试的时候，偶然被问到，开根号的实现，虽然给面试官讲解了思路，但是没有实际实现过，闲来无事，就把自己的思路写一下，做个笔记。

如果某个数字正好可以开根号为2个整数，例如1,4,9等，那就很简单了。

如果某个数字不可以正好开根号为2个整数，而且要保留几位精度，例如：2,3,5等，我们该怎么办呢？？？？？

首先我们可以把这个数字分成整数部分和小数部分，分别计算。

例如√5≈2.236 我们可以先算出整数部分为2，然后在根据保留几位精度，去计算小数部分。依次计算十分位、百分位和千分位等，然后把整数位+十分位+百分位+千分位+。。。，结果就是我们想要的结果了。

下面我写了一个通用的方法，可以根据传的参数来保留精度。

package comc.n;
import java.math.BigDecimal;
public class Square {
	public static void main(String[] args) {
		System.out.println(Math.sqrt(5));
		System.out.println(MathSqure(5, 6));
	}
	/**
	 * 
	 * @param n  需要开根号的数据
	 * @param m  需要保留的精度,即几位小数
	 * @return
	 */
	public static double MathSqure(int n, int m){
		double[] arr = new double[m];
		if(m >0){
			arr = sc(m);
		}
		int s = sq(n);
		return sb(n, s, arr);
	}
	/**
	 * 计算整数位
	 * @param n
	 * @return
	 */
	public static int sq(int n){
		if( n == 1){
			return 1;
		}
		int tmp = 0;
		for(int i=1;i<=n/2+1;i++){
			if(i*i == n){
				tmp = i;
				break;
			}
			if(i*i > n){
				tmp = i-1;
				break;
			}
		}
		return tmp;
	}
	/**
	 * 计算要保留几位小数
	 * @param m
	 * @return
	 */
	public static double[] sc(int m){
		double[] arr = new double[m];
		int num = 0;
		while(num != m){
			double f = 1;
			for(int i=0;i<=num;i++){
				f = f*10;
			}
			arr[num] = 1/f;
			num++;
		}
		return arr;
	}
	/**
	 * 开根号
	 * @param n
	 * @param j
	 * @param arr
	 * @return
	 */
	public static double sb(int n, double j, double[] arr){
		double tmp = j;
		for(int p=0;p<arr.length;p++){
			if(p>0){
				j = tmp;//计算过后的值（整数位+小数位的和，赋值给j，下面继续运算）
			}
			for(int i=1;i<=9;i++){//小数位只有九位{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9}
				tmp = i*arr[p]+j;//i*arr[p],相当于每次加0.1,0.2 ...
				if(tmp*tmp == n){
					return tmp;
				}
				if(tmp*tmp >n){
					//避免丢失精度
					BigDecimal c1 = new BigDecimal(Double.toString(tmp));
					BigDecimal c2 = new BigDecimal(Double.toString(arr[p]));
					tmp = c1.subtract(c2).doubleValue();
					break;
				}
			}
		}
		return tmp;
	}
}

输出结果：

java实现一定精度的开根号运算

需求：在不借助系统库的情况下，编写一个函数，实现开根号的操作，并且保证一定的精度

代码采用了牛顿迭代法以及二分查找法两种方式并分别打印了他们的循环次数以比较优劣：

/**
 * 实现一个函数，完成对v开根号的操作，误差小于t，不能调用函数库
 */
public class Sqrt{
    /**
     * 可以使用牛顿迭代法
     * 首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了
     */
    public static double iter(int v,double t){
        int i = 0;
        // 首先预估一个数
        double random = v >> 1;
        while(abs((v-random*random)) > t){
            random = (random + v/random) >> 1;
            i++;
        }
        System.out.println("开根号值: "+random+"  ,循环次数: "+i);
        return random;
    }
    // 二分查找法
    public static double binarySearch(int v,double t){
        int i = 0;
        double max = v;
        double min = 0;
        double temp = v >> 1;
        while (abs(temp*temp-v) > t){
            if (temp*temp > v ){
                max = temp;
            } else if(temp*temp < v){
                min = temp;
            }
            temp = (min+max) >> 1;
            i++;
        }
        System.out.println("开根号值: "+temp+"  ,循环次数: "+i);
        return temp;
    }
    public static double abs(double a){
        return (a <= 0.0D) ? 0.0D - a : a ;
    }
    public static void main(String[] args) {
        iter(100,0.1);
        System.out.println("-----------------");
        binarySearch(100,0.1);
    }
}

结果如下：