logo标签列表

Java中BigDecimal的平方根

javabigdecimalsquare-root
66

我们能否在Java中仅使用Java API而不是自定义的100行算法来计算一个BigDecimal的平方根？

1
不用编写自己的算法？达到所需的精度？不可能。 - Louis Wasserman
6
要不要考虑定制一个50行的算法，包括注释？牛顿迭代法并不是很复杂。 - Patricia Shanahan
1
从Java 9开始，您可以使用BigDecimal.sqrt()方法实现！@dimo414对这个问题给出了正确的答案。 - Tim
12个回答
36

我用过这个方法，效果还不错。 这里是一个高层次的演示算法的例子。

编辑：我很好奇如下定义的精度有多高。这里是来自官方源的sqrt（2）：

(first 200 digits) 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147

以下是使用我下面概述的方法，并将 SQRT_DIG 设置为150得到的结果：

(first 200 digits) 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206086685

第一个偏差发生在195位数字精度之后。如果您需要如此高的精度，请自行决定是否使用。

将SQRT_DIG更改为1000会产生1570位数字精度。

private static final BigDecimal SQRT_DIG = new BigDecimal(150);
private static final BigDecimal SQRT_PRE = new BigDecimal(10).pow(SQRT_DIG.intValue());

/**
 * Private utility method used to compute the square root of a BigDecimal.
 * 
 * @author Luciano Culacciatti 
 * @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
 */
private static BigDecimal sqrtNewtonRaphson  (BigDecimal c, BigDecimal xn, BigDecimal precision){
    BigDecimal fx = xn.pow(2).add(c.negate());
    BigDecimal fpx = xn.multiply(new BigDecimal(2));
    BigDecimal xn1 = fx.divide(fpx,2*SQRT_DIG.intValue(),RoundingMode.HALF_DOWN);
    xn1 = xn.add(xn1.negate());
    BigDecimal currentSquare = xn1.pow(2);
    BigDecimal currentPrecision = currentSquare.subtract(c);
    currentPrecision = currentPrecision.abs();
    if (currentPrecision.compareTo(precision) <= -1){
        return xn1;
    }
    return sqrtNewtonRaphson(c, xn1, precision);
}

/**
 * Uses Newton Raphson to compute the square root of a BigDecimal.
 * 
 * @author Luciano Culacciatti 
 * @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
 */
public static BigDecimal bigSqrt(BigDecimal c){
    return sqrtNewtonRaphson(c,new BigDecimal(1),new BigDecimal(1).divide(SQRT_PRE));
}

一定要查看barwnikk的答案。它更加简洁，似乎提供了同样好甚至更好的精度。

4
请注意，对于较大的BigDecimal，此递归解决方案将耗尽堆栈。 - MZB
尝试使用BigDecimal.valueOf(123.123123123*123.123123123)进行计算，它会给出一个有趣的结果。 - Ilya Gazman
6
当执行乘法时，得到的结果是15159.303447561417273129。但是，如果你使用BigDecimal构造函数进行计算，则可以获得正确的答案。对BigDecimal使用String构造函数进行计算，可以得到bigSqrt(new BigDecimal("15159.303447561417273129")) = 123.1231231230000000000000000000000000...。我认为这个问题是由于从Double转换为BigDecimal的方便方法导致的，而不是由于求平方根的算法本身。 - haventchecked
1
@snd 如果您按照javadoc中的链接，您会发现这不是我的作品，我保留了原始作者的作品。还有一个维基百科链接，显示为什么这种方法在数学上是可靠的。 - haventchecked
33
public static BigDecimal sqrt(BigDecimal A, final int SCALE) {
    BigDecimal x0 = new BigDecimal("0");
    BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
    while (!x0.equals(x1)) {
        x0 = x1;
        x1 = A.divide(x0, SCALE, ROUND_HALF_UP);
        x1 = x1.add(x0);
        x1 = x1.divide(TWO, SCALE, ROUND_HALF_UP);

    }
    return x1;
}

这个工作完美！对于超过65536位的数字非常快！

5
+1 对于使用良好的初始估计值。但是 !x0.equals(x1) 有点危险。您有证明循环在所有情况下都会终止吗？ - Henry
3
注意，对于较大的BigDecimal，A.doubleValue() = NaN。使用（例如）A.divide(TWO，RoundingMode.FLOOR）将使其适用于更大的值。 - MZB
4
TWO是什么，它为什么不能编译？它只是数字2吗，BigDecimal.valueOf(2)吗？ - Domchi
3
使用BigDecimal.ZERO代替重复创建对象。同时，调用doubleValue()会丢失任意精度，这违背了本次操作的目的。 - EntangledLoops
10
这个算法是巴比伦算法的一种实现方式。无论初始估计值如何，它都会在精度级别上收敛于相同的精确结果，该精度级别由SCALE确定。该估计仅用于提高性能；Math.sqrt()是一个合理的起点：它在处理大值时失败（使得MZB的备选方案成为一个良好的通用选择），但是当其不返回NaN时并不影响精度。您可能会因计算超出范围而自欺欺人，但绝对不会影响精度。 - Jason C
显示剩余6条评论
18
8

通过使用卡普技巧，可以在仅两行代码中实现此操作，无需循环，精度可达32位数字：

public static BigDecimal sqrt(BigDecimal value) {
    BigDecimal x = new BigDecimal(Math.sqrt(value.doubleValue()));
    return x.add(new BigDecimal(value.subtract(x.multiply(x)).doubleValue() / (x.doubleValue() * 2.0)));
}
你有Karp的技巧的来源吗？我找不到它。 - bobanahalf
4
很遗憾，只有32位数字精度... BigDecimal适用于大数。 - barwnikk
4
这会放弃 BigDecimal 的任意精度，而这恰恰是它的核心特点。 - EntangledLoops
有人可以解释一下为什么这个解决方案需要32位数字精度吗？是最多32位还是恰好32位？ - chomp
5
如果你只需要寻找整数平方根，可以使用以下两种方法。 牛顿迭代法 - 即使对于1000位的BigInteger，也非常快速：
public static BigInteger sqrtN(BigInteger in) {
    final BigInteger TWO = BigInteger.valueOf(2);
    int c;

    // Significantly speed-up algorithm by proper select of initial approximation
    // As square root has 2 times less digits as original value
    // we can start with 2^(length of N1 / 2)
    BigInteger n0 = TWO.pow(in.bitLength() / 2);
    // Value of approximate value on previous step
    BigInteger np = in;

    do {
        // next approximation step: n0 = (n0 + in/n0) / 2
        n0 = n0.add(in.divide(n0)).divide(TWO);

        // compare current approximation with previous step
        c = np.compareTo(n0);

        // save value as previous approximation
        np = n0;

        // finish when previous step is equal to current
    }  while (c != 0);

    return n0;
}

二分法 - 比牛顿法慢50倍以上 - 仅用于教育目的:

 public static BigInteger sqrtD(final BigInteger in) {
    final BigInteger TWO = BigInteger.valueOf(2);
    BigInteger n0, n1, m, m2, l;
    int c;

    // Init segment
    n0 = BigInteger.ZERO;
    n1 = in;

    do {
        // length of segment
        l = n1.subtract(n0);

        // middle of segment
        m = l.divide(TWO).add(n0);

        // compare m^2 with in
        c = m.pow(2).compareTo(in);

        if (c == 0) {
            // exact value is found
            break;
        }  else if (c > 0) {
            // m^2 is bigger than in - choose left half of segment
            n1 = m;
        } else {
            // m^2 is smaller than in - choose right half of segment
            n0 = m;
        }

        // finish if length of segment is 1, i.e. approximate value is found
    }  while (l.compareTo(BigInteger.ONE) > 0);

    return m;
}
1

这是一个非常精确和快速的解决方案，它基于我的BigIntSqRoot solution和以下观察结果：A^2B的平方根是A乘以B的根。使用这种方法，我可以轻松地计算出2的前1000位平方根。

1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472

所以这是源代码。
public class BigIntSqRoot {
    private static final int PRECISION = 10000;
    private static BigInteger multiplier = BigInteger.valueOf(10).pow(PRECISION * 2);
    private static BigDecimal root = BigDecimal.valueOf(10).pow(PRECISION);
    private static BigInteger two = BigInteger.valueOf(2L);

    public static BigDecimal bigDecimalSqRootFloor(BigInteger x)
            throws IllegalArgumentException {
        BigInteger result = bigIntSqRootFloor(x.multiply(multiplier));
        //noinspection BigDecimalMethodWithoutRoundingCalled
        return new BigDecimal(result).divide(root);
    }

    public static BigInteger bigIntSqRootFloor(BigInteger x)
            throws IllegalArgumentException {
        if (checkTrivial(x)) {
            return x;
        }
        if (x.bitLength() < 64) { // Can be cast to long
            double sqrt = Math.sqrt(x.longValue());
            return BigInteger.valueOf(Math.round(sqrt));
        }
        // starting with y = x / 2 avoids magnitude issues with x squared
        BigInteger y = x.divide(two);
        BigInteger value = x.divide(y);
        while (y.compareTo(value) > 0) {
            y = value.add(y).divide(two);
            value = x.divide(y);
        }
        return y;
    }

    public static BigInteger bigIntSqRootCeil(BigInteger x)
            throws IllegalArgumentException {
        BigInteger y = bigIntSqRootFloor(x);
        if (x.compareTo(y.multiply(y)) == 0) {
            return y;
        }
        return y.add(BigInteger.ONE);
    }

    private static boolean checkTrivial(BigInteger x) {
        if (x == null) {
            throw new NullPointerException("x can't be null");
        }
        if (x.compareTo(BigInteger.ZERO) < 0) {
            throw new IllegalArgumentException("Negative argument.");
        }

        return x.equals(BigInteger.ZERO) || x.equals(BigInteger.ONE);
    }
}
Math.sqrt(x.longValue()) 注意，Math.sqrt()（从Java 9开始）需要一个double参数：适用于大约52位。 - greybeard
1

如果您想计算比double类型更大的数字（具有较大规模的BigDecimal）的平方根：

维基百科上有一篇关于计算平方根的文章：http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method

这是我的实现：

public static BigDecimal sqrt(BigDecimal in, int scale){
    BigDecimal sqrt = new BigDecimal(1);
    sqrt.setScale(scale + 3, RoundingMode.FLOOR);
    BigDecimal store = new BigDecimal(in.toString());
    boolean first = true;
    do{
        if (!first){
            store = new BigDecimal(sqrt.toString());
        }
        else first = false;
        store.setScale(scale + 3, RoundingMode.FLOOR);
        sqrt = in.divide(store, scale + 3, RoundingMode.FLOOR).add(store).divide(
                BigDecimal.valueOf(2), scale + 3, RoundingMode.FLOOR);
    }while (!store.equals(sqrt));
    return sqrt.setScale(scale, RoundingMode.FLOOR);
}

setScale(scale + 3, RoundingMode.Floor) 因为过度计算可以提供更高的精度。RoundingMode.Floor 截取数字，RoundingMode.HALF_UP 进行普通四舍五入。

1

在Java API中没有任何东西，因此如果double不够准确（如果不是的话，为什么要使用BigDecimal？）那么您需要像下面的代码一样的东西。

import java.math.BigDecimal;

public class BigDSqrt {
  public static BigDecimal sqrt(BigDecimal n, int s) {
    BigDecimal TWO = BigDecimal.valueOf(2);

    // Obtain the first approximation
    BigDecimal x = n
        .divide(BigDecimal.valueOf(3), s, BigDecimal.ROUND_DOWN);
    BigDecimal lastX = BigDecimal.valueOf(0);

    // Proceed through 50 iterations
    for (int i = 0; i < 50; i++) {
      x = n.add(x.multiply(x)).divide(x.multiply(TWO), s,
          BigDecimal.ROUND_DOWN);
      if (x.compareTo(lastX) == 0)
        break;
      lastX = x;
    }
    return x;
  }
}

来源：http://www.java2s.com/Code/Java/Language-Basics/DemonstrationofhighprecisionarithmeticwiththeBigDoubleclass.htm

1
我想出了一个算法，它不仅可以对每个BigDecimal进行平方根运算，还可以对整数以下的每个根进行计算。最大的优点是它不需要搜索算法，因此在0.1毫秒至1毫秒的运行时间内非常快。
但是，虽然速度和多功能性很高，但精度却不够准确，平均只有5位正确数字，第五位的偏差为3（使用一百万个随机数和根进行测试），尽管测试使用了非常高的根，因此如果将根保持在10以下，则可以期望更高的精度。
结果只保留64位精度，其余数字为零，因此如果需要非常高的精度，请勿使用此函数。
它是为处理非常大的数字和非常大的根而设计的，而不是处理非常小的数字。
public static BigDecimal nrt(BigDecimal bd,int root) {
//if number is smaller then double_max_value it's faster to use the usual math 
//library
    if(bd.compareTo(BigDecimal.valueOf(Double.MAX_VALUE)) < 0) 
        return new BigDecimal( Math.pow(bd.doubleValue(), 1D / (double)root ));

    BigDecimal in = bd;
    int digits = bd.precision() - bd.scale() -1; //take digits to get the numbers power of ten
    in = in.scaleByPowerOfTen (- (digits - digits%root) ); //scale down to the lowest number with it's power of ten mod root is the same as initial number

    if(in.compareTo(BigDecimal.valueOf( Double.MAX_VALUE) ) > 0) { //if down scaled value is bigger then double_max_value, we find the answer by splitting the roots into factors and calculate them seperately and find the final result by multiplying the subresults
        int highestDenominator = highestDenominator(root);
        if(highestDenominator != 1) {
            return nrt( nrt(bd, root / highestDenominator),highestDenominator); // for example turns 1^(1/25) 1^(1/5)^1(1/5)
        }
        //hitting this point makes the runtime about 5-10 times higher,
        //but the alternative is crashing
        else return nrt(bd,root+1) //+1 to make the root even so it can be broken further down into factors
                    .add(nrt(bd,root-1),MathContext.DECIMAL128) //add the -1 root and take the average to deal with the inaccuracy created by this
                    .divide(BigDecimal.valueOf(2),MathContext.DECIMAL128); 
    } 
    double downScaledResult = Math.pow(in.doubleValue(), 1D /root); //do the calculation on the downscaled value
    BigDecimal BDResult =new BigDecimal(downScaledResult) // scale back up by the downscaled value divided by root
            .scaleByPowerOfTen( (digits - digits % root) / root );
    return BDResult;
}
private static int highestDenominator(int n) {
    for(int i = n-1; i>1;i--) {
        if(n % i == 0) {
            return i;
        }
    }
    return 1;
}

它的工作原理是利用一种数学属性，基本上是说在进行平方根运算时，可以将x^0.5改为(x/100)^0.5 * 10，所以将底数除以100，然后取幂并乘以10。一般化后，变成x^(1/n) = (x / 10^n) ^ (1/n) * 10。因此，对于立方根，需要将底数除以10^3，对于四次方根，需要除以10^4，依此类推。该算法使用这些函数将输入缩小到数学库可以处理的范围，然后根据输入被缩小的程度将其放大回来。它还处理了一些边缘情况，其中输入无法缩小足够多，正是这些边缘情况导致了许多准确性问题。
1

如前所述：如果您不在意答案的精度，但只想在第15位之后生成随机数字，那么为什么要使用BigDecimal？

下面是用于处理浮点数BigDecimal的方法的代码：

    import java.math.BigDecimal;
    import java.math.BigInteger;
    import java.math.MathContext;



public BigDecimal bigSqrt(BigDecimal d, MathContext mc) {
    // 1. Make sure argument is non-negative and treat Argument 0
    int sign = d.signum();
    if(sign == -1)
      throw new ArithmeticException("Invalid (negative) argument of sqrt: "+d);
    else if(sign == 0)
      return BigDecimal.ZERO;
    // 2. Scaling:
    // factorize d = scaledD * scaleFactorD 
    //             = scaledD * (sqrtApproxD * sqrtApproxD)
    // such that scalefactorD is easy to take the square root
    // you use scale and bitlength for this, and if odd add or subtract a one
    BigInteger bigI=d.unscaledValue();
    int bigS=d.scale();
    int bigL = bigI.bitLength();
    BigInteger scaleFactorI;
    BigInteger sqrtApproxI;
    if ((bigL%2==0)){
       scaleFactorI=BigInteger.ONE.shiftLeft(bigL);
       sqrtApproxI=BigInteger.ONE.shiftLeft(bigL/2);           
    }else{
       scaleFactorI=BigInteger.ONE.shiftLeft(bigL-1);
       sqrtApproxI=BigInteger.ONE.shiftLeft((bigL-1)/2 );          
    }
    BigDecimal scaleFactorD;
    BigDecimal sqrtApproxD;
    if ((bigS%2==0)){
        scaleFactorD=new BigDecimal(scaleFactorI,bigS);
        sqrtApproxD=new BigDecimal(sqrtApproxI,bigS/2);
    }else{
        scaleFactorD=new BigDecimal(scaleFactorI,bigS+1);
        sqrtApproxD=new BigDecimal(sqrtApproxI,(bigS+1)/2);         
    }
    BigDecimal scaledD=d.divide(scaleFactorD);

    // 3. This is the core algorithm:
    //    Newton-Ralpson for scaledD : In case of f(x)=sqrt(x),
    //    Heron's Method or Babylonian Method are other names for the same thing.
    //    Since this is scaled we can be sure that scaledD.doubleValue() works 
    //    for the start value of the iteration without overflow or underflow
    System.out.println("ScaledD="+scaledD);
    double dbl = scaledD.doubleValue();
    double sqrtDbl = Math.sqrt(dbl);
    BigDecimal a = new BigDecimal(sqrtDbl, mc);

    BigDecimal HALF=BigDecimal.ONE.divide(BigDecimal.ONE.add(BigDecimal.ONE));
    BigDecimal h = new BigDecimal("0", mc);
    // when to stop iterating? You start with ~15 digits of precision, and Newton-Ralphson is quadratic
    // in approximation speed, so in roundabout doubles the number of valid digits with each step.
    // This fmay be safer than testing a BigDecifmal against zero.
    int prec = mc.getPrecision();
    int start = 15;
    do {
        h = scaledD.divide(a, mc);
        a = a.add(h).multiply(HALF);
        start *= 2;
    } while (start <= prec);        
    // 3. Return rescaled answer. sqrt(d)= sqrt(scaledD)*sqrtApproxD :          
    return (a.multiply(sqrtApproxD));
}

作为一个测试，尝试多次平方一个数字，然后再进行重复的平方根运算，看看你距离起点有多接近。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接