Java中BigDecimal的平方根
我们可以通过仅使用Java API而不是自定义的100行algorithm来计算Java中BigDecimal平方根吗？
我用过这个，效果很好。 下面是algorithm如何在高层工作的一个例子。
编辑：我很好奇，看到如何定义如下准确。 这是来自官方的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的答案。 它更简洁，似乎提供了更好或更好的精度。
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位！
通过使用卡普技巧，这可以实现没有一个循环只有两行，给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))); }
如果你只需要find整数平方根 – 这是两个可以使用的方法。
牛顿的方法 – 即使是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, ie approximate value is found } while (l.compareTo(BigInteger.ONE) > 0); return m; }
如果要计算具有更多数字的数字的平方根，而不是以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做正常的四舍五入。
这是非常准确和快速的解决scheme，它是基于我的BigIntSqRoot解决scheme和下一个观察： A ^ 2B – 是A的平方根乘以B的根 。 使用这种方法，我可以很容易地计算2的平方根的前1000位数。
1.
所以这里是源代码
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); } }
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; } }
public static BigDecimal sqrt( final BigDecimal value ) { BigDecimal guess = value.multiply( DECIMAL_HALF ); BigDecimal previousGuess; do { previousGuess = guess; guess = sqrtGuess( guess, value ); } while ( guess.subtract( previousGuess ).abs().compareTo( EPSILON ) == 1 ); return guess; } private static BigDecimal sqrtGuess( final BigDecimal guess, final BigDecimal value ) { return guess.subtract( guess.multiply( guess ).subtract( value ).divide( DECIMAL_TWO.multiply( guess ), SCALE, RoundingMode.HALF_UP ) ); } private static BigDecimal epsilon() { final StringBuilder builder = new StringBuilder( "0." ); for ( int i = 0; i < SCALE - 1; ++i ) { builder.append( "0" ); } builder.append( "1" ); return new BigDecimal( builder.toString() ); } private static final int SCALE = 1024; private static final BigDecimal EPSILON = epsilon(); public static final BigDecimal DECIMAL_HALF = new BigDecimal( "0.5" ); public static final BigDecimal DECIMAL_TWO = new BigDecimal( "2" );
正如之前所说：如果你不介意你的答案会是什么精度，但只是想在第15个有效的数字之后产生随机数字，那你为什么要使用BigDecimal呢？
这里是应该用浮点BigDecimals做这个技巧的方法的代码：
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)); }
作为一个testing，试着重复数次，而不是重复平方根，看看你离开始的距离有多近。
BigDecimal.valueOf(Math.sqrt(myBigDecimal.doubleValue()));
假设你不想只处理小的小数点的小事情，你想pipe理精度，那么答案是否定的：这不能在几个LOC没有外部库，但这个相关的问题列表一些好的。
